本文章由 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 从洛谷专栏拉取，原发布时间为 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 从洛谷专栏拉取，原发布时间为 2023-07-02 23:36:49

传送门： P9330

牛逼 dp。

step1 $(n \le 8)$：

首先真贪心是把区间按照右端点排序，然后从前到后能选就选。

我们考虑求答案的补，即计算假贪心能够求出正确答案的方案数，总方案数为 $1-2n$ 中所有奇数之积，所以当 $n \le 8$ 时直接 dfs 即可。

总方案数的证明考虑 $i$ 从 $1$ 至 $n$ 安排 $a_i,b_i$:

• 当安排 $a_i$ 时方案数为 $1$，只能安排最小的未被选过的数。
• 当安排 $b_i$ 时方案数为 $2n-2i+1$，可以安排任意一个未被选过的数。

step2 $(n \le 300)$：

将真贪心选中的区间称为红区间，假贪心选中的区间称为蓝区间，注意两种贪心可能选中同一个区间，不妨将这种区间称为紫区间，其它区间则为黑区间。

那么一组红区间应当满足的性质为：

• 相邻两个红区间无交。
• 两个相邻红区间的右端点之间不存在其它完整区间，特别的，第一个红区间的右端点之前不存在其它完整区间。

同时也容易证明当一组区间满足上述条件时，这组区间也一定是真贪心选出来的红区间。

同样可以得出蓝区间的性质：

• 相邻两个蓝区间无交。
• 前一个蓝区间的右端点和后一个蓝区间的左端点之间不存在其它区间的左端点，特别的，第一个蓝区间的左端点之前不存在其他区间的左端点。

和红区间一样，满足上述性质的一组区间也一定是假贪心选出的蓝区间。

我们再将红蓝区间放到一起观察，由于要求红蓝区间个数相等，所以我们将第 $i$ 个红区间与第 $i$ 个蓝区间配对，可以发现第 $i$ 个红区间的右端点一定大于第 $i-1$ 个蓝区间的右端点，小于等于第 $i$ 个蓝区间的右端点。

配合下图理解（截自日文题解）：

dp 的最重要一步来了：考虑按顺序每次插入一对红蓝区间。

具体来说，在 dp 状态中记录当前已经插入的区间个数 $i$，转移就考虑每次插入“一对新的红蓝区间以及所有右端点在当前最后一个红区间右端点和新插入的红区间右端点之间的黑区间”，所以我们需要枚举新插入的黑区间个数 $j$；同时我们还需要为这些新插入的黑区间右端点分配左端点，而左端点还有关于蓝区间的限制（见上文），所以还需要在状态中记录之前能插入一个左端点的位置数 $k$；同时还要添一维 $0/1$ 表示当前这对红蓝区间是不是紫区间。

转移细节就不展开写了，不是重点。

于是我们就得到了状态 $O(n^2)$，转移 $O(n)$ 的 $O(n^3)$ dp。

step3 $(n \le 3000)$：

按照插入区间的思路，转移感觉上就是不可避免地需要枚举插入的黑区间个数，所以我们考虑优化状态数。

观察上述的 $O(n^2)$ 状态的 dp，注意到需要多出来一维 $k$ 是因为左端点有较强的限制，但是右端点的限制较弱，于是我们就可以考虑去转换左右端点。

具体来说，我们考虑倒着插入每一对红蓝区间，枚举新插入的黑区间数量 $j$，同时为新插入的黑区间左端点分配右端点，这时就会发现右端点是可以插入到之前任意两个端点之间的！

于是我们可以设计 dp：$f_{i,0/1}$ 表示当前已经插入了 $i$ 个区间，当前这对红蓝区间是(1)否(0)是紫区间，根据 $0/1$ 不同一共有 $4$ 种转移式，这里具体展开一下 $0 \rightarrow 0$ 的转移式：

$$ f_{i+j+2,0} \leftarrow f_{i+j+2,0} + f_{i,0} \cdot (j+2)(j+1) \cdot (2i-2+(j-1))^{\underline{j}} $$

其中 $(2i-2+(j-1))^{\underline{j}}$ 为插入 $j$ 个黑区间右端点的方案数，$(j+2)(j+1)$ 为将共计 $j+3$ 个端点划分为 $3$ 段的方案数，配合下两图理解：

