zqs`s blog

有朋自远方来，虽远必诛

莫队总结

发表于 更新于 分类于 Valine：

由于莫队是一种毒瘤的数据结构，而且最近一直在练莫队的扩展，所以就把练习的题目放到这里面。

还没更完，咕。

带修莫队

P1903 [国家集训队]数颜色 / 维护队列

小Z的袜子也是国家集训队，是不是国家集训队都喜欢出莫队板子啊（大雾

个人认为本文提到的莫队的三种扩展中最容易理解，代码最好写的。

对于每个询问除左右端点 $l,r$ 外记录一个 $t$ 表示这个询问之间有几次修改。

把每个询问按照左端点所在块号为第一关键字，右端点块号为第二关键字，$t$ 为第三关键字排序。

普通莫队的话询问 $[l,r]$ 可以转移到 $[l-1,r],[l,r-1],[l+1,r],[l,r+1]$，多了时间维 $t$ 可以转移到 $[l-1,r,t],[l,r-1,t],[l+1,r,t],[l,r+1,t],[l,r,t-1],[l,r,t+1]$。

按照时间轴撤销/进行修改操作。每次修改维护原数组，如果修改的点在当前区间内进行一次 add 和 del。

块长取 $O(n^{2/3})$ 可以做到 $O(n^{5/3})$ 的理论上不如暴力的效率（考虑常数，$n,m$ 同阶）。然而众所周知莫队肥肠玄学，所以就过了（

其实带修莫队相当于三维询问的莫队，对于 $k$ 维的询问，可以用类似的方法做到 $O(n^{2k-1/k})$ 的复杂度（这个复杂度很假，我们要相信莫队的玄学（大雾））。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cmath>
#include <algorithm>

int n, m, S, a[150005], ans[150005], Old[150005], New[150005];
int p[150005], cnt[1000005], b[150005], now, Q;
struct Quest {
	int l, r, t, id;
	inline bool operator < (const Quest a) const {
		int lb = (l - 1) / S, lb2 = (a.l - 1) / S, rb = (r - 1) / S, rb2 = (a.r - 1) / S;
		return lb == lb2 ? (rb == rb2 ? t < a.t : rb < rb2) : lb < lb2;
	}
} q[150005];
inline void add(int x) {if ((++ cnt[x]) == 1) ++ now;}
inline void del(int x) {if (!(-- cnt[x])) -- now;}

int main() {
	int l = 1, r = 0, t = 0;
	scanf("%d%d", &n, &m);
	S = pow(n, 2.0 / 3.0);
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i), b[i] = a[i];
	for (int i = 1, j = 0; i <= m; ++ i) {
		int l, r;
		char opt;
		scanf(" %c%d%d", &opt, &l, &r);
		if (opt == 'R') Old[++ j] = b[l], New[j] = r, b[l] = r, p[j] = l;p[j]记录第j次修改的位置
		else q[++ Q].l = l, q[Q].r = r, q[Q].t = j, q[Q].id = Q;
	}
	std::sort(q + 1, q + Q + 1);
	for (int i = 1; i <= Q; ++ i) {
		while (l > q[i].l) add(a[-- l]);
		while (r < q[i].r) add(a[++ r]);
		while (l < q[i].l) del(a[l ++]);
		while (r > q[i].r) del(a[r --]);
		while (t < q[i].t) {
			++ t;
			if (l <= p[t] && p[t] <= r) del(a[p[t]]), add(New[t]);//进行修改操作，考虑对答案的影响。
			a[p[t]] = New[t];
		}
		while (t > q[i].t) {
			if (l <= p[t] && p[t] <= r) del(a[p[t]]), add(Old[t]);//撤销修改。
			a[p[t]] = Old[t], -- t;
		}
		ans[q[i].id] = now;
	}
	for (int i = 1; i <= Q; ++ i) printf("%d\n", ans[i]);
	return 0;
}

树上莫队

SP10707 COT2 - Count on a tree II

其实这个世界上莫队本来上不了树，把树转成序列，莫队就上了树（雾

一个很自然的想法是把 $u\rightarrow v$ 的路径转为 $u\rightarrow lca,lca\rightarrow v$ 两条路径。

dfs 序尝试发现没救，我们考虑欧拉序，记一个点第一次在欧拉序出现的位置 $fst[u]$，第二次出现的位置 $lst[u]$。

我们默认 $fst[u]<fst[v]$。

分情况讨论：

  1. $u=lca$。那么这时候对应欧拉序 $[fst[u],fst[v]]$ 这一段区间只出现一次的点。
  2. $u\ne lca$。对应 $[lst[u],fst[v]]$ 这段区间内只出现一次的点。而 $lca$ 没有在这段区间出现，因此我们还要特判 $lca$。

至于为什么读者自证不难。

由于这题调的时候心态炸掉所以变量名有些儒雅随和（逃

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <cstdio> 
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>

int fst[100005], lst[100005], a[100005], c[200005], d[200005], S;
int cnt, Cnt[100005], Cnt2[100005], id, now, ans[100005], fa[100005][19], dep[100005];
int nmsl[100005];
std::map<int, int> mp;//离散化
struct Edge {
	int to, nxt;
} e[200005];
int head[100005], tot;
inline void AddEdge(int u, int v) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
}
struct Quest {
	int l, r, lca, id;
	inline bool operator < (const Quest x) {
		return (l - 1) / S == (x.l - 1) / S ? r < x.r : (l - 1) / S < (x.l - 1) / S;
	}
} q[100005];

void dfs(int u) {
	for (int i = 1; i <= 18; ++ i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	dep[u] = dep[fa[u][0]] + 1, fst[u] = ++ cnt, d[cnt] = u;
	int t;
	if (!mp.count(a[u])) t = mp[a[u]] = ++ id;
	else t = mp[a[u]];
	c[cnt] = nmsl[u] = t;//nmsl[u]记点u离散化后的值
	for (int i = head[u]; i; i = e[i].nxt)
		if (e[i].to != fa[u][0]) fa[e[i].to][0] = u, dfs(e[i].to);
	lst[u] = ++ cnt, d[cnt] = u, c[cnt] = t;
}
inline int query(int u, int v) {
	if (dep[u] < dep[v]) u ^= v ^= u ^= v;
	for (int i = 0; i <= 18; ++ i)
		if (dep[u] - dep[v] & 1 << i) u = fa[u][i];
	if (u == v) return u;
	for (int i = 18; i >= 0; -- i)
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
inline void shabi(int x) {
	Cnt2[d[x]] ^= 1;
	if (Cnt2[d[x]] && ++ Cnt[c[x]] == 1) ++ now;
	if (!Cnt2[d[x]] && !(-- Cnt[c[x]])) -- now;
}

int main() {
	int n, m, l = 1, r = 0;
	scanf("%d%d", &n, &m);
	S = 2 * n / sqrt(m);
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		AddEdge(u, v), AddEdge(v, u);
	}
	dfs(1);
	for (int i = 1; i <= m; ++ i) {
		int u, v, lca;
		scanf("%d%d", &u, &v);
		if (fst[u] > fst[v]) u ^= v ^= u ^= v;
		lca = query(u, v), q[i].id = i, q[i].lca = lca;
		if (lca == u) q[i].l = fst[u], q[i].r = fst[v];
		else q[i].l = lst[u], q[i].r = fst[v];
	}
	std::sort(q + 1, q + m + 1);
	for (int i = 1; i <= m; ++ i) {
		while (r < q[i].r) shabi(++ r);
		while (r > q[i].r) shabi(r --);
		while (l < q[i].l) shabi(l ++);
		while (l > q[i].l) shabi(-- l);
		ans[q[i].id] = now + (Cnt[nmsl[q[i].lca]] == 0);
	}
	for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
	return 0;
}

回滚莫队

一听名字就感觉它比前两种莫队高端，然而实际上它就是个不需要删除操作的莫队（没有 del 函数）。

AT1219 歴史の研究

加权区间众数是个经典的问题。如果用莫队解决删除操作似乎很麻烦（其实普通莫队可以做，但重点不在这里）。

回滚莫队就专门解决这种删除麻烦的情况。设一个块长 $S$。

对于询问区间长度小于 $S$ 的询问我们直接暴力。

对于询问区间长度大于 $S$ 的询问我们把他们按左端点所在块号为第一关键字，右端点为第二关键字排序。

然后一口气把左端点落在同一个块里的询问处理完。

如下图，假设我们处理了绿色区间的询问，下一个要处理的是红色区间（$p$ 代表这两个区间左端点所在块的右端点）。

1145141919810.png

右端点 $r$ 由于是排好序的直接向右添加即可，但左端点如果 $l[1]\ge l[2]$ 那还好，可 $l[1]<l[2]$ 就不可避免地要删除，怎么办？

这个时候回滚莫队说，直接把左端点 $l$ 从 $l[1]$ 移到 $p$，再把 $l$ 从 $p$ 移到 $l[2]$。

那把左端点从 $l[1]$ 移到 $p$ 还不是要删除？

但我们可以提前记录下 $[p,r[1]]$ 这段区间的答案 $lst$，然后直接删除数字即可，不需要修改答案。这样删除就是 $O(1)$ 的了。

然后调整 $l$ 到 $p$ 后再调整右端点，加入 $[r[1]+1,r[2]]$ 之间的元素，更新 $lst$ 为 $[p,r[2]$ 区间的答案。最后再移动左端点 $l$ 到 $l[2]$，得到当前询问的答案。

时间复杂度：若块长为 $S$，那么左端点移动就是 $O(mS)$ 的，右端点是 $O(n^2/S)$ 的，$S$ 取 $n\div \sqrt{m}$ 可以获得 $O(n\sqrt{m})$ 的优秀复杂度。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstring>
#define int long long

inline int max(const int x, const int y) {return x > y ? x : y;}
std::map<int, int> mp;
int a[100005], x[100005], ans[100005], cnt[100005], cnt2[100005], S, id, now;
struct Quest {
	int l, r, id;
	inline bool operator < (const Quest x) const {
		return (l - 1) / S == (x.l - 1) / S ? r < x.r : (l - 1) / S < (x.l - 1) / S;
	}
} q[100005];

signed main() {
	int n, m;
	scanf("%lld%lld", &n, &m);
	S = n / sqrt(m);
	for (int i = 1; i <= n; ++ i) scanf("%lld", x + i);
	for (int i = 1; i <= n; ++ i)
		if (!mp.count(x[i])) a[i] = mp[x[i]] = ++ id;
		else a[i] = mp[x[i]];
	for (int i = 1; i <= m; ++ i)
		scanf("%lld%lld", &q[i].l, &q[i].r), q[i].id = i;
	std::sort(q + 1, q + m + 1);
	for (int i = 1; i <= m;) {
		int blk = (q[i].l - 1) / S + 1, l = blk * S + 1, r = blk * S, lst = 0;
		memset(cnt, 0, sizeof cnt);
		for (; i <= m && blk == (q[i].l - 1) / S + 1; ++ i) {//一口气处理左端点在一个块里的询问
			if (q[i].r <= blk * S) {//直接暴力
				int now = 0;
				for (int k = q[i].l; k <= q[i].r; ++ k) cnt2[a[k]] = 0;
				for (int k = q[i].l; k <= q[i].r; ++ k)
					now = max(now, x[k] * (++ cnt2[a[k]]));
				ans[q[i].id] = now;
			} else {
				while (l <= blk * S) -- cnt[a[l ++]];//回滚左端点到p
				now = lst;
				while (r < q[i].r) ++ r, now = max(now, x[r] * (++ cnt[a[r]]));//调整右端点，更新lst
				lst = now;
				while (l > q[i].l) -- l, now = max(now, x[l] * (++ cnt[a[l]]));//调整左端点
				ans[q[i].id] = now;
			}
		}
	}
	for (int i = 1; i <= m; ++ i) printf("%lld\n", ans[i]);
	return 0;
}

BZOJ4358 permu

求 $[l,r]$ 区间最长连续段很容易想到用并查集。

具体的，若存在数字 $k$，则 $k,k+1$ 应在一个集合里。最终的答案就是节点数最多的集合的节点数减一。

但是现在问题来了：如果仍然上回滚莫队，我们如何撤销并查集的操作？

把那张图再放一遍：

1145141919810.png

我们想要撤销 $[l[1],p]$ 的并查集操作。

因此无法路径压缩，这里我选择启发式合并，按秩合并少一个 $\log$ 但代码长一些。

在加入 $[l[1],p]$ 中的元素合并并查集时，我们把每次把并查集中节点数小的那个集合合并到节点数大的那一个去。所以我们把这些节点数小的 push 到一个栈中，然后弹出栈顶依次撤销。

为什么要用一个栈而非队列？用队列会让某些节点的子节点数撤销后比原来大！

复杂度 $O(n\sqrt{m}\log n)$。由于并查集的玄学和常数极小&数据规模本来就小所以跑得飞快。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>

inline int max(const int x, const int y) {return x > y ? x : y;}
int fa[50005], a[50005], ans[50005], sze[50005], s[50005], top, n, m, S, now;
int fa2[50005], sz2[50005];
struct Quest {
	int l, r, id;
	inline bool operator < (const Quest a) const {
		return (l - 1) / S == (a.l - 1) / S ? r < a.r : (l - 1) / S < (a.l - 1) / S;
	}
} q[50005];
int find(int x) {return fa[x] == x ? x : find(fa[x]);}
inline void merge(int x, int y, bool flag = false) {
	x = find(x), y = find(y);
	if (x == y) return;
	if (sze[x] < sze[y]) x ^= y ^= x ^= y;
	fa[y] = x, now = max(now, (sze[x] += sze[y]) - 1);
	if (flag) s[++ top] = y;
}

int main() {
	scanf("%d%d", &n, &m);
	S = n / sqrt(m);
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i <= m; ++ i) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
	std::sort(q + 1, q + m + 1);
	for (int i = 1; i <= m;) {
		for (int j = 1; j <= n + 1; ++ j) fa[j] = j, sze[j] = 1;
		for (int j = 1; j <= n + 1; ++ j) fa2[j] = j, sz2[j] = 1;
		int blk = (q[i].l - 1) / S + 1, l = blk * S + 1, r = blk * S, lst = 0;
		top = 0;
		for (; (q[i].l - 1) / S + 1 == blk; ++ i) {
			if (q[i].r <= blk * S) {
				now = 0;
				for (int k = q[i].l; k <= q[i].r; ++ k) merge(a[k], a[k] + 1);
				ans[q[i].id] = now;
				for (int k = q[i].l; k <= q[i].r; ++ k)
					fa[a[k]] = a[k], sze[a[k]] = sze[a[k] + 1] = 1, fa[a[k] + 1] = a[k] + 1;
			} else {
				l = blk * S + 1;
				while (top) {
					sze[fa[s[top]]] -= sze[s[top]];
					fa[s[top]] = s[top];
					-- top;
				}
				now = lst;
				while (r < q[i].r) ++ r, merge(a[r], a[r] + 1);
				lst = now;
				while (l > q[i].l) -- l, merge(a[l], a[l] + 1, true);
				ans[q[i].id] = now;
			}
		}
	}
	for (int i = 1; i <= m; ++ i) printf("%d\n", ans[i]);
	return 0;
}

莫队综合

P4074 [WC2013] 糖果公园

树上带修莫队板子。写起来那是相当的恶心，而且我的代码uoj，校内oj，本地均AC，洛谷boom0很离谱。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <cstdio> 
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#define int long long

int fst[100005], lst[100005], a[100005], b[200005], pre[100005], S;
int cnt, Cnt[100005], Cnt2[100005], id, now, ans[100005], fa[100005][19], dep[100005];
int v[100005], w[100005], Old[200005], New[200005], p[100005];
int l = 1, r, t;
struct Edge {
	int to, nxt;
} e[200005];
int head[100005], tot;
inline void AddEdge(int u, int v) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
}
struct Quest {
	int l, r, lca, id, t;
	inline bool operator < (const Quest x) const {
		int lb = (l - 1) / S, lb2 = (x.l - 1) / S, rb = (r - 1) / S, rb2 = (x.r - 1) / S;
		return lb == lb2 ? (rb == rb2 ? t < x.t : rb < rb2) : lb < lb2;
	}
} q[100005];

void dfs(int u) {
	for (int i = 1; i <= 18; ++ i) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	dep[u] = dep[fa[u][0]] + 1, fst[u] = ++ cnt, b[cnt] = u;
	for (int i = head[u]; i; i = e[i].nxt)
		if (e[i].to != fa[u][0]) fa[e[i].to][0] = u, dfs(e[i].to);
	lst[u] = ++ cnt, b[cnt] = u;
}
int query(int u, int v) {
	if (dep[u] < dep[v]) u ^= v ^= u ^= v;
	for (int i = 0; i <= 18; ++ i)
		if (dep[u] - dep[v] & 1 << i) u = fa[u][i];
	if (u == v) return u;
	for (int i = 18; i >= 0; -- i)
		if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}
inline void add(int x) {
	int c = a[x];
	Cnt2[x] ^= 1;
	if (!Cnt2[x]) now -= v[c] * w[Cnt[c] --];
	if (Cnt2[x] && ++ Cnt[c] > 0) now += v[c] * w[Cnt[c]];
}
inline void del(int x) {
	int c = a[x];
	Cnt2[x] ^= 1;
	if (!Cnt2[x]) now -= v[c] * w[Cnt[c] --];
	if (Cnt2[x] && ++ Cnt[c] > 0) now += v[c] * w[Cnt[c]];
}
void modify(int p, int x) {
	if (Cnt2[p]) del(p), a[p] = x, add(p);
	a[p] = x;
}

signed main() {
	int n, m, Q, qt = 0;
	scanf("%lld%lld%lld", &n, &m, &Q);
	S = pow(n, 2.0 / 3.0) * sqrt(2);
	for (int i = 1; i <= m; ++ i) scanf("%lld", v + i);
	for (int i = 1; i <= n; ++ i) scanf("%lld", w + i);
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%lld%lld", &u, &v);
		AddEdge(u, v), AddEdge(v, u);
	}
	for (int i = 1; i <= n; ++ i) scanf("%lld", a + i), pre[i] = a[i];
	dfs(1);
	for (int i = 1, j = 0; i <= Q; ++ i) {
		int opt;
		scanf("%lld", &opt);
		if (opt == 1) {
			int u, v, lca;
			scanf("%lld%lld", &u, &v);
			if (fst[u] > fst[v]) u ^= v ^= u ^= v;
			lca = query(u, v), q[++ qt].id = qt, q[qt].t = j;
			if (lca == u) q[qt].l = fst[u], q[qt].r = fst[v];
			else q[qt].l = lst[u], q[qt].r = fst[v], q[qt].lca = lca;
		} else {
			int x, y;
			scanf("%lld%lld", &x, &y);
			Old[++ j] = pre[x], New[j] = pre[x] = y, p[j] = x;
		}
	}
	std::sort(q + 1, q + qt + 1);
	for (int i = 1; i <= qt; ++ i) {
		while (l > q[i].l) add(b[-- l]);
		while (r < q[i].r) add(b[++ r]);
		while (r > q[i].r) del(b[r --]);
		while (l < q[i].l) del(b[l ++]);
		while (t < q[i].t) ++ t, modify(p[t], New[t]);
		while (t > q[i].t) modify(p[t], Old[t]), t --;
		if (q[i].lca) ans[q[i].id] = v[a[q[i].lca]] * w[Cnt[a[q[i].lca]] + 1];
		ans[q[i].id] += now;
	}
	for (int i = 1; i <= qt; ++ i) printf("%lld\n", ans[i]);
	return 0;
}
-------------本文结束感谢您的阅读-------------