本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-14 16:08:25

OMv(Online Matrix–Vector multiplication)猜想：

给定布尔矩阵 $M \in \{0,1\}^{n\times n}$，接下来会收到 $n$ 个 $n$ 维布尔向量 $v^{(1)},\dots,v^{(n)}$，在线回答 $$ Mv^{(t)} $$ 的结果，这里将矩阵乘法定义中的 $+$ 换为 $\ee$，$\times$ 换为 $\wedge$。

对于上述 OMv 问题，不存在一个算法能在 $O(n^{3-\epsilon})$ 时间内解决。

目前还没有找到一个这样算法或是证明猜想成立。

以下证明仅能得到强制在线回答中位数时的一个复杂度下界 $\widetilde{O}(n^{1.5})$，笔者水平有限，还未得到一个高于 $\widetilde{O}(n)$ 的可离线版本的复杂度下界。

我们考虑树是一条链，即在一个给定序列 $a_i$ 上操作，查询换为给定 $m$，验证其是否为当前的中位数，这个问题显然要更弱。

沿用上面描述 OMv 问题时的记号，考虑任意一个规模为 $\sqrt{n}$ 的 OMv 问题。初始令 $a = \{\}$，先枚举 $M$ 的每一列 $j$，再枚举每一行 $i$，当 $m_{i,j}=1$ 时，向 $a$ 最后加入一个数 $i$。最终得到长度不超过 $n$ 的序列 $a$。记第 $j$ 列加入的元素为 $a_{l_j,\dots,r_j}$。

要查询 $Mv^{(t)}$ 时，从 $1$ 到 $\sqrt{n}$ 枚举 $j$，当 $v^{(t)}j=1$ 时，说明 $M$ 的第 $j$ 列会对答案造成贡献，此时将 $a{l_j,\dots,r_j}$ 加入 $D$ 中一次。最后我们想知道对于每个行编号 $i$，$i$ 在 $a$ 中的出现次数有没有增加。

由于有强制在线，只需要在 $a$ 中额外加一个 $0$ 和 $n+1$，通过填充 $0$ 和 $\sqrt{n}+1$ 的个数可以一次询问求出序列中 $\le i$ 的数是否至少有 $c$ 个，然后即可二分求出当前序列中一个数 $i$ 的出现次数。

这样修改和询问都是 $\widetilde{O}(n)$ 级别的，如果存在一个 $\widetilde{O}(n^{1.5-\epsilon})$ 时间内解决中位数查询问题的算法，则有 OMv 猜想不成立。因此该问题目前的一个复杂度下界为 $\widetilde{O}(n^{1.5})$

将 $(i,a_i)$ 看作二维平面上一个点，我们的修改是将矩形 $[l,r]\times (-\infty,+\infty)$ 内所有点权值 $+k$，查询使用二分答案，求矩形 $(-\infty,+\infty)\times (-\infty, m]$ 内所有点的点权和，转化成一个特殊的动态矩形加、矩形和问题。

对于 $d$ 维欧式空间中的在线 $d$ 维矩形加，矩形求和（半群信息），这篇文章给出了一个对任意 $T_{\mathrm{qry}}(n),T_{\mathrm{upd}}(n)$ 满足 $T_{\mathrm{qry}}(n)\times T_{\mathrm{upd}}(n) = n$，$\widetilde{O}(n)$ 空间，修改耗时 $O(T_{\mathrm{upd}}\log^d n)$，查询耗时 $O(T_{\mathrm{qry}}\log^d n)$ 的结构。且同样通过 OMv 归约证明了 $\widetilde{O}(n^{1.5})$ 是目前的复杂度下界。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-14 16:10:10

传送门： P13698

先把所有点按照权值 $a_i$ 排序得到一个排列 $p_i$，也即做离散化。为了方便处理，将所有 $1$ 类修改操作离线下来，对于第 $i$ 次 $1$ 修改，若在其后出现了 $c$ 次复制操作，就将这次修改的 $k$ 更改为 $k2^c$。我们的目标是求出每次 $1$ 类操作后的中位数，设 $len_i$ 表示第 $i$ 次操作后 $D$ 的长度。

经典思路是将 $p_i$ 按照块长 $B = \Theta(\sqrt{n})$ 分块，对每次询问先求出中位数所在的块，然后再枚举块中的每个点检查是否是答案。

对于整块查询，记第 $i$ 块的左右端点为 $l_i,r_i$，对每一块 $i$ 以及前 $j$ 次修改求出 $f_{i,j}$ 表示 $p_{1,\dots,r_i}$ 在前 $j$ 修改中共被加入 $D$ 中 $f_{i,j}$ 次，找到最小的 $j$ 满足 $f_{i,j} \ge \lceil \dfrac{len_j}{2} \rceil$。对每个 $i$ 求出 $sum_u$ 表示树上从点 $u$ 到点 $1$ 的路径上出现了 $sum_u$ 个 $p_{1,\dots,r_i}$ 中的点即可 $O(n\sqrt{n})$ 求出所有的 $f_{i,j}$。

对于散点检查，我们需要求出一个点 $u$ 在前 $j$ 次修改中被加入的次数。依次枚举修改 $u,v,k$，则路径 $u\rightarrow v$ 上的点加入次数 $+k$。差分后支持单点加，查询区间和即可。由于修改次数为 $O(n)$，查询次数为 $O(n\sqrt{n})$，依然按 $B$ 分块后平衡为单次修改 $O(\sqrt{n})$，单次查询 $O(1)$ 即可。

时间复杂度 $O(n\sqrt{n})$，将处理整块的过程离线即可做到空间复杂度 $O(n)$。

关于强制在线版本复杂度下界的一个证明

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

typedef long long ll;
const int N = 1e5+5;
const int B = 1500;
const int Mod = 998244353;

int n, m, a[N], id[N];
int nfd[N], dfn[N], ct[N], f[N], dep[N], siz[N], hs[N];

vector<int> T[N];

void dfs1(int x, int fa) {
    f[x] = fa;
    dep[x] = dep[fa] + 1;
    siz[x] = 1;
    for (auto s : T[x]) {
        if (s == fa) continue;
        dfs1(s, x);
        siz[x] += siz[s];
        if (siz[s] >= siz[hs[x]]) hs[x] = s;
    }
}

void dfs2(int x, int ctop) {
    ct[x] = ctop;
    nfd[dfn[x] = ++dfn[0]] = x;
    if (hs[x]) dfs2(hs[x], ctop);
    for (auto s : T[x]) {
        if (s == f[x] || s == hs[x]) continue;
        dfs2(s, s);
    }
}