其它 $3$ 种转移大同小异，请自行画图理解。

于是我们得到了状态 $O(n)$，转移 $O(n)$ 的 $O(n^2)$ dp，同时也存在其它 $O(n^2)$ dp 方法，但大多由于为状态 $O(n^2)$，转移 $O(1)$ 而无法进一步优化。

$O(n^2)$ 核心代码：

f[1][0] = f[2][1] = 1;
	for (int i = 1; i < n; i++)
		for (int p = 0; p < 2; p++) if (f[i][p])
			for (int j = 0; i + j + 1 <= n; j++)
				for (int q = 0; i + j + 1 + q <= n && q < 2; q++) {
					ll t = f[i][p];
					if (q) t = t * (j + 1 + p) % Mod;
					if (p) t = t * (j + 1) % Mod;
					Add(f[i + j + 1 + q][q], t * fac[2 * i - 3 + !p + j] % Mod * ifac[2 * i - 3 + !p] % Mod);
				}

step4 $(n \le 20000)$：

其实 n 方卡卡常就能草过去。

依然以 $0 \rightarrow 0$ 的转移为例（其它大同小异），令 $j \leftarrow i+j+2$，重新化简一下转移式：

$$ \begin{aligned} f_{j,0} \leftarrow f_{j,0} &+f_{i,0} \cdot (j-i)(j-i-1) \cdot \dfrac{(j+i-5)!}{(2i-3)!}\ f_{j,0} \leftarrow f_{j,0} &+ \dfrac{f_{i,0}(i^2+i)}{(2i-3)!} \cdot (j+i-5)!\ &+ (j^2-j)\dfrac{f_{i,0}}{(2i-3)!}(j+i-5)!\ &- 2j\dfrac{f_{i,0}i}{(2i-3)!}(j+i-5)! \end{aligned} $$

式子中只有和 $i,j,i+j$ 有关的项，所以这实际上就是半在线减法卷积，使用分治法解决即可。

注意到是任意模数，写 NTT 巨烦，可以考虑用 Karatsuba 乘法代替。

使用 NTT 或 Karatsuba 乘法即可得到 $O(n \log^2 n)$ 或 $O(n^{1.59})$ 的复杂度。

细节较多，注意代码实现。

代码（使用 Karatsuba 乘法）：

#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;
typedef vector<int> poly;
const int N = 4e4+5;

struct FastMod {
    ll p, m;
    FastMod(ll pp): p(pp), m((1ll << 62) \/ pp) { }
    ll operator ()(ll x) {
        ll r = x - p * ((__int128) x * m >> 62);
        return r >= p ? r - p : r;
    }
} F(2);

int n, Mod, ans = 1;
int f[N][2];
ll Bfac[N], Bifac[N], *fac = Bfac + 2, *ifac = Bifac + 2;

inline ll 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 void Add(ll &a, int b) { a += b; if (a >= Mod) a -= Mod; }

ll A[N], B[N], C[N], r0[15][N], r1[15][N], r2[15][N], x[15][N], y[15][N];

inline int mul(int d, ll *a, ll *b, int n, ll *g) {
    if (!n) return 0;
    for (int i = 0; i < 2 * n - 1; i++) g[i] = 0;
    \/\/ if (1) {
    if (n <= 16) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i + j] = F(g[i + j] + a[i] * b[j]);
        return 2 * n - 1;
    }
    int mid = (n + 1) \/ 2;
    int l0 = mul(d + 1, a, b, mid, r0[d]);
    int l1 = mul(d + 1, a + mid, b + mid, n - mid, r1[d]);
    for (int i = 0; i < l0; i++) Add(g[i + mid], Mod - r0[d][i]), Add(g[i], r0[d][i]);
    for (int i = 0; i < l1; i++) Add(g[i + mid], Mod - r1[d][i]), Add(g[i + 2 * mid], r1[d][i]);

    for (int i = 0; i < mid; i++) {
        x[d][i] = a[i], y[d][i] = b[i];
        if (mid + i < n) Add(x[d][i], a[mid + i]), Add(y[d][i], b[mid + i]);
    }
    int l2 = mul(d + 1, x[d], y[d], mid, r2[d]);

    for (int i = 0; i < l2; i++) Add(g[i + mid], r2[d][i]);

    return 2 * n - 1;
}

inline ll c0(int p, int q, ll j) { return F(p * q * j * j + (p + q - p * q) * j); }
inline ll c1(int p, int q, ll i) { return F(p * q * i * i + (p * q - p - q) * i + (1 - p) * (1 - q) + Mod); }

void solve(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	solve(l, mid);
	for (int p = 0; p < 2; p++)
		for (int q = 0; q < 2; q++) {
			for (int i = 0; i < r - l; i++) B[i] = fac[mid - 2 + l - q + i - p], A[i] = 0;
			if (p * q || (p + q - p * q)) {
				for (int i = l; i <= mid; i++) A[mid - i] = F(f[i][p] * ifac[2 * i - 2 - p]);
				mul(0, A, B, r - l, C);
				for (int i = mid - l; i <= r - l - 1; i++) {
					int j = i + 1 + l - q;
                    f[j + q][q] = F(f[j + q][q] + c0(p, q, j) * C[i]);
				}
			}

			if (p * q || (p * q - p - q) || (1 - p) * (1 - q)) {
				for (int i = l; i <= mid; i++) A[mid - i] = F(F(f[i][p] * ifac[2 * i - 2 - p]) * c1(p, q, i));
				mul(0, A, B, r - l, C);
				for (int i = mid - l; i <= r - l - 1; i++) Add(f[i + 1 + l][q], C[i]);
			}

			if (p * q) {
				for (int i = l; i <= mid; i++) A[mid - i] = F(F(f[i][p] * ifac[2 * i - 2 - p]) * i);
				mul(0, A, B, r - l, C);
				for (int i = mid - l; i <= r - l - 1; i++) {
					int j = i + 1 + l - q;
					Add(f[j + q][q], Mod - F(C[i] * 2 * j));
				}
			}
		}
	solve(mid + 1, r);
}

int main() {
	scanf("%d%d", &n, &Mod); F = FastMod(Mod);

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

	f[1][0] = f[2][1] = 1;
	solve(1, n);

	for (int i = 3; i <= 2 * n; i += 2) ans = (ll) ans * i % Mod;
	for (int i = 1; i <= n; i++)
		for (int p = 0; p < 2; p++) {
			ll t = f[i][p];
			if (p) t = t * (n - i + 1) % Mod;
			Add(ans, Mod - t * fac[n + i - 3 + !p] % Mod * ifac[2 * i - 3 + !p] % Mod);
		}

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

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

题目大意：

给定序列 $a_{1, \dots, n}$，定义 $S_{l,r}$ 为 $a_{l,\dots,r}$ 的中位数集合（大小为 $1$ 或 $2$），$w_{l,r,x} = \sum_{i=l}^r [a_i=x]$，求 $\max_{1 \le l \le r \le n} \max_{x \in S_{l,r}} w(l,r,x)$。

$n \le 5 \times 10^5$。

小清新数据结构。

容易想到枚举中位数的值，设为 $x$，将序列中 $<x$ 的位置赋为 $0$，$>x$ 的位置赋为 $1$，目标即为计算所有 $x$ 是中位数的区间中 $x$ 的最大出现次数。

step1

先来考虑 $x \in S_{l,r}$ 的等价条件是什么，设区间中 $x$ 的出现次数为 $c$，$0$ 的出现次数为 $c_0$，$1$ 的出现次数为 $c_1$，不难得到：

$$ \begin{aligned} &x \in S_{l,r}\

\Leftrightarrow &\begin{cases} c+c_0 \ge c_1\ c+c_1 \ge c_0\ \end{cases}\

\Leftrightarrow &\max(c_1-c_0-c,c_0-c_1-c) \le 0

\end{aligned} $$

设 $u_{i} = w(1,i,1)-w(1,i,0)-w(1,i,x)$，$v_i = w(1,i,0)-w(1,i,1)-w(1,i,x)$，那么 $x \in S_{l,r}$ 当且仅当 $\max(u_r-u_{l-1}, v_r - v_{l-1}) \le 0$，将 $p_i=(u_i, v_i)$ 看作二维平面上的一个点，这个条件实际上就是在说 $p_r$ 在 $p_{l-1}$ 的左下方。

step2

现在再来观察 $p_{i-1}$ 和 $p_i$ 之间的位置关系。如果 $a_i = x$，那么 $p_{i}$ 是 $p_{i-1}$ 向左下走一步；如果 $a_i = 0$，那么是向左上走一步；如果 $a_i=1$，那么是向右下走一步。画出来会像下图：

画出来就能一眼看出这张图的特点：由若干条（准确来说是 $w(1,n,x)+1$ 条）斜率为 $-1$ 的线段以及连接它们的斜率为 $1$ 的线段组成。现在我们的目标就变成了找到相距最远的两条斜率为 $-1$ 线段（距离定义为从一条走到另一条需要向左下走的次数），满足能够从其上面分别找出一个点满足一个在另一个的左下方。

考虑能够找出这样两个点的等价条件是什么，不妨来看上图中的线段 BC 和 DE，画一下图就能得出条件：

$$ \begin{cases} C_x \ge D_x\ B_y \ge E_y\ \end{cases} $$

二维数点的形式。使用 BIT，支持单点修改，后缀 $\min$ 即可；第 $i$ 条斜率为 $-1$ 的线段实际上就是点 $x$ 的第 $i-1$ 次出现位置到第 $i$ 次出现位置之间的所有位置对应的点的集合，所以线段端点的横纵坐标只需要使用线段树，支持区间加，区间 $\max \And \min$ 即可。

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

代码：

\/\/#include "sequence.h"
#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 = 5e5+5;
const int Mod = 998244353;
const int INF = 0x3f3f3f3f;

int n, a[N], ans;
vector<int> pos[N];

struct segT {
    struct node {
        int mx, mn, ad;
    } T[N << 2];

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

    inline void push_up(int p) {
        T[p].mx = max(T[ls].mx, T[rs].mx) + T[p].ad;
        T[p].mn = min(T[ls].mn, T[rs].mn) + T[p].ad;
    }

    void upd(int p, int l, int r, int gl, int gr, int k) {
        if (l >= gl && r <= gr) {
            T[p].mx += k, T[p].mn += k;
            T[p].ad += k;
            return;
        }
        int mid = (l + r) >> 1;
        if (mid >= gl) upd(ls, l, mid, gl, gr, k);
        if (mid < gr) upd(rs, mid + 1, r, gl, gr, k);
        push_up(p);
    }

    int qry_mn(int p, int l, int r, int gl, int gr) {
        if (l >= gl && r <= gr) return T[p].mn;
        int mid = (l + r) >> 1, ret = INF;
        if (mid >= gl) ret = qry_mn(ls, l, mid, gl, gr);
        if (mid < gr) ret = min(ret, qry_mn(rs, mid + 1, r, gl, gr));
        return ret + T[p].ad;
    }

    int qry_mx(int p, int l, int r, int gl, int gr) {
        if (l >= gl && r <= gr) return T[p].mx;
        int mid = (l + r) >> 1, ret = -INF;
        if (mid >= gl) ret = qry_mx(ls, l, mid, gl, gr);
        if (mid < gr) ret = max(ret, qry_mx(rs, mid + 1, r, gl, gr));
        return ret + T[p].ad;
    }

    #undef ls
    #undef rs
} Tx, Ty;

int cnt;

struct opt {
    int op, x, y, k;\/\/0询问，1修改
} P[N * 2];

struct Hsh {
    int v[N * 2], c;
    int operator [](int x) { return v[x]; }
    inline void ins(int x) { v[++c] = x; }
    inline void init() {
        sort(v + 1, v + c + 1);
        c = unique(v + 1, v + c + 1) - v - 1;
    }
    inline int f(int x) { return lower_bound(v + 1, v + c + 1, x) - v; }
} H;

struct BIT {
    int T[N * 2];
    inline void upd(int x, int k) { for (; x; x -= lowbit(x)) T[x] = min(T[x], k); }
    inline int qry(int x) { int ret = INF; for (; x <= H.c; x += lowbit(x)) ret = min(ret, T[x]); return ret; }
    inline void clr(int x) { for (; x; x -= lowbit(x)) T[x] = INF; }
} T;

inline void work() {\/\/二维数点
    sort(P + 1, P + cnt + 1, [](opt a, opt b) { return a.x == b.x ? a.op > b.op : a.x > b.x; });

    H.c = 0;
    for (int i = 1; i <= cnt; i++) H.ins(P[i].y);
    H.init();

    for (int i = 1; i <= cnt; i++) {
        P[i].y = H.f(P[i].y);
        if (P[i].op == 1) T.upd(P[i].y, P[i].k);
        else ans = max(ans, P[i].k - T.qry(P[i].y));
    }
    for (int i = 1; i <= cnt; i++) T.clr(P[i].y);
}

int sequence(int N, std::vector<int> A) {
	n = N;
	for (int i = 1; i <= n; i++) pos[A[i - 1]].pb(i);
	
	memset(T.T, 0x3f, sizeof(T.T));
    for (int i = 1; i <= n; i++) Tx.upd(1, 0, n, i, i, i), Ty.upd(1, 0, n, i, i, -i);
    for (int i = 1; i <= n; i++) if (!pos[i].empty()) {
        for (int j : pos[i])\/\/from c1 to c
            Tx.upd(1, 0, n, j, n, -2);

        cnt = 0;
        pos[i].pb(n + 1);
        int k = pos[i].size(), lst = 0;
        for (int j = 0; j < k; j++) {
            int cur = pos[i][j];
            int mn_x = Tx.qry_mn(1, 0, n, lst, cur - 1), mn_y = Ty.qry_mn(1, 0, n, lst, cur - 1);
            int mx_x = Tx.qry_mx(1, 0, n, lst, cur - 1), mx_y = Ty.qry_mx(1, 0, n, lst, cur - 1);
            P[++cnt] = (opt) { 1, mx_x, mx_y, j };
            P[++cnt] = (opt) { 0, mn_x, mn_y, j };
            lst = cur;
        }

        work();

        pos[i].pop_back();
        for (int j : pos[i])\/\/from c to c0
            Ty.upd(1, 0, n, j, n, 2);
    }
    
    return ans;
}

\/\/int main() {
\/\/    int n;
\/\/    vector<int> A;
\/\/	scanf("%d", &n); A.resize(n);
\/\/	for (int i = 0; i < n; i++) scanf("%d", &A[i]);
\/\/	
\/\/	printf("%d", sequence(n, A));
\/\/    return 0;
\/\/}

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

传送门：P9340

题目大意：

给定一棵 $n$ 个点的树以及一个序列 $a_{1,\dots,m}$，$q$ 次询问包含 $a_{l,\dots,r}$ 中所有点的最小连通块大小。

回滚莫队一点也不优美，所以这里是 $O(n \log^2 n)$ 解法。

step1

不妨将树的根定为 $1$ 号结点。

不难看出题目就是求区间所有点构成的虚树大小，将在区间 $[l,r]$ 中出现过的点染黑，其它点染白，可以将虚树大小转化成两部分：

1. 加上所有点 $u$ 的个数，满足 $u$ 的子树中存在至少一个黑点
2. 减去所有点 $u$ 的个数，满足 $u$ 的子树之外（包括 $u$）全部为白点

第二部分实际上就是虚树的根的深度，这是好算的，虚树的根就是区间 $[l,r]$ 中 dfn 最小的结点和 dfn 最大的结点的 lca。

step2

难点在于第一部分。

现在来分析右端点固定为 $r$ 时，对于一个结点 $u$，左端点 $l$ 取到何值会让 $u$ 对第一部分有贡献。记 $mx_u$ 表示 $u$ 的子树中在前缀 $[1,r]$ 中最后一次出现时间最大的点的最后一次出现位置，容易发现当 $l \in [1,mx_u]$ 时，$u$ 子树中的点 $a_{mx_u}$ 必然为黑点，当 $l \in [mx_u + 1, r]$ 时，$u$ 子树中必然不存在黑点；所以 $u$ 会且仅会对区间 $[1,mx_u]$ 有 $+1$ 的贡献。

考虑扫描线：枚举 $r$，动态维护 $mx_u$ 以及所有左端点的答案，初始有 $mx_u = 0$。观察从 $r-1$ 枚举到 $r$ 时 $a_r$ 会对 $mx_u$ 造成什么影响：就是将 $a_r$ 到 $1$ 的路径上的所有点的 $mx_u$ 赋值为 $i$ 。这很容易联想到 LCT 的 access 操作，也就是说，如果暴力对于从 $a_r$ 到 $1$ 的路径上的 $mx_u$ 相同的连续段分别修改的话，根据 access 的复杂度分析，这是均摊单次 $O(\log n)$ 的（可以看作每次操作都是在 $O(\log n)$ 条重链上做颜色段均摊）。而在整条链 $mx_u$ 相同的情况下，我们只需要知道这条链的点数即可用 BIT 快速修改。

这个过程用 LCT 即可非常方便地模拟，总复杂度 $O(n \log^2 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;

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 = 1e5+5;

int n, m, q, c[N], ans[N];
int siz[N], dep[N], hs[N], f[N];
int ct[N], dfn[N], nfd[N];
int mn[N][17], mx[N][17], lg2[N];

vector<int> T[N];
vector<pair<int, int> > Q[N];

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

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

inline int LCA(int x, int y) {
	while (ct[x] != ct[y]) {
		if (dep[ct[x]] < dep[ct[y]]) swap(x, y);
		x = f[ct[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

int BIT[N];
inline void upd(int x, int k) { for (; x <= m; x += lowbit(x)) BIT[x] += k; }
inline void upd(int l, int r, int k) { upd(l, k), upd(r + 1, -k); }
inline int qry(int x) { int ret = 0; for (; x; x -= lowbit(x)) ret += BIT[x]; return ret; } 

namespace LCT {
	struct node {
		int son[2], fa;
		int cov, col;
	} T[N];

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

	inline void cov(int x, int k) { if (x) T[x].cov = T[x].col = k; }
	inline void push_down(int x) { if (int &t = T[x].cov) cov(son(x, 0), t), cov(son(x, 1), t), t = 0; }
	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 bool isRt(int x) { return son(f(x), 0) != x && son(f(x), 1) != x; }

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

	int stk[N], top;

	inline void splay(int x) {
		int y = x;
		stk[top = 1] = y;
		while (!isRt(y)) stk[++top] = y = f(y);
		while (top) push_down(stk[top--]);
		for (y = f(x); !isRt(x); rotate(x), y = f(x))
			if (!isRt(y))
				rotate(get_son(x) == get_son(y) ? y : x);
	}

	inline void access(int x, int t) {
		int y = 0;
		for (; x; x = f(y = x)) {
			if (y) upd(T[y].col + 1, t, dep[y] - dep[x]);
			splay(x), son(x, 1) = y;
		}
		upd(T[y].col + 1, t, dep[y]);
		cov(y, t);
	}

	#undef son
	#undef f
}

int main() {
	n = read(), m = read(), q = read();
	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);
	for (int i = 2; i <= n; i++) LCT::T[i].fa = f[i];
	
	lg2[0] = -1;
	for (int i = 1; i <= m; i++) {
		c[i] = read();
		lg2[i] = lg2[i >> 1] + 1;
		mn[i][0] = mx[i][0] = dfn[c[i]];
		for (int j = 1; j <= lg2[i]; j++) {
			mn[i][j] = min(mn[i][j - 1], mn[i - (1 << j - 1)][j - 1]);
			mx[i][j] = max(mx[i][j - 1], mx[i - (1 << j - 1)][j - 1]);
		}
	}

	for (int i = 1; i <= q; i++) {
		int l = read(), r = read();
		Q[r].eb(l, i);
	}
	
	for (int i = 1; i <= m; i++) {
		LCT::access(c[i], i);
		for (auto j : Q[i]) {
			int L = j.first, R = i, len = lg2[R - L + 1];
			ans[j.second] = qry(L);
			int mnd = min(mn[R][len], mn[L + (1 << len) - 1][len]);
			int mxd = max(mx[R][len], mx[L + (1 << len) - 1][len]);
			ans[j.second] -= dep[LCA(nfd[mnd], nfd[mxd])] - 1;
		}
	}

	for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
	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;
}

本文章由 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-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-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 从洛谷专栏拉取，原发布时间为 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;
}