inline int lca(int u, int v) {
    while (ct[u] != ct[v]) {
        if (dep[ct[u]] < dep[ct[v]]) swap(u, v);
        u = f[ct[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

inline int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)] + 1; }

struct op {
    int u, v, l;
    ll k;
    op() {}
    op(ll _k, int _v, int _u): u(_u), v(_v), k(_k) { l = lca(_u, _v); }
} P[N];

int qry_p[N], db_p[N], st[N], ans[N];
int bl[N \/ B + 5], br[N \/ B + 5], sum[N];
bitset<N> v;
ll nd[N];

namespace B1 {\/\/O(sqrt(n))单点加，O(1)区间和
    const int B = 330;

    ll sb[N \/ B + 5], s[N + B];
    inline void add(int x, ll k) {
        int xb = x \/ B;
        for (int i = xb + 1; i <= n \/ B; i++) sb[i] += k;
        for (int i = x; i \/ B == xb; i++) s[i] += k;
    }
    inline ll qry(int x) { return sb[x \/ B] + s[x]; }

    inline void upd(op p) {
        add(dfn[p.u], p.k);
        add(dfn[p.v], p.k);
        add(dfn[p.l], -p.k);
        if (f[p.l]) add(dfn[f[p.l]], -p.k);
    }
}

int main() {
    n = read();

    for (int i = 1; i <= n; i++) a[i] = read(), id[i] = i;

    sort(id + 1, id + n + 1, [](int x, int y) { return a[x] < a[y]; });

    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        T[u].pb(v);
        T[v].pb(u);
    }

    dfs1(1, 0);
    dfs2(1, 1);

    int _ = read();
    ll cl = 0;
    while (_--) {
        int o = read();
        if (o == 1) P[++m] = op(read(), read(), read());
        else if (o == 2) qry_p[m]++;
        else db_p[m]++;
    }

    for (ll i = m, t = 1; i; i--) {
        while (db_p[i]--) t <<= 1;
        P[i].k *= t;
    }
    for (int i = 1; i <= m; i++)
        cl += P[i].k * dis(P[i].u, P[i].v), nd[i] = (cl + 1) \/ 2;

    for (int i = 0; i <= n \/ B; i++) {
        bl[i] = max(1, i * B);
        br[i] = min(n, i * B + B - 1);

        for (int j = bl[i]; j <= br[i]; j++) v[id[j]] = 1;
        for (int j = 1; j <= n; j++) sum[nfd[j]] = sum[f[nfd[j]]] + v[nfd[j]];
        for (int j = bl[i]; j <= br[i]; j++) v[id[j]] = 0;
        
        cl = 0;
        for (int j = 1; j <= m; j++) {
            cl += P[j].k * (sum[P[j].u] + sum[P[j].v] - sum[P[j].l] - sum[f[P[j].l]]);
            if (!st[j] && qry_p[j]) {
                if (nd[j] > cl) nd[j] -= cl;
                else st[j] = bl[i];
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        B1::upd(P[i]);
        
        if (qry_p[i]) {
            for (int j = st[i]; ; j++) {
                cl = B1::qry(dfn[id[j]] + siz[id[j]] - 1) - B1::qry(dfn[id[j]] - 1);
                if (nd[i] > cl) nd[i] -= cl;
                else { ans[i] = id[j]; break; }
            }
        }
    }

    for (int i = 0; i <= m; i++) while (qry_p[i]--) printf("%d\n", a[ans[i]]);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-03 17:40:54

传送门： ABC275Ex

题目大意：

给定 $n$ 以及两个长度为 $n$ 的正整数序列 $A_i,B_i$，你可以执行下述操作任意次：

• 选定任意整数 $l,r$，满足 $1 \le l \le r \le n$。
• 花费 $max_{i=l}^{r} \{B_i\}$ 的代价，将 $A_l,A_{l+1}, \dots A_r$ 中每个都减去 $1$。

请求出使得 $A_i$ 中元素全部 $\le 0$ 所需的最小代价。

$1 \le n \le 10^5, 1 \le A_i,B_i \le 10^9$。

看到这题第一反应是：这不 [APIO2016] 烟火表演 吗？实际两题在思路和做法上确实非常相似。

首先注意到代价是一个区间极值的形式，而且在代价不变的时候，修改区间肯定是越大越好。不难想到根据 $B$ 建立笛卡尔树，一次操作就是选择一个节点 $i$，花费 $B_i$ 的代价使得 $x$ 子树内所有点对应的 $A$ 减 $1$。

其次，我们只需要关心子树内当前 $A$ 的最大值，可以设计 dp 状态 $f_{i,j}$ 表示当前子树 $i$ 内 $A$ 的最大值 $\le j$ 时所需的最小代价，设点 $i$ 的左右儿子分别为 $x,y$，不难得到转移方程：

$$ \begin{aligned} f_{i,j} &= \min_{k = \max(j,A_i)}^{+\infty} \{f_{x,k}+f_{y,k}+(k-j)B_i \}\ &= -B_ij + \min_{k = \max(j,A_i)}^{+\infty} \{f_{x,k}+f_{y,k}+B_ik \} \end{aligned} $$

这样做是 $O(nV)$ 的，显然要从值域入手优化。将 $f_{i,j}$ 看作关于 $j$ 的函数，对于这种没有明显特征的转移方程，可以手玩一下小一点的数据，观察 $f_{i,j}$ 的图像，可以看出 $f_{i,j}$ 是一次分段下凸函数（其实题做多了以后，看到这个式子的第一反应就是凸性优化）。

证明可以考虑归纳法，首先空节点的 $f$ 图像就是与横轴重合的直线，满足归纳假设，接下来先考虑 $f_{x,k}+f_{y,k}+B_ik$，显然这是三个一次分段凸函数相加（$B_ik$ 就是一条斜率为 $B_i$ 的直线），结果仍然是一次分段凸函数，图像大致长这样：

观察 $\min_{k= \max(j,A_i)}^{+\infty}$ 对这个函数图像的变换效果，首先找到直线 $x=A_i$ 右侧的最低点（图中为点C），对于最低点左侧的部分，其函数值等于最低点对应的函数值，右侧保持不变，也就是长这样（红色部分）：

当然也可能长这样：

可以看作是将斜率小于 $0$ 以及 $\le A_i$ 的部分全部删掉，并在一开始加入一段斜率为 $0$ 的线段，变换后再加上 $-B_ij$（一条直线），很明显依然是一个一次分段下凸函数。

很明显一次转移最多新加入 $O(1)$ 条线段，所以总段数是 $O(n)$ 的，考虑用数据结构加速维护过程，官方题解使用的是 set+启发式合并，时间复杂度 $O(n \log^2n)$。不过这个东西用可并堆也非常容易维护，具体来说，可以维护图像上拐点的横坐标以及拐点右侧线段与左侧线段斜率之差，按照横坐标大小维护小根堆，两个函数相加就直接把两个堆合并起来，进行 $\min_{k= \max(j,A_i)}^{+\infty}$ 这个变换的时候就直接暴力删点，总共只会删 $O(n)$ 次，总复杂度 $O(n \log n)$。

代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 1e5+5;
const int Mod = 998244353;

int n, A[MAXN], B[MAXN];
int l[MAXN], r[MAXN], stk[MAXN], top;
int rt[MAXN], tot;
ll cur[MAXN];

struct node {
    int ls, rs, dis;
    ll x, k;
} H[MAXN * 4];

int merge(int a, int b) {
    if (!a || !b) return a | b;
    if (H[a].x > H[b].x) swap(a, b);
    H[a].rs = merge(H[a].rs, b);
    if (H[H[a].rs].dis > H[H[a].ls].dis) swap(H[a].ls, H[a].rs);
    H[a].dis = H[H[a].rs].dis + 1;
    return a;
}

inline void push(int num, ll x, ll k) {
    H[++tot].x = x;
    H[tot].k = k;
    rt[num] = merge(tot, rt[num]);
}

inline void pop(int num) {
    rt[num] = merge(H[rt[num]].ls, H[rt[num]].rs);
}

void dfs(int x) {
    if (!x) return;
    dfs(l[x]), dfs(r[x]);
    cur[x] = cur[l[x]] + cur[r[x]];
    rt[x] = merge(rt[l[x]], rt[r[x]]);
    push(x, 0, B[x]);
    ll curx = 0, curk = 0;\/\/当前斜率
    while (1) {
        curx = H[rt[x]].x;
        curk += H[rt[x]].k;
        if (curk >= 0 && curx >= A[x]) {
            H[rt[x]].k = curk;
            push(x, 0, 0);
            break;
        }
        pop(x);
        if (curk >= 0 && (!rt[x] || H[rt[x]].x >= A[x])) {
            cur[x] += curk * (A[x] - curx);
            push(x, A[x], curk);
            push(x, 0, 0);
            break;
        }
        cur[x] += curk * (H[rt[x]].x - curx);
    }
    push(x, 0, -B[x]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &B[i]);

    for (int i = 1; i <= n; i++) {
        int lst = 0;
        while (top && B[stk[top]] <= B[i]) {
            r[stk[top]] = lst;
            lst = stk[top--];
        }
        l[i] = lst;
        stk[++top] = i;
    }
    for (int i = 2; i <= top; i++) r[stk[i - 1]] = stk[i];

    dfs(stk[1]);

    printf("%lld", cur[stk[1]]);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-06 10:19:23

传送门： G - Count Sequences

题目大意： 求长度为 $n$ 的整数序列 $a_i$ 的个数，满足：

• $0 \le a_1 \le a_2 \le \dots \le a_n \le m$.
• $\forall 1 \le i < n,a_i \not \equiv a_{i+1} \pmod{3}$.

生成函数入门题，完全不需要考虑组合意义。

首先有一个很明显的 $O(nm^2)$ dp，记 $f_{i,j}$ 为考虑序列前 $i$ 个数，且 $a_i=j$ 时的序列个数，有转移：

$$ f_{i,j} = \begin{cases} 1 &i=1\ \sum_{ 0 \le k \le j, k \not \equiv j } f_{i-1,k} &i > 1 \end{cases} $$

可以用前缀和优化到 $O(nm)$，但很明显不够，考虑设OGF $F_i(x) = \sum_{j \ge 0} f_{i,j}x^j$，上面的转移式就变成了：

$$ F_i(x) = \begin{cases} \dfrac{1}{1-x} &i=1\ \dfrac{x^2+x}{1-x^3} F_{i-1}(x) &i > 1 \end{cases} $$

很明显可以得到 $F_i(x)$ 的封闭形式：

$$ F_i(x) = \dfrac{(x^2+x)^{i-1}}{(1-x)(1-x^3)^{i-1}} $$

最后的答案是 $\sum_{i=0}^m f_{n,i}$，那么我们要求的就是：

$$ \begin{aligned} &\sum_{i=0}^m[x^i] F_n(x) \ = &[x^m]\dfrac{1}{1-x}F_{n}(x)\ = &[x^m] \dfrac{(x^2+x)^{n-1}}{(1-x)^2(1-x^3)^{n-1}}\ = &[x^m] \dfrac{x^{n-1}(x+1)^{n-1}}{(1-x)^2(1-x^3)^{n-1}}\ = &[x^{m-n+1}] \dfrac{(x+1)^{n-1}}{(1-x)^2} \cdot \dfrac{1}{(1-x^3)^{n-1}}\ \end{aligned} $$

其中 $\dfrac{(x+1)^{n-1}}{(1-x)^2}$ 就是 $(x+1)^{n-1}$ 的二阶前缀和，而 $(x+1)^{n-1},\dfrac{1}{(1-x^3)^{n-1}}$ 均为经典的关于组合数的生成函数：

$$ \begin{aligned} (x+1)^{n-1} &= \sum_{i \ge 0} \binom{n-1}{i}x^i\ \dfrac{1}{(1-x^3)^{n-1}} &= \sum_{i \ge 0} \binom{i+n-2}{n-2}(x^3)^i \end{aligned} $$

$\dfrac{(x+1)^{n-1}}{(1-x)^2},\dfrac{1}{(1-x^3)^{n-1}}$ 的前 $m-n+1$ 项均可在线性时间内算出，同样可在线性时间内算出二者卷积的第 $m-n+1$ 项，总复杂度线性。

感觉这个式子找不出什么组合意义。

题外话：使用线性递推可以做到 $O(n \log n \log m)$，$n$ 开到 $10^5$ 级别，此时 $m$ 可以开到 $10^{18}$。

代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int V = 1e7+5;
const int Mod = 998244353;

int n, m, ans;
ll fac[V], finv[V], F[V];

inline int qpow(int a, int b) {
    ll base = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * base % Mod;
        base = base * base % Mod;
        b >>= 1;
    }
    return ans;
}

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }
inline ll C(int n, int m) {
    if (m > n) return 0;
    return fac[n] * finv[m] % Mod * finv[n - m] % Mod;
}

int main() {
    fac[0] = 1;
    for (int i = 1; i < V; i++) fac[i] = fac[i - 1] * i % Mod;
    finv[V - 1] = qpow(fac[V - 1], Mod - 2);
    for (int i = V - 1; i; i--) finv[i - 1] = finv[i] * i % Mod;

    scanf("%d%d", &n, &m);
    
    F[0] = 1;
    for (int i = 1; i <= m - n + 1; i++) F[i] = (F[i - 1] + C(n - 1, i)) % Mod;
    for (int i = 1; i <= m - n + 1; i++) F[i] = (F[i - 1] + F[i]) % Mod;
    for (int i = 0; i <= m - n + 1; i += 3) Add(ans, C(i \/ 3 + n - 2, n - 2) * F[m - n + 1 - i] % Mod);

    printf("%d", ans);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-06 20:56:47

传送门： C. Watching Fireworks is Fun

upd：这题的slope trick（现在才知道这个优化原来叫这个）和 CF1534G 一模一样，而且只用两个优先队列维护即可，比我当时写的一坨splay简洁多了。

考虑记 $f_{i,j}$ 为第 $i$ 个烟花燃放后，当前位置在 $j$ 时的最大快乐值，转移显然：

$$ f_{i,j} = \max_{k = - d(t_i-t_{i-1})}^{d(t_i-t_{i-1})}\{f_{i-1,j+k} \} + b_i- |a_i-j| $$

观察转移式，$f_i$ 是由 $f_{i-1}$ 加上一个关于 $j$ 的函数 $b_i-|a_i-j|$ 得到的，注意到 $b_i-|a_i-j|$ 是上凸函数，不妨猜测 $f_i$ 也是上凸函数，事实上使用归纳法非常容易证明—— $\max_{k = - d(t_i-t_{i-1})}^{d(t_i-t_{i-1})}\{f_{i-1,j+k} \}$ 相当于将 $f_{i,j}$ 的图像从最高点处分为左右两半，左半边整体向左平移 $d(t_i-t_{i-1})$，右半边整体向右平移 $d(t_i-t_{i-1})$，最后再用一条斜率为 $0$ 的线段从断点处将两部分连接起来，很明显若 $f_{i-1}$ 是上凸函数，那么变换后依然保持上凸，$f_i$ 就等于两个上凸函数相加，必然还是上凸函数。

用平衡树维护函数上的拐点，即可在 $O(m \log m)$ 时间内解决本问题。

代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define ll __int128
#define pb push_back
#define mp make_pair
using namespace std;

const int MAXN = 4e5+5;
const int Mod = 998244353;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

void write(ll x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x \/ 10);
    putchar(x % 10 + '0');
}

int n, m, d;
int rt = 1, tot = 1;
ll delta;

struct fireworks {
    int a, b, t;
} F[MAXN];

struct node {
    int son[2], fa;
    ll adx, adk, x, k, dy, lx, rx, rk;
} T[MAXN];

#define son(x, s) T[x].son[s]
#define f(x) T[x].fa

inline void cct(int x, int y, bool loc) { son(x, loc) = y, f(y) = x; }
inline bool get_son(int x) { return son(f(x), 1) == x; }

inline void push_up(int x) {
    if (!x) return;
    T[x].lx = son(x, 0) ? T[son(x, 0)].lx : T[x].x;
    T[x].rx = son(x, 1) ? T[son(x, 1)].rx : T[x].x;
    T[x].rk = son(x, 1) ? T[son(x, 1)].rk : T[x].k;
    T[x].dy = T[son(x, 0)].dy + T[son(x, 1)].dy;
    if (son(x, 1)) T[x].dy += (T[son(x, 1)].lx - T[x].x) * T[x].k;
    if (son(x, 0)) T[x].dy += (T[x].x - T[son(x, 0)].rx) * T[son(x, 0)].rk;
}

inline void addx(int x, ll k) { if (x) T[x].x += k, T[x].adx += k, T[x].lx += k, T[x].rx += k; }
inline void addk(int x, ll k) { if (x) T[x].k += k, T[x].adk += k, T[x].dy += (T[x].rx - T[x].lx) * k, T[x].rk += k; }
inline void push_down(int x) {
    if (T[x].adx) {
        addx(son(x, 0), T[x].adx);
        addx(son(x, 1), T[x].adx);
        T[x].adx = 0;
    }
    if (T[x].adk) {
        addk(son(x, 0), T[x].adk);
        addk(son(x, 1), T[x].adk);
        T[x].adk = 0;
    }
}

inline void rotate(int x) {
    int y = f(x);
    bool loc = get_son(x);
    f(x) = f(y);
    if (f(y)) {
        son(f(y), get_son(y)) = x;
    }
    cct(y, son(x, loc ^ 1), loc);
    cct(x, y, loc ^ 1);
    push_up(y), push_up(x);
}

inline void splay(int x) {
    for (int y = f(x); y; rotate(x), y = f(x))
        if (f(y))
            rotate(get_son(x) == get_son(y) ? y : x);
    rt = x;
}

inline void find() {\/\/找到最高点
    int x = rt, ret;
    while (x) {
        push_down(x);
        if (T[x].k <= 0) ret = x, x = son(x, 0);
        else x = son(x, 1);
    }
    splay(ret);
}

inline void find(ll k) {
    int x = rt, ret;
    while (x) {
        push_down(x);
        if (T[x].x <= k) ret = x, x = son(x, 1);
        else x = son(x, 0);
    }
    splay(ret);
}

int main() {
    n = read(), m = read(), d = read();
    for (int i = 1; i <= m; i++) {
        F[i].a = read(), F[i].b = read(), F[i].t = read();
        delta += F[i].b - F[i].a - (ll) F[i].t * d;
    }

    sort(F + 1, F + m + 1, [](fireworks a, fireworks b) { return a.t < b.t; });

    for (int i = 1; i <= m; i++) {

        find();

        if (T[rt].k) {
            T[++tot] = T[rt], son(tot, 0) = 0;
            T[rt].k = 0;
            cct(tot, son(rt, 1), 1);
            cct(rt, tot, 1);
            push_up(tot), push_up(rt);
        }
        ll D = (ll) d * (F[i].t - F[i - 1].t);
        T[rt].x -= D;
        addx(son(rt, 0), -D);
        addx(son(rt, 1), D);
        push_up(rt);

        find(F[i].a);

        if (T[rt].x < F[i].a) {
            T[++tot] = T[rt], son(tot, 0) = 0;
            T[tot].x = F[i].a, T[rt].k += 1;
            cct(tot, son(rt, 1), 1);
            cct(rt, tot, 1);
            push_up(tot), push_up(rt);
        } else T[rt].k -= 1;
        addk(son(rt, 0), 1);
        addk(son(rt, 1), -1);
        push_up(rt);
    }

    find();
    write(delta + T[son(rt, 0)].dy + (T[rt].x - T[son(rt, 0)].rx) * T[son(rt, 0)].rk);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-29 10:18:45

T2 数组开小+多测没清干净，估计会挂得比较惨（不过在洛谷上居然有75pts），没什么心情，题解随便写写吧。

2022/12/6 upd：昨天出成绩了，T2 好歹有35pts，不过听说 $O(nm)$ 能过TAT。。。

T1.plant

记 $A_{i,j}$ 表示从点 $(i,j)$ 最多能向右延伸多少格，那么以 $(x1,y1),(x2,y1)$ 为拐点的 C 的个数就是 $A_{x1,y1} \cdot A_{x2,y1}$，F 的个数还要再乘上点 $(x2,y1)$ 最多向下延伸的格数，这个东西用前缀和维护一下就能做到 $O(nm)$。

考场代码：

\/\/-O2 -std=c++14 -Wl,-stack=134217728 -Wall -Wextra -Wshadow
#include <bits\/stdc++.h>
#define pb push_back
#define eb emplace_back
#define lowbit(x) (x & -x)
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 1005;
const int Mod = 998244353;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
	while (c >= '0' && c <= '9') x =  x * 10 + (c - '0'), c = getchar();
	return x * f;
}

int n, m, c, f, ansc, ansf;
int dc[MAXN], rc[MAXN][MAXN], sumc[MAXN][MAXN], sumf[MAXN][MAXN];
char a[MAXN][MAXN];

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

void solve() {
	n = read(), m = read(), c = read(), f = read();
	for (int i = 1; i <= n; i++) {
		scanf(" %s", a[i] + 1);
		rc[i][m + 1] = 0;
		for (int j = m; j; j--) {
			sumc[i][j] = sumf[i][j] = 0;
			if (a[i][j] == '1') rc[i][j] = 0;
			else rc[i][j] = rc[i][j + 1] + 1;
		}
	}
	
	ansc = ansf = 0;
	
	for (int i = 1; i <= m; i++) dc[i] = n + 1, sumc[n + 1][i] = sumf[n + 1][i] = 0;
	for (int i = n; i; i--) {
		for (int j = 1; j <= m; j++) {
			sumc[i][j] = sumc[i + 1][j];
			sumf[i][j] = sumf[i + 1][j];
			if (rc[i][j]) {
				if (i < n && a[i + 1][j] != '1') {
					Add(ansc, (ll) (rc[i][j] - 1) * (sumc[i + 2][j] - sumc[dc[j]][j] + Mod) % Mod);
					Add(ansf, (ll) (rc[i][j] - 1) * (sumf[i + 2][j] - sumf[dc[j]][j] + Mod) % Mod);
				}
				Add(sumc[i][j], rc[i][j] - 1);
				Add(sumf[i][j], (ll) (rc[i][j] - 1) * (dc[j] - i - 1) % Mod);
			} else {
				dc[j] = i;
			}
		}
	}
	
\/\/	for (int i = 1; i <= n; i++, puts(""))
\/\/		for (int j = 1; j <= m; j++) printf("%d ", sumf[i][j]);
	printf("%d %d\n", c * ansc, f * ansf);
}

int main() {
	freopen("plant.in", "r", stdin);
	freopen("plant.out", "w", stdout);

	int T = read(), id = read();
	while (T--) {
		solve();
	}
	return 0;
}

T2.meow

为什么不把这题放T4 /fn/fn/fn

考场看到这个构造都懵了，虽然看了眼T3发现很简单，但心态还是快崩了，一直在想我不会连NOIP T2都做不出来吧，好在吃了块巧克力冷静了下来，连想带码一共花了两个半小时总算写出来了，虽然最后还是因为数组开小+多测没清空挂飞了，点这看公开处刑。

首先 $k=2n-2$ 时非常容易构造，我们可以保持一个栈时刻为空，另外 $n-1$ 个栈各最多有 $2$ 个元素，这样 $2n-2$ 个元素恰好可以放进这 $n-1$ 个栈中且要么是栈顶，要么是栈底，这样下一个元素如果在栈顶，那就直接消去，如果在栈底，则刚好可以利用空栈消去。

接下来考虑 $k=2n-1$ 时的情况，依然可以延续 $k=2n-2$ 时的想法，时刻保证一个栈为空，另外 $n-1$ 个栈保持上限 $2$ 个元素，此时我们就要考虑已经放入 $2n-2$ 个元素，即 $n-1$ 个栈已经填满时，如果再加入新的元素 $x$ 是应怎么操作。

注意到只有元素在栈底时我们才需要用到空栈来消除，假设当前要操作的新元素 $x$ 是 $a_i$，那么我们从 $i$ 开始往后找到第一个出现在栈底的元素 $y$，假设它是 $a_j$（当然也可能先遇到了一个新的 $x$），也就是说 $a_{i+1 \dots j-1}$ 全都是出现在栈顶的元素，我们去看 $y$ 所在栈的栈顶是否在 $a_{i+1 \dots j-1}$ 中出现过，接下来有三种情况：

1. $y$ 所在栈的栈顶在 $a_{i+1 \dots j-1}$ 中出现过，说明在操作到 $a_j$ 之前，压在它上面的元素已经被消去了，此时我们可以将 $a_i$ 压入当前的空栈中，因为 $a_{i+1 \dots j-1}$ 全部是出现在栈顶的元素，所以操作到 $a_j$ 时一定可以保证其所在栈中只有 $y$ 这一个元素，直接把它消去，这样就能再次空出来一个新栈。
2. $y$ 所在栈的栈顶在 $a_{i+1 \dots j-1}$ 中没出现过，说明操作到 $a_j$ 之前，$y$ 所在栈都不需要进行操作，此时直接将 $a_i$ 压入 $y$ 所在栈中（这个栈就有了三个元素），依然保持原来的空栈，直到操作到 $a_j$ 时就可以通过空栈将栈底的 $y$ 消去，这样就又变成了一个空栈加 $n-1$ 个上限为2的栈。
3. 若在遇到出现在栈底的元素之前先遇到了一个新的 $x$，即 $a_j=x$ 时，此时因为 $a_{i+1 \dots j-1}$ 中元素全部在栈顶出现，所以用不到空栈，直接将 $a_i$ 压入空栈，操作到 $a_j$ 时再将 $a_i$ 消去即可。

考场我写的实现是 $O(n \sum m)$ 的，瓶颈在于需要 $O(n)$ 时间找到一个还没满两个元素的栈，这个用队列可以做到 $O(1)$ 查找。

代码（在考场代码的基础上改成了可以AC洛谷数据的代码）：

\/\/-O2 -std=c++14 -Wl,-stack=134217728 -Wall -Wextra -Wshadow
#include <bits\/stdc++.h>
#define pb push_back
#define eb emplace_back
#define lowbit(x) (x & -x)
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 2e6+5;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
	while (c >= '0' && c <= '9') x =  x * 10 + (c - '0'), c = getchar();
	return x * f;
}

int n, m, k, a[MAXN];
int stt[605], cur[605], tag[605], ban, cnt;\/\/考场数组才开到305，，，

deque<int> Q[605];

struct info {
	int op, x, y;
} ans[MAXN * 2];

inline void bk_in(int num, int x) {
	ans[++cnt] = (info) { 1, num, num };
	if (!Q[num].empty()) stt[Q[num].back()] -= 2;
	Q[num].push_back(x);
	stt[x] = 2;
	cur[x] = num;
	if (Q[num].size() == 1) stt[x] = 3;
}

inline void bk_out(int num, int x) {
	ans[++cnt] = (info) { 1, num, num };
	stt[x] = 0;
	Q[num].pop_back();
	if (!Q[num].empty()) stt[Q[num].back()] |= 2;
}

inline void ft_out(int num, int x) {
	ans[++cnt] = (info) { 1, ban, ban };
	ans[++cnt] = (info) { 2, ban, num };
	stt[x] = 0;
	Q[num].pop_front();
	if (!Q[num].empty()) stt[Q[num].front()] |= 1;
}

void solve() {
	n = read(), m = read(), k = read();
	for (int i = 1; i <= m; i++) a[i] = read();
	for (int i = 1; i <= k; i++) tag[i] = 0;\/\/考场才循环到n，，，
	
	ban = n; cnt = 0;
	for (int i = 1; i <= m; i++) {
		if (stt[a[i]] & 2) {
			bk_out(cur[a[i]], a[i]);
		} else if (stt[a[i]] & 1) {
			ft_out(cur[a[i]], a[i]);
		} else {
			for (int j = 1; j <= n; j++)
				if (Q[j].size() < 2 && j != ban) {
					bk_in(j, a[i]);
					break;
				}
			
			if (!stt[a[i]]) {\/\/出现第2n+1种 
				for (int j = i + 1; j <= m; j++) {
					if (stt[a[j]] == 1) {
						if (tag[Q[cur[a[j]]].back()] == i) {
							bk_in(ban, a[i]);
							ban = cur[a[j]];
						} else {
							bk_in(cur[a[j]], a[i]);
						}
						break;
					} else if (!stt[a[j]]) {
						bk_in(ban, a[i]);
						break;
					} else {
						tag[a[j]] = i;
					}
				}
			}
		}
	}
	printf("%d\n", cnt);
	for (int i = 1; i <= cnt; i++) {
		if (ans[i].op == 1) printf("1 %d\n", ans[i].x);
		else printf("2 %d %d\n", ans[i].x, ans[i].y);
	}
}

int main() {
	\/\/ freopen("meow.in", "r", stdin);
	\/\/ freopen("meow.out", "w", stdout);

	int T = read();
	while (T--) {
		solve();
	}
	return 0;
}

T3.barrack

为什么不把这题放T2 /fn/fn/fn

首先因为 B 只会摧毁一条道路，所以显然 e-DCC 中的边是可选可不选的，用 Tarjan 缩点（Tarjan还是我现糊的写法QAQ）以后无向图就变成了一颗树，问题就变成了在树上选出一个非空点集，这些点的虚树上的边必选，其他边可选可不选，求方案数，使用树形 dp 即可解决：

设状态 $f_{i,0/1/2}$ 表示考虑以 $i$ 为根的子树的方案数，0 为子树内没选点，1 为子树内选点的 lca 不是 $i$，2 为子树内选点的 lca 是 $i$ 。转移比较基础，不写了。

出来以后群里就有人说T3样例缩完点全是链，我看大样例范围这么大以为很强就没拍，，，有点哈人，幸亏没挂。

考场代码：

\/\/-O2 -std=c++14 -Wl,-stack=134217728 -Wall -Wextra -Wshadow
#include <bits\/stdc++.h>
#define pb push_back
#define eb emplace_back
#define lowbit(x) (x & -x)
#define mp make_pair
using namespace std;

typedef long long ll;
const int MAXN = 1e6+5;
const int Mod = 1e9+7;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
	while (c >= '0' && c <= '9') x =  x * 10 + (c - '0'), c = getchar();
	return x * f;
}

int n, m, pw2[MAXN * 2], ans;
int dfn[MAXN], low[MAXN], sd[MAXN];
int stk[MAXN], top, cnte[MAXN], cntc[MAXN];
ll t[3][3], f[MAXN][3];

struct edge {
	int u, v;
} E[MAXN];

vector<int> G[MAXN], T[MAXN];

void Tarjan(int x, int fa) {
	dfn[x] = low[x] = ++dfn[0];
	stk[++top] = x;
	for (auto to : G[x]) {
		if (!dfn[to]) {
			Tarjan(to, x);
			low[x] = min(low[x], low[to]);
		} else if (to != fa) low[x] = min(low[x], dfn[to]);
	}
	
	if (!fa || low[x] == dfn[x]) {
		sd[stk[top]] = x;
		cntc[x] = 1;
		while (stk[top--] != x) sd[stk[top]] = x, cntc[x]++;
	}
}

void dfs(int x, int fa) {
	f[x][0] = pw2[cnte[x]];
	f[x][2] = (pw2[cntc[x] + cnte[x]] - f[x][0] + Mod) % Mod;
	for (auto son : T[x]) {
		if (son == fa) continue;
		dfs(son, x);
		cnte[x] += cnte[son] + 1;
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				t[i][j] = f[x][i] * f[son][j] % Mod;

		f[x][0] = 2 * t[0][0] % Mod;
		f[x][1] = (2 * t[1][0] + t[0][1] + t[0][2]) % Mod;
		f[x][2] = (t[1][1] + t[1][2] + 2 * t[2][0] + t[2][1] + t[2][2]) % Mod;
	}
	
	ans = (ans + f[x][2] * pw2[m - cnte[x]]) % Mod;
}

int main() {
\/\/ 	freopen("barrack.in", "r", stdin);
\/\/ 	freopen("barrack.out", "w", stdout);
	n = read(), m = read();
	
	pw2[0] = 1;
	for (int i = 1; i <= n + m; i++) pw2[i] = (ll) pw2[i - 1] * 2 % Mod; 
	
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		E[i].u = u, E[i].v = v;
		G[u].pb(v), G[v].pb(u);
	}
	
	for (int i = 1; i <= n; i++)
		if (!dfn[i])
			Tarjan(i, 0);
	
	for (int i = 1; i <= m; i++) {
		int u = E[i].u, v = E[i].v;
		if (sd[u] == sd[v]) cnte[sd[u]]++;
		else T[sd[u]].pb(sd[v]), T[sd[v]].pb(sd[u]);
	}
	
	dfs(1, 0);
	
	printf("%d", ans);
	return 0;
}
\/*
4 4
1 2
2 3
3 1
1 4
*\/

T4.match

为什么不把这题放 T3 /fn/fn/fn

套路题。

看到对区间的所有子区间求和，一眼扫描线模型，还是维护最大值，更套路了，直接用单调栈维护，修改是区间覆盖，查询区间 $\sum A_iB_i$ 历史版本和，直接上线段树 $O(n \log n)$ 解决，缺点是 tag 有点多，常数稍大，听说有分治 $O(n \log^2 n)$ 的小常数做法，但是我不会/kk

关于维护历史版本信息的思路可以参考我写的博客线段树历史信息维护，不过感觉我写的也不是很明白嘛QAQ。

代码：

\/\/P8868 [NOIP2022] 比赛
#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef unsigned long long ll;
const int MAXN = 2.5e5+5;
const int Mod = 998244353;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int n, q, a[MAXN], b[MAXN];
int stka[MAXN], topa, stkb[MAXN], topb;
ll ans[MAXN];

vector<pair<int, int> > Q[MAXN];

struct node {
    int ca, cb, len, t;
    ll sum, sa, sb, hs, ha, hb, h;
} T[MAXN << 2];

#define ls (p << 1)
#define rs (p << 1 | 1)

inline void push_up(int p) {
    T[p].sa = T[ls].sa + T[rs].sa;
    T[p].sb = T[ls].sb + T[rs].sb;
    T[p].sum = T[ls].sum + T[rs].sum;
    T[p].hs = T[ls].hs + T[rs].hs;
}

inline void cova(int p, ll k) { T[p].sa = T[p].len * k, T[p].ca = k, T[p].sum = k * T[p].sb; }
inline void covb(int p, ll k) { T[p].sb = T[p].len * k, T[p].cb = k, T[p].sum = k * T[p].sa; }
inline void adda(int p, ll k) {
    T[p].hs += T[p].sb * k;
    if (!T[p].cb) T[p].ha += k;
    else T[p].h += k * T[p].cb;
}

inline void addb(int p, ll k) {
    T[p].hs += T[p].sa * k;
    if (!T[p].ca) T[p].hb += k;
    else T[p].h += k * T[p].ca;
}

inline void addh(int p, ll k) { T[p].hs += T[p].len * k, T[p].h += k; }
inline void addt(int p, ll k) {
    T[p].hs += T[p].sum * k;                                    
    if (!T[p].ca && !T[p].cb) T[p].t += k;
    else if (!T[p].cb) T[p].ha += T[p].ca * k;
    else if (!T[p].ca) T[p].hb += T[p].cb * k;
    else T[p].h += k * T[p].ca * T[p].cb;
}

inline void push_down(int p) {
    if (int &t = T[p].t) addt(ls, t), addt(rs, t), t = 0;
    if (ll &t = T[p].ha) adda(ls, t), adda(rs, t), t = 0;
    if (ll &t = T[p].hb) addb(ls, t), addb(rs, t), t = 0;
    if (ll &t = T[p].h) addh(ls, t), addh(rs, t), t = 0;
    if (int &t = T[p].ca) cova(ls, t), cova(rs, t), t = 0;
    if (int &t = T[p].cb) covb(ls, t), covb(rs, t), t = 0;
}

void build(int p, int l, int r) {
    T[p].len = r - l + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
}

void upd_a(int p, int l, int r, int gl, int gr, int k) {
    if (l >= gl && r <= gr) return cova(p, k);
    push_down(p);
    int mid = (l + r) >> 1;
    if (mid >= gl) upd_a(ls, l, mid, gl, gr, k);
    if (mid < gr) upd_a(rs, mid + 1, r, gl, gr, k);
    push_up(p);
}

void upd_b(int p, int l, int r, int gl, int gr, int k) {
    if (l >= gl && r <= gr) return covb(p, k);
    push_down(p);
    int mid = (l + r) >> 1;
    if (mid >= gl) upd_b(ls, l, mid, gl, gr, k);
    if (mid < gr) upd_b(rs, mid + 1, r, gl, gr, k);
    push_up(p);
}

ll qry(int p, int l, int r, int gl, int gr) {
    if (l >= gl && r <= gr) return T[p].hs;
    push_down(p);
    int mid = (l + r) >> 1; ll ret = 0;
    if (mid >= gl) ret = qry(ls, l, mid, gl, gr);
    if (mid < gr) ret += qry(rs, mid + 1, r, gl, gr);
    return ret;  
}

#undef ls
#undef rs

int main() {
    n = (read(), read());
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();

    q = read();
    for (int i = 1; i <= q; i++) {
        int l = read(), r = read();
        Q[r].eb(l, i);
    }

    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        while (topa && a[stka[topa]] < a[i]) topa--;
        while (topb && b[stkb[topb]] < b[i]) topb--;
        upd_a(1, 1, n, stka[topa] + 1, i, a[i]);
        upd_b(1, 1, n, stkb[topb] + 1, i, b[i]);
        stka[++topa] = stkb[++topb] = i;

        addt(1, 1);

        for (auto j : Q[i])
            ans[j.second] = qry(1, 1, n, j.first, i);
    }

    for (int i = 1; i <= q; i++) printf("%llu\n", ans[i]);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-01-06 23:20:43

洛谷传送门：Snowy Mountain

贡献一个 $O(n \log n)$ 解法。

初始可以用 BFS 求出每个点的高度 $h_u$。

接下来我们来考虑如何使得操作数最大化，这点其它题解讲的很明白，从点 $u$ 出发的答案即为 $2h_u-h_v$，其中 $v$ 是从 $u$ 出发能到达的高度最小的具有相同高度邻点的点。

考虑使用点分治计算每个点 $u$ 所对应的 $h_v$，设当前分治连通块的重心为 $x$，连通块大小为 $s$，先用 DFS $O(s)$ 计算出从 $x$ 出发到达连通块内每个点 $v$ 所需的最小初始动能，具体做法是维护变量 $sum$，高度下降则 $-1$，不变则 $+1$，到 $v$ 点时所需的最小动能即为过程中 $sum$ 的最大值。

使用同样的方法，我们也可以用第二遍 DFS 处理出从连通块内每个点 $u$ 是否可以到达 $x$，以及到达时的动能。此时在 $O(s \log s)$ 时间内处理每个连通块的方式就比较明朗了：将所有能够到达的、具有相同高度邻点的 $v$ 按照到达它所需的最小动能排序，然后按照 $h_v$ 做一个前缀min，在第二遍 DFS 到某个点 $u$ 时直接在这个有序序列上二分查找其所对应的最小的 $h_v$ 即可，因为是取min而不是求和，所以可以不用担心 $u$ 和 $v$ 来自同一棵子树的情况。

这样复杂度是 $O(n \log^2 n)$ 的，然后我们还有很好的一个性质没有用到：每次变量 $sum$ 只会 $+1$ 或 $-1$。

这意味着变量 $sum$ 的值是 $O(s)$ 的，这就允许我们可以不用排序，而是直接在值域上操作，这样处理单个分治连通块的复杂度就降到了 $O(s)$，总复杂度 $O(n \log n)$。

代码：

\/\/CF1654G Snowy Mountain
\/\/O(nlogn)解法
#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 2e5+5;
const int Mod = 998244353;

int n, h[N], ans[N];
int siz[N];
bool b[N], vis[N];

vector<int> T[N];
queue<int> Q;

void dfs_centre(int x, int fa, int sizz, int &c) {
    siz[x] = 1;
    int mx = 0;
    for (auto son : T[x]) {
        if (son == fa || vis[son]) continue;
        dfs_centre(son, x, sizz, c);
        siz[x] += siz[son];
        mx = max(mx, siz[son]);
    }
    if (mx <= sizz \/ 2 && siz[x] >= sizz \/ 2) c = x;
}

int L, R, mn[N * 2];

void dfs(int x, int fa, int mx, int sum, bool t) {
    mx = max(mx, t ? sum : -sum);
    if (t) {
        if (sum >= mx && sum + n >= L)
            ans[x] = min(ans[x], mn[min(R, sum + n)]);
    } else if (b[x]) {
        while (R < mx + n) mn[++R] = n;
        while (L > mx + n) mn[--L] = n;
        mn[mx + n] = min(mn[mx + n], h[x]);
    }

    for (auto son : T[x]) {
        if (son == fa || vis[son]) continue;
        if (h[son] == h[x]) dfs(son, x, mx, sum - 1, t);
        else if (t ^ (h[x] > h[son])) dfs(son, x, mx, sum + 1, t);
    }
}

inline void calc(int x) {
    L = R = mn[n] = n;
    dfs(x, x, 0, 0, 0);
    for (int i = L + 1; i <= R; i++) mn[i] = min(mn[i], mn[i - 1]);
    dfs(x, x, 0, 0, 1);
}

void solve(int x, int sizz) {
    dfs_centre(x, x, sizz, x);
    vis[x] = 1;
    calc(x);
    for (auto son : T[x]) {
        if (vis[son]) continue;
        solve(son, siz[son] > siz[x] ? sizz - siz[x] : siz[son]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        h[i] = -1;
        if (b[i]) {
            h[i] = 0;
            Q.push(i);
        }
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        T[u].pb(v), T[v].pb(u);
    }

    while (!Q.empty()) {
        int top = Q.front();
        Q.pop();
        for (auto v : T[top]) if (!~h[v]) {
            h[v] = h[top] + 1;
            Q.push(v);
        }
    }

    for (int i = 1; i <= n; i++) {
        ans[i] = h[i];
        b[i] = 0;
        for (auto j : T[i]) if (h[i] == h[j])
            { b[i] = 1; break; }
    }

    solve(1, n);

    for (int i = 1; i <= n; i++) printf("%d ", 2 * h[i] - ans[i]);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-01-09 19:36:45

传送门：G - Only Once

题意：

给定 $n$，对于一个长度为 $n$，值域为 $n$ 的序列 $A$，我们按如下方法构造无限序列 $B_i(1 \le i \le n)$：

• $B_{i,1} = i$
• $B_{i,j} = A_{B_{i,j-1}}(j > 1)$

记 $S_i$ 为 $B_i$ 中只出现了一次的元素的个数，定义序列 $A$ 的价值为 $\sum_{i=1}^n S_i$，现在请求出所有 $n^n$ 个可能的序列 $A$ 的价值之和对 $M$ 取模的结果。

$n \le 2 \times 10^5, 10^8 \le M \le 10^9$.

这是不同于官方题解的麻烦不知道多少倍的邪道解法。

对于任意 $1 \le i \le n$，我们从 $i$ 向 $A_i$ 连一条有向边，不难发现每个点有且仅有一条出边，整张图形成一个内向基环树森林（记为 $\mathcal{T}$）。

先来考虑怎样计算单个 $\mathcal{T}$ 的价值，观察序列 $B_i$ 的构造方式不难发现 $B_i$ 即为从点 $i$ 出发，沿着出边一直走下去经过的点形成的序列，$S_i$ 即为从点 $i$ 出发进入环之前经过的点的数量，$\sum_{i=1}^n S_i$ 就是每个不在环上的点被经过的次数，也即其子树大小，不妨简记为 $\sum_{i=1}^{n} siz_i$。

接下来就可以大力列式子了：

$$ \begin{aligned} &\sum_{\mathcal{T}}\sum_{i=1}^n siz_i \ = &\sum_{\mathcal{T}}\sum_{i=1}^n i\sum_{j=1}^{n} [siz_j=i] \ = &\sum_{i=1}^n i \sum_{\mathcal{T}}\sum_{j=1}^{n} [siz_j=i] \ = &\sum_{i=1}^n i \binom{n}{i} i^{i-1} (n-i)^{n-i+1} \end{aligned} $$

解释一下最后一步，$\binom{n}{i}$ 为选出来组成这个大小为 $i$ 的子树的点的方案数，$i^{i-1}$ 为该树的形态数，即为 $i$ 个点的有标号有根树的数量（证明见Prufer 序列），而剩下的点加上根节点这总共 $n-i+1$ 个点每个点都能向剩下的 $n-i$ 个点随意连边，所以最后要乘上 $(n-i)^{n-i+1}$。

如果模数是个大质数，那么这题已经做完了，但关键是模数可能为合数，导致 $n!$ 的逆元不存在，从而没法求 $\binom{n}{i}$。解决办法是借鉴扩展卢卡斯定理的思想，考虑将模数质因数分解成 $\sum p_i^{k_i}$，单独求出在模 $p_i^{k_i}$ 意义下的答案，最后使用中国剩余定理合并出答案，简单说一下如何在模 $p^k$ 意义下求 $\binom{n}{m}$：

$$ \begin{aligned} &\binom{n}{m} \ = &\dfrac{n!}{m!(n-m)!} \ = &\dfrac{\dfrac{n!}{p^x}}{\dfrac{m!}{p^y} \dfrac{(n-m)!}{p^z}} p^{x-y-z} \end{aligned} $$

其中 $x$ 是最大的满足 $p^x | n!$ 的整数，$y,z$ 同理，其实就是将分子和分母中的质因数 $p$ 单独拿出来算，这样分母就和模数互质，可以求逆元了，我们可以直接在 $O(n)$ 的时间内预处理出来 $\dfrac{i!}{p^{x_i}}(1 \le i \le n)$，总复杂度即为 $O(nt + n \log n)$，其中 $t$ 为模数的不同的质因数的数量，最大为 $9$，这不和官方做法复杂度一样吗。

代码：

\/\/邪道解法
#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 2e5+5;

int n, M, cnt, ans;
int num[10][N];
ll fac[10][N], ifac[10][N], ppow[10][101], c[10], tmp[N];

pair<int, int> fctr[10];

inline int qpow(int a, int b, int Mod) {
    ll base = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * base % Mod;
        base = base * base % Mod;
        b >>= 1;
    }
    return ans;
}

void init() {
    int t = M;
    for (int i = 2; i * i <= t; i++) if (t % i == 0) {
        fctr[++cnt] = mp(i, 1);
        ppow[cnt][0] = 1;
        int tt = 0;
        while (t % i == 0) ppow[cnt][++tt] = (fctr[cnt].second *= i), t \/= i;
    }
    if (t != 1) fctr[++cnt] = mp(t, t), ppow[cnt][0] = 1;

    for (int i = 1; i <= cnt; i++) {
        auto [p, pw] = fctr[i];
        c[i] = M \/ pw * qpow(M \/ pw, pw \/ p * (p - 1) - 1, pw);

        fac[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            tmp[j] = (j % p ? j : tmp[j \/ p]);
            fac[i][j] = fac[i][j - 1] * tmp[j] % pw;
            num[i][j] = num[i][j \/ p] + j \/ p;
        }

        ifac[i][n] = qpow(fac[i][n], pw \/ p * (p - 1) - 1, pw);
        for (int j = n; j; j--) ifac[i][j - 1] = ifac[i][j] * tmp[j] % pw;
    }
}

ll C(int n, int m) {
    ll ret = 0;
    for (int i = 1; i <= cnt; i++) {
        int pw = fctr[i].second;
        ll a = fac[i][n] * ifac[i][m] % pw * ifac[i][n - m] % pw * ppow[i][min(num[i][n] - num[i][m] - num[i][n - m], 100)] % pw;
        ret = (ret + c[i] * a) % M;
    }
    return ret;
}

int main() {
    scanf("%d%d", &n, &M);

    init();

    for (int i = 1; i < n; i++) ans = (ans + C(n, i) * qpow(i, i, M) % M * qpow(n - i, n - i + 1, M)) % M;

    printf("%d", ans);
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-13 21:05:55

P5283 [十二省联考 2019] 异或粽子 加强版。

step1

首先先将 $m$ 乘二，变成统计最大的 $m$ 个有序对。

把所有 $a_i$ 插入到一个 Trie 中，对于每个结点记录子树中叶子个数，第一步先来考虑求出第 $m$ 大值是什么，记第 $m$ 大值为 $lim$。

这个可以从高位到低位按位确定。假设当前考虑完了 $[30,b+1]$ 位，正在确定第 $b$ 位，对于 Trie 上第 $b+1$ 层的每一个结点 $i$，记录另一个结点 $cor_i$ 表示 $i$ 和 $cor_i$ 对应值的异或和的 $[30,b+1]$ 位等于 $lim$。这样就能对于第 $b$ 位统计出满足异或和 $[30,b+1]$ 位和 $lim$ 相等且第 $b$ 位为 $1$ 的点对数，从而确定 $lim$ 的第 $b$ 位是 $0$ 还是 $1$。

由于 Trie 上每个结点只会被遍历一遍，这部分复杂度是 $O(n \log V)$ 的。

step2

接下来考虑统计答案，这里只统计异或和小于 $lim$ 的点对贡献，等于 $lim$ 的贡献为 $lim*(m-cnt)$，$cnt$ 为异或和小于 $lim$ 的点对数。

枚举点对异或和和第 $m$ 大值二进制表示的 lcp。具体来讲，依然枚举 Trie 树上的一个点 $i$，贡献其实就是 $i$ 的子树 $t$ 以及 $cor_i$ 的子树 $t \oplus 1$ 中任意两对值的异或和，异或和没有很好的性质，只能拆位算，记 $s_{i,j,0/1}$ 表示 $i$ 的子树中第 $j$ 位为 $0/1$ 的值的个数，然后直接枚举每一位算贡献即可。

step3

最后来分析复杂度：

首先是 $s_{i,j,0/1}$ 的计算，如果点 $i$ 两个儿子都有，那么直接 $O(\log V)$ 暴力合并，否则 $s_{i}$ 可以直接继承其仅有的一个儿子的值（可以用指针实现），这样在三度点处的贡献是 $O(\log V)$ 的，在二度点处为 $O(1)$，由于叶子个数只有 $O(n)$ 个，所以三度点也只有 $O(n)$ 个，于是这部分是 $O(n \log V)$ 的。

然后是暴力拆位算贡献的部分，每一对 $(i,cor_i)$ 会造成 $O(\log V)$ 的贡献。如果 $i,cor_i$ 中有一个是三度点，注意到 $i$ 和 $cor_i$ 是一一对应的，所以这样的 $(i,cor_i)$ 只有 $O(n)$ 个；注意到如果 $i$ 和 $cor_i$ 中如果有一个是空子树，那么是不需要贡献 $O(\log V)$ 的，而如果 $i,cor_i$ 均为二度点且有 $O(\log V)$ 的贡献的话，那么是必然不会继续从 $i$ 递归到它的子树中的，所以对于每一个叶子，其祖先中的二度点至多有 $1$ 个会有贡献，因此这样的二度点总数也是 $O(n)$ 的，于是这部分复杂度也是 $O(n \log V)$ 的。

总复杂度 $O(n \log V)$。

代码（写的很丑QwQ）：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define rep for (int t = 2; t--; )
using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
	int x = 0; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;
}

typedef long long ll;
const int N = 5e4+5;
const int Mod = 1e9+7;

int n, a[N], tot = 1, ans;
ll m, lim;
int bf[N * 2][2][30], c, (*s[N * 30])[30];
int cor[N * 30];
vector<int> id[31];

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

struct node {
	int son[2], siz, d;
} T[N * 30];

#define son(p, s) T[p].son[s]

inline void ins(int v) {
	int p = 1;
	for (int i = 29; ~i; i--) {
		int g = v >> i & 1;
		if (son(p, g)) p = son(p, g);
		else p = son(p, g) = ++tot, T[p].d = i, id[i].pb(p);
		T[p].siz++;
	}
	if (T[p].siz == 1) s[p] = bf[c++];
}

int main() {
	n = read(), m = read() * 2ll; T[1].d = 30;
	for (int i = 1; i <= n; i++) ins(read());
	
	for (int i = tot; i; i--) {
		rep if (son(i, t)) s[son(i, t)][t][T[son(i, t)].d] += T[son(i, t)].siz;

		if (son(i, 0) && son(i, 1)) {
			s[i] = bf[c++];
			for (int k = T[i].d - 1; ~k; k--)
				rep s[i][t][k] = s[son(i, 0)][t][k] + s[son(i, 1)][t][k];
		} else if (son(i, 0) | son(i, 1)) s[i] = s[son(i, 0) | son(i, 1)];
	}

	id[30].pb(1); cor[1] = 1;
	for (int b = 29; ~b; b--) {
		ll cnt = 0;
		for (int i : id[b + 1]) if (cor[i])
			rep cnt += T[son(i, t)].siz * T[son(cor[i], t ^ 1)].siz;

		if (cnt >= m) {\/\/这一位为1
			lim |= 1 << b;
			for (int i : id[b + 1])
				rep cor[son(i, t)] = son(cor[i], t ^ 1);
		} else {\/\/这一位为0
			m -= cnt;
			for (int i : id[b + 1])
				rep {
					cor[son(i, t)] = son(cor[i], t);
					int x = son(cor[i], t ^ 1), y = son(i, t);
					if (x && y) {
						Add(ans, lim * T[x].siz * T[y].siz % Mod);
						for (int k = b; ~k; k--)
							rep Add(ans, (1ll << k) * s[x][t][k] * s[y][t ^ 1][k] % Mod);
					}
				}
		}
	}

	Add(ans, lim * m % Mod);

	printf("%lld", (ll) ans * (Mod + 1) \/ 2 % Mod);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-17 20:30:35

这是 CF1824B 枚举点计算贡献的 $O(n)$ 做法。

step1

称有人的结点为关键点。

实际上 $\min_u \sum_{i} dis(u,i)$ 的性质就是重心，即点 $u$ 是好的当且仅当以 $u$ 做为根时，每个子树中关键点的数量均 $\le \lfloor \dfrac{k}{2} \rfloor$，因为从这样的点向任意方向移动都只会使距离和不减。

step2

接下来的思路非常直接：枚举每个点 $u$，然后计算有多少关键点的分布方式使得 $u$ 满足 step1 中提到的性质。

直接算不太行，但是注意到关键点数 $> \lfloor \dfrac{k}{2} \rfloor$ 的子树至多有一个，所以可以考虑容斥，于是点 $u$ 的贡献有式子：

$$ \sum_{(u,v) \in E} \sum_{i = \lfloor \frac{k}{2} \rfloor + 1}^{k} \binom{siz_v}{i} \binom{n-siz_v}{k-i} $$

直接抄式子，能得到一个 $O(n^2)$ 做法。

step3

注意到 $\sum_{i = \lfloor \frac{k}{2} \rfloor + 1}^{k} \binom{siz_v}{i} \binom{n-siz_v}{k-i}$ 这整个式子只跟 $siz_v$ 有关系所欲我们不妨设：

$$ f_x = \sum_{i = \lfloor \frac{k}{2} \rfloor + 1}^{k} \binom{x}{i} \binom{n-x}{k-i} $$

可以考虑 $O(n)$ 递推出来 $f_{1 \dots n}$。具体来说，我们有：

$$ \begin{aligned} L &= \lfloor \frac{k}{2} \rfloor + 1\ f_{x+1} - f_{x} &= \sum_{i = L}^k \binom{x+1}{i}\binom{n-x-1}{k-i}-\binom{x}{i}\binom{n-x}{k-i}\ &= \sum_{i=L}^k \binom{x}{i-1}\binom{n-x-1}{k-i} + \binom{x}{i}\binom{n-x-1}{k-i} - \binom{x}{i}\binom{n-x}{k-i}\ &= \sum_{i=L-1}^{k-1} \binom{x}{i}\binom{n-x-1}{k-i-1}-\sum_{i=L}^{k-1} \binom{x}{i}\binom{n-x-1}{k-i-1}\ &= \binom{x}{\lfloor \frac{k}{2} \rfloor} \binom{n-x-1}{k - \lfloor \frac{k}{2} \rfloor - 1} \end{aligned} $$

于是我们就能 $O(n)$ 递推出 $f_{1 \dots n}$ 了，当然这个差分也可以考虑组合意义而不是暴力推：考虑 $f_{x+1}$ 比 $f_x$ 多的部分实际上就是前 $x+1$ 个点中恰好有 $\lfloor \frac{k}{2} \rfloor + 1$ 个关键点且第 $x+1$ 个点必为关键点的情况。

总复杂度 $O(n)$，所以这题实际上可以加强到带点权 $n \le 1 \times 10^7$。

代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long ll;
const int N = 2e5+5;
const int Mod = 1e9+7;

int n, k, siz[N];
int ans;
int f[N];

ll fac[N], ifac[N];

vector<int> T[N];

void dfs(int x, int fa) {
    siz[x] = 1;
    for (int son : T[x]) {
        if (son == fa) continue;
        dfs(son, x);
        siz[x] += siz[son];
    }
}

inline int qpow(int a, int b) {
    ll base = a, ans = 1;
    while (b) {
        if (b & 1) ans = ans * base % Mod;
        base = base * base % Mod;
        b >>= 1;
    }
    return ans;
}

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }
inline ll C(int n, int m) { return n >= m ? fac[n] * ifac[m] % Mod * ifac[n - m] % Mod : 0; }

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        T[u].pb(v);
        T[v].pb(u);
    }

    dfs(1, 0);

    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % Mod;
    ifac[n] = qpow(fac[n], Mod - 2);
    for (int i = n; i; i--) ifac[i - 1] = ifac[i] * i % Mod;

    for (int i = 1; i <= n; i++) {
        f[i] = (f[i - 1] + C(n - i, k - k \/ 2 - 1) * C(i - 1, k \/ 2)) % Mod;
    }

    for (int i = 1; i <= n; i++) {
        Add(ans, C(n, k));
        for (int son : T[i]) {
            int s = siz[son] < siz[i] ? siz[son] : n - siz[i];
            Add(ans, Mod - f[s]);
        }
    }

    printf("%lld", (ll) ans * qpow(C(n, k), Mod - 2) % Mod);
    return 0;
}