我说你啊……能不能对自己好一点？不会爱自己的人也没办法爱别人的哦！——《工作细胞》

你看这一个个细胞多像分块，这一个个分块多像兔子。

所以细胞是兔子。

莫队

莫队，是莫涛发明的一种解决区间查询等问题的离线算法，基于分块思想，复杂度为 ，但是只支持单点修改。

普通莫队

好事善人做。

一般来说，如果可以在 内从 的答案转移到 、 、 、 这四个与之相邻的区间的答案，则可以使用莫队，可以来看看这道题目：

给出一个序列和若干个查询区间 ，问 中有多少个不同的数。

这道题可以用树状数组和块状数组来做，但是用莫队会比较简单（况且我们今天的主题是莫队）。

好，那么我们广告之后，精彩继续。

转移

欢迎回来，相信很多观众刚刚打开博客，让我们回到莫队。

书接上回，我们要把一个区间的答案转移到与之相邻的区间中去，所以要用一个 来记录每个数出现的次数， 表示当前区间的答案，比如：

转移！

那么我们转移到紧邻的区间，例如转移到 ：

转！

可以看到 ，说明添加了一个没出现过的数，所以 变成 ，但是如果这里再向右转移：

看啥呢，转走了这还能有吗

这里 不为 ，所以虽然 ，但是 却不再增长。

其他的转移都是类似的。容易发现，转移分为两种情况，在区间里添数，或者在区间里删数： 

1
2
3
4
5
6
7
8
9
10
11
12
inline void add (int p) // 加数 
{
	if (Cnt[a[p]] == 0) // 如果原本未出现过  
		cur ++; // 贡献 + 1 
	Cnt[a[p]] ++; // 同时计数  
}
inline void del (int p) // 删数 
{
	Cnt[a[p]] --; // 先计数  
	if (Cnt[a[p]] == 0) // 再判 
		cur --;
}

那么从任意的一个区间转移到另一个区间，只需要这么写：

1
2
3
4
5
6
7
8
while (l > q[i].l)
	add (-- l);
while (l < q[i].l)
	add (l ++);
while (r < q[i].r)
	add (++ r);
while (r > q[i].r)
	del (r --);

注意 和 的位置。删数是先删后移，加数是先移后添。初始化时，令 。

现在我们可以从一个区间的答案转移到另一个区间了，但是如果直接在线查询，很有可能在序列两头使用秘技”反复横跳“，结果还劣于 的算法了。但是我们可以把查询离线下来，然后排个序。

排序

当然我们这边讲的排序不是平时的排序。

要说起平时的排序，那是：

快速排序，归并排序，选择排序，插入排序，冒泡排序，带桶的，带基数的，带计数的，带二叉树的，带鸡尾酒的，带最小增量的。

梳排序、圈排序、侏儒排序、珠排序、块排序、相邻图、鸽巢、闪电、内省、奇偶、臭皮匠排序、插值、爆炸、拓扑排序、平滑白肚儿、清蒸图书馆、鸭子锦标赛、原地合并、梯级归并、美国旗、弱堆排、煎饼、意粉、伸展、耐心、清蒸笛卡尔、震荡排、多相排、两两排、双调排序器。

见到这些排序，机房上将命难逃，背堆带桶逞英豪，威风凛凛杀气高，要问此排名和姓，姓分名块字莫涛，莫队的英明它四海飘！

三 个 贯 口 走 上 岸。

好好好不玩了，我们很容易想到以 为第一关键词， 为第二关键词排序，但这样做效果并不好。使用分块，那好得不是一点点啊。然后按照 为第一关键词，以 为第二关键词排序。这样这个算法的时间复杂度可以降到 。

但在此之上，我们还可以进行常数优化，奇偶化排序。如果 如果是奇数，则将 顺序排序，否则将 逆序排序。

一般的排序，指针的动向可能是这样的：

老好用了

我们看到，每次 跨过一个块， 都必须往左移很长一截。

而奇偶化排序后，指针的动向会变成这样：

征求下次贯口素材

可以发现，如果 在偶数块， 指针会在返回的“途中”，就解决问题。

给出代码：

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
int sq;
struct Query {
	int l, r, id;
	bool operator < (const Query &o) const
	{
		if (l / sq != o.l / sq)
			return l < o.l;
		if (l / sq & 1)
			return r < o.r;
		return r > o.r;
	}
} q[N];

int a[N], ans[N], cnt[N], cur, l = 1, r = 0;

inline void add (int p)
{
	if (cnt[a[p]] == 0)
		cur ++;
	cnt[a[p]] ++;
}

inline void del (int p)
{
	cnt[a[p]] --;
	if (cnt[a[p]] == 0)
		cur --;
}

int main ()
{
	scanf ("%d", &n);
	sq = sqrt (n);
	for (int i = 1; i <= n; i ++)
		scanf ("%d", &a[i]);
	scanf ("%d", &m);
	for (int i = 0; i < m; i ++)
	{
		scanf ("%d %d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort (q, q + m);
	for (int i = 0; i < m; i ++)
	{
		while (l > q[i].l)
			add (-- l);
		while (r < q[i].r)
			add (++ r);
		while (l < q[i].l)
			del (l ++);
		while (r > q[i].r)
			del (r --);
		ans[q[i].id] = cur;
	}
}

只要数据可离线（有些题目会强制在线，就不能用这个方法了），且可以在 内实现转移，就可以用这个方法，有时只需要改亿改 和 函数即可。

带修改莫队

从这跳下去。

普通莫队是不能带修改的，但是我们可以强行让它修改，就像 一样，可以强行加上一维时间维，表示这次操作的时间。

那我们的状态就变成了 、 、 、 、 、 。

每次回答询问的时候，先从上一个询问的时间跳转到当前询问的时间，如果当前询问的时间更靠后，则顺序执行所有修改，直到达到当前询问时间；如果当前询问的时间更靠前，则回到之前，还原所有多余的修改。

模板代码老长了：

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
103
104
105
struct Query {
	int l, r, id, t;
	bool operator < (const Query &o) const
	{
		if (bel[l] != bel[o.l])
			return l < o.l;
		if (bel[r] != bel[o.r])
			return r < o.r;
		return id < o.id;
	}
} q[N];

inline void change_add (int cur) // 增加修改，在 cur 的位置  
{
	if (pos[cur] >= pl && pos[cur] <= pr)
	{
		cnt[a[pos[cur]]] --;
		if (!cnt[a[pos[cur]]])
			res --;
	}
	pre[cur] = a[pos[cur]]; // 如果正确，记录前驱  
	a[pos[cur]] = val[cur];
	if (pos[cur] >= pl && pos[cur] <= pr)
	{
		if (!cnt[a[pos[cur]]])
			res ++;
		cnt[a[pos[cur]]] ++;
	}
}

inline void change_del (int cur) // 取消曾经修改，在 cur 的位置 
{
	if (pos[cur] >= pl && pos[cur] <= pr)
	{
		cnt[a[pos[cur]]] --;
		if (!cnt[a[pos[cur]]])
			res --;
	}
	a[pos[cur]] = pre[cur]; // 如果是回退的，转移  
	if (pos[cur] >= pl && pos[cur] <= pr)
	{
		if (!cnt[a[pos[cur]]])
			res ++;
		cnt[a[pos[cur]]] ++;
	}
}

inline void change (int now)
{
	while (cur < idxC && tim[cur + 1] <= now) // 如果比之前大，按正常修改 
		change_add (++ cur);
	while (cur && tim[cur] > now) // 如果发现比前驱小，回退  
		change_del (cur --);
}

inline void add (int p)
{
	if (!cnt[a[p]])
		res ++;
	cnt[a[p]] ++;
}

inline void del (int p)
{
	cnt[a[p]] --;
	if (!cnt[a[p]])
		res --;
}

int main ()
{
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++)
		scanf ("%d", &a[i]);
	for (int i = 1; i <= m; i ++)
	{
		scanf ("%c", op);
		if (op == 'Q')
		{
			idxQ ++;
			q[idxQ].id = idxQ;
			q[idxQ].t = i;
			scanf ("%d %d", &q[idxQ].l, &q[idxQ].r);
		}
		else
		{
			tim[++ idxC] = i;
			scanf ("%d %d", &pos[idxC], &val[idxC]);
		}
	}
	sort (q + 1, q + idxQ + 1); // 对所有查询进行三个关键字的排序 
	for (int i = 1; i <= idxQ; i ++)
	{
		change (q[i].t); // 对于当前时间点去维护 
		while (pl > q[i].l) // 板子 
			add (-- pl); // 同上
		while (pr < q[i].r) // 同上
			add (++ pr); // 同上
		while (pl < q[i].l) // 同上
			add (pl ++); // 同上
		while (pr > q[i].r) // 同上
			del (pr --); // 同上
		ans[q[i].id] = res; // 看到这个我就想起来我爸讲的一个雾都时代笑话
	} 
}

每一块大小是 的，时间复杂度是还算可以的 。

树上莫队

分块靠得住。

因为分块可以上树所以莫队也可以上树。

莫队只能处理线性问题，所以我们要把树强行压成一维的。

给出例题：

灰蕈秘境

小刻误入了灰蕈秘境，秘境中不仅有美丽的风景，有友好的旅行商，有热水壶，还有许多蜜饼的发放点。

灰蕈秘境的结构十分奇特，它由 个关卡组成，每个关卡都有一个蜜饼发放点，有 条双向道路连接着这些关卡，并且整个秘境都是连通的，即从任何一个关卡出发都可以通过这些道路达到秘境里所有其他关卡。

小刻不喜欢走回头路，她准备从一个特定的关卡出发前往另一个特定的关卡，这条路线一定是唯一的。她经过每个关卡都可以品尝到对应种类的蜜饼。

每种蜜饼有不同美味指数，第 种蜜饼的美味指数为 。另外，如果小刻反复地品尝同一种类的蜜饼，她肯定会觉得有一些腻。根据量化统计，小刻第 次品尝某类蜜饼的新奇指数 ，如果小刻第 次品尝第 种蜜饼，那么她的希望指数 将会增加对应美味指数与新奇指数的乘积，即 。小刻这次冒险的希望指数就是最终这些乘积的和。

一看就知道是树上带修改莫队。

就是给你一棵树，每个点有颜色，每次询问 。

要干的事情就是先用 把树踩成序列，然后对于每个区间进行转移，这里会涉及一个欧拉序（入栈出栈序），也就是这个子节点在 中第一次和第二次出现的位置和时间，然后去掉因为遍历子树而产生的多余贡献。

因为扫的过程中起点里的点肯定会被扫两次，但贡献为 ，所以可以开一个 数组，每次扫到点 ，就把 异或上 ，如果 ，那这个点的贡献就可以不计，加上一维时间维就可以变成带修改树上莫队。

比如这么一张图

假设现在是 到 区间：

一波毫无压力的处理

这就不需要怎么弄了，直接该转移转移，该咋写咋写了，如果是 到 的话，就会发现中间如果不是的那些序号的都遍历过了两遍了：

这也是小问题吧果然

但是需要注意的是如果出现这种情况：

几乎失败

就需要考虑到我们有一个 ，即 没有被考虑到，然后不用担心怎么去做，其实就是最后加一个判断就可以了，判是否在同一条链上，如果是就不需要，如果不是就加上 的贡献呗，要注意的是别用奇偶化排序，已经有人吃过这个亏了，当然你要用我也不拦你。

完整代码如下：

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 1;

struct Edge {
	int nxt, to;
} edge[N << 1];

int bel[N << 1];

struct Query {
	int id, l, r, t;
	int lca;
	bool friend operator < (Query a, Query b) 
	{
		if (bel[a.l] == bel[b.l])
		{
			if (bel[a.r] == bel[b.r])
			{
				if (bel[a.r] & 1)
					return a.t < b.t;
				else
					return a.t > b.t;
			}
			if (bel[a.l] & 1)
				return a.r < b.r;
			else
				return a.r > b.r;
		}
		else
			return a.l < b.l;
	}
} q[N];

int head[N], cnt;
int n, m, qs, v[N], w[N], c[N], tmp[N], num1, num2, ans[N];
int dep[N], fa[N][19];
int a[N << 1], tot, in[N], out[N], buc[N];
int vis[N], now;

struct Event { // 记录修改
	int x, fr, to;
} h[N];

inline void add_edge (int u, int v)
{
	edge[++ cnt].to = v;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}

void dfs (int x, int depth) // 预处理出父亲、欧拉序、深度
{
	dep[x] = depth;
	a[++ tot] = x;
	in[x] = tot;
	for (int i = head[x]; i; i = edge[i].nxt)
	{
		int y = edge[i].to;
		if (y == fa[x][0])
			continue;
		fa[y][0] = x;
		dfs (y, depth + 1);
	}
	a[++ tot] = x;
	out[x] = tot; 
}

inline int lca (int x, int y) // lca 板子
{
	if (dep[x] < dep[y])
		swap (x, y);
	for (int i = 18; i >= 0; i --)
		if (dep[fa[x][i]] >= dep[y])
			x = fa[x][i];
	if (x == y)
		return x;
	for (int i = 18; i >= 0; i --)
		if (fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	return fa[x][0];
}

inline void update (int id, int c) // 这里只需要写一个 update，记录贡献，如果重复就删掉了
{
	if (c == 1)
		now += v[id] * w[buc[id] + 1];
	else
		now -= v[id] * w[buc[id]];
	buc[id] += c; // 也可以写 ^ 的
}

inline void change (int x, int o)
{
	int pos = a[x];
	if (vis[pos] & 1)
		update (c[pos], -1);
	else
		update (c[pos], 1);
	vis[pos] += o;
}

inline void add (int t)
{
	if (vis[h[t].x] == 1)
	{
		update (c[h[t].x], -1);
		c[h[t].x] = h[t].to;
		update (c[h[t].x], 1);
	}
	c[h[t].x] = h[t].to;
}

inline void del (int t)
{
	if (vis[h[t].x] == 1)
	{
		update (c[h[t].x], -1);
		c[h[t].x] = h[t].fr;
		update (c[h[t].x], 1);
	}
	c[h[t].x] = h[t].fr;
}

void work ()
{
	int l = 0, r = 0, t = 0;
	for (int i = 1; i <= num2; i ++)
	{
		while (t < q[i].t) // 维护
			add (++ t);
		while (t > q[i].t) // 同上
			del (t --);
		while (r < q[i].r) // 常规莫队 
			change (++ r, 1);
		while (l > q[i].l) // 同上 
			change (-- l, 1);
		while (r > q[i].r) // 同上
			change (r --, -1);
		while (l < q[i].l) // 同上
			change (l ++, -1);
		if (q[i].lca) // 特判 lca 
			ans[q[i].id] = now + v[c[q[i].lca]] * (w[buc[c[q[i].lca]] + 1]);
		else
			ans[q[i].id] = now;
	}
}

signed main ()
{
	scanf ("%lld %lld %lld", &n, &m, &qs);
	int sq = pow (qs, 0.66666);
	for (int i = 1; i <= m; i ++)
		scanf ("%lld", &v[i]);
	for (int i = 1; i <= n; i ++)
		scanf ("%lld", &w[i]);
	int x, y;
	for (int i = 1; i < n; i ++)
	{
		scanf ("%lld %lld", &x, &y);
		add_edge (x, y);
		add_edge (y, x);
	}
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%lld", &c[i]);
		tmp[i] = c[i];
	}
	dfs (1, 1);
	for (int j = 1; j <= 17; j ++)
		for (int i = 1; i <= n; i ++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1]; // 动规求出父亲 
	for (int i = 1; i <= tot; i ++)
		bel[i] = (i - 1) / sq + 1;
    num1 = 0;
	int op;
	for (int i = 1; i <= qs; i ++)
	{
		scanf ("%lld", &op);
		if (op == 0) // 如果是修改 
		{
			scanf ("%lld %lld", &x, &y);
			h[++ num1].x = x;
			h[num1].to = y;
			h[num1].fr = tmp[x];
			tmp[x] = y;
		}
		else // 看上去是查询 
		{
			scanf ("%lld %lld", &x, &y);
			q[++ num2].id = num2;
			q[num2].t = num1;
			int res = lca (x, y);
			if (res == x || res == y) // 如果是同一条链
			{
				if (in[x] > in[y])
					swap (x, y);
				q[num2].l = in[x];
				q[num2].r = in[y];
				q[num2].lca = 0;
			}
			else // 如果是双截棍
			{
				q[num2].lca = res;
				if (out[x] > in[y])
					swap (x, y);
				q[num2].l = out[x];
				q[num2].r = in[y];
			}
		}
	}
	sort (q + 1, q + num2 + 1);
	work ();
	for (int i = 1; i <= num2; i ++)
		printf ("%lld\n", ans[i]);
	return 0;
}

当然也可以按正常做法在树上分块，求欧拉序也可以使用树链剖分，但是要我来写估计就 行了，咕然不写。

糖果公园也就是图一乐，要真树上莫队还得看我颜色题。

给定一棵有 个节点的树，每个节点有一种颜色。

给出 次询问，每次询问给出一段区间 ，回答 之间的路径上的节点的不同颜色数。

没有带修改的操作，方便多了，直接上代码吧：

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 1;

struct Edge {
	int nxt, to;
} edge[N << 1];

int head[N], edgecnt;

int n, m, temp[N];

int sq, dep[N], a[N], tot, in[N], out[N], cnt[N], c[N], ans, res[N];

bool vis[N];

inline int getblock (int x)
{
	return x / sq + ((x % sq) ? 1 : 0);
}

int fa[N][19];

struct Query {
	int l, r, add, id;
	bool friend operator < (Query a, Query b)
	{
		if (getblock (a.l) == getblock (b.l))
			return (getblock (a.l) & 1) ? (a.r < b.r) : (a.r > b.r);
		else
			return getblock (a.l) < getblock (b.l);
	}
} q[N];

inline void add_edge (int u, int v)
{
	edge[++ edgecnt].to = v;
	edge[edgecnt].nxt = head[u];
	head[u] = edgecnt;
}

void dfs (int x, int depth)
{
	dep[x] = depth;
	a[++ tot] = x;
	in[x] = tot;
	for (int i = head[x]; i; i = edge[i].nxt)
	{
		int y = edge[i].to;
		if (y == fa[x][0])
			continue;
		fa[y][0] = x;
		dfs (y, depth + 1);
	}
	a[++ tot] = x;
	out[x] = tot;
}

inline int LCA (int x, int y)
{
	if (dep[x] < dep[y])
		swap (x, y);
	for (int i = 18; i >= 0; i --)
		if (dep[fa[x][i]] >= dep[y])
			x = fa[x][i];
	if (x == y)
		return x;
	for (int i = 18; i >= 0; i --)
		if (fa[x][i] != fa[y][i])
		{
			x = fa[x][i];
			y = fa[y][i];
		}
	return fa[x][0];
}

void add (int x)
{
	if (vis[x])
	{
		cnt[c[x]] --;
		if (cnt[c[x]] == 0)
			ans --;
	}
	else
	{
		cnt[c[x]] ++;
		if (cnt[c[x]] == 1)
			ans ++;
	}
	vis[x] ^= 1;
}

int main ()
{
	scanf ("%d %d", &n, &m);
	sq = sqrt (n);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%d", &c[i]);
		temp[i] = c[i];
	}
	sort (temp + 1, temp + n + 1);
	int size = unique (temp + 1, temp + n + 1) - temp - 1;
	for (int i = 1; i <= n; i ++)
		c[i] = lower_bound (temp + 1, temp + size + 1, c[i]) - temp;
	for (int i = 1; i < n; i ++)
	{
		int x, y;
		scanf ("%d %d", &x, &y);
		add_edge (x, y);
		add_edge (y, x);
	}
	dfs (1, 1);
	for (int j = 1; j <= 17; j ++)
		for (int i = 1; i <= n; i ++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
	for (int i = 1; i <= m; i ++)
	{
		int x, y, lca;
		scanf ("%d %d", &x, &y);
		lca = LCA (x, y);
		if (in[y] < in[x])
			swap (x, y);
		if (x == lca)
			q[i] = (Query) {in[x], in[y], 0, i};
		else
			q[i] = (Query) {out[x], in[y], lca, i};
	}
	sort (q + 1, q + m + 1);
	int ql = 1, qr = 0;
	for (int i = 1; i <= m; i ++)
	{
		while (ql < q[i].l)
		{
			add (a[ql]);
			++ ql;
		}
		while (ql > q[i].l)
		{
			-- ql;
			add (a[ql]);
		}
		while (qr < q[i].r)
		{
			++ qr;
			add (a[qr]);
		}
		while (qr > q[i].r)
		{
			add (a[qr]);
			-- qr;
		}
		if (q[i].add)
			add (q[i].add);
		res[q[i].id] = ans;
		if (q[i].add)
			add (q[i].add);
	}
	for (int i = 1; i <= m; i ++)
		printf ("%d\n", res[i]);
	return 0;
}

回滚莫队

骨碌骨碌咕。

回滚莫队不是把莫队像滚雪球一样滚成一团超可爱的样子，也不是把寿司滚来滚去，滚啥都不对。

用于维护一些不支持增加或删除操作的信息，所以也叫不删除莫队。核心思路很简单，既然我只能实现一个操作，那么就食用一个操作，剩下的交给回滚解决。

只使用增加

我们考虑一个区间问题，若这个问题在区间转移中，加点操作得以实现，但是删点操作无法有效的实现时，就可以使用只能增加的回滚莫队（像废话）。

我们先对原序列进行分块，并将所有询问以以左端点所在的块升序为第一关键字，以右端点升序为第二关键字的方式排序。

如果询问左端点所属块 和上一个询问的左端点所属块不同，那么将莫队区间的左端点初始化为 的右端点加一，将莫队区间的右端点初始化为 的右端点，这是一个空区间。

如果询问的左右端点在同一个块中，就直接暴力扫描区间回答询问。

但是如果左右端点所属块不同：此时，如果询问的右端点大于莫队区间的右端点，那么不断扩展右端点直到莫对区间的右端点等于询问的右端点，不断扩展莫队区间的左端点直至莫队区间的左端点等于询问的左端点，然后回答询问，撤销左端点的改动，使莫队区间的左端点回滚到 的右端点加一。

时间复杂度是 。

给出一道例题：

歴史の研究

国历研究的第一人—— 教授，最近获得了一份被认为是古代 国的住民写下的日记， 教授为了通过这份日记来研究古代 国的生活，开始放弃着手调查日记中记载的事件。

日记里记录了连续 天发生的事件，大约每天发生一件，狗屁多大的事怎么这么多呢。

事件有种类之分。第 天发生的事件的种类用一个整数 表示， 越大，就说明事件的规模越大。

教授决定选择日记中连续的一段日子 作为分析的时间段，同时定义事件 的重要度 为 ，其中 为该事件在区间 中出现的次数。

现在，教授需要自己求出所有事件中重要度最大的时间是哪个，并输出其重要度，因为 教授很强所以你不需要帮他了，他自己就能完成这个程序，或者可以自己心算。

既然上面过程都清晰明了都说出来了，直接放例题完整代码了：

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
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 1;

int n, m, a[N], sq, bel[N], u[N], tot, ans[N], tmp[N];

int cnt[N], now, cur;

struct Query {
	int l, r, id;
	bool friend operator < (Query x, Query y)
	{
		return bel[x.l] == bel[y.l] ? x.r < y.r : x.l < y.l;
	}
} q[N];

inline int calc (int l, int r) // 计算贡献  
{
	int res = 0;
	for (int i = l; i <= r; i ++)
		tmp[a[i]] = 0;
	for (int i = l; i <= r; i ++)
	{
		tmp[a[i]] ++;
		res = max (res, tmp[a[i]] * u[a[i]]);
	}
	return res;
}

inline void add (int x)
{
	cnt[x] ++;
	now = max (now, cnt[x] * u[x]);
}

inline void del (int x)
{
	cnt[x] --;
}

inline void work ()
{
	int L = sq, R = L - 1, pl = L;
	for (int i = 1; i <= m; i ++)
	{
		if (bel[q[i - 1].l] < bel[q[i].l]) // 不在同一块内  
		{
			L = (bel[q[i].l] + 1) * sq;
			R = L - 1;
			memset (cnt, 0, sizeof cnt);
			pl = L;
			cur = now = 0;
		}
		if (bel[q[i].l] == bel[q[i].r]) // 在同一块内  
		{
			ans [q[i].id] = calc (q[i].l, q[i].r); // 直接暴力处理  
			continue;
		}
		while (R < q[i].r)
			add (a[++ R]); // 扩展右端点  
		cur = now;
		while (q[i].l < L)
			add (a[-- L]); // 扩展左端点  
		ans[q[i].id] = now; // 回答询问  
		while (L < pl) // 撤销左端点改动  
			del (a[L ++]);
		now = cur;
	}
}

signed main ()
{
	scanf ("%lld %lld", &n, &m);
	sq = sqrt (n);
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%lld", &a[i]);
		bel[i] = i / sq;
		u[i] = a[i];
	}
	sort (u + 1, u + n + 1);
	tot = unique (u + 1, u + n + 1) - u - 1;
	for (int i = 1; i <= n; i ++)
		a[i] = lower_bound (u + 1, u + tot + 1, a[i]) - u;
	for (int i = 1; i <= m; i ++)
	{
		scanf ("%lld %lld", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort (q + 1, q + m + 1);
	work ();
	for (int i = 1; i <= m; i ++)
		printf ("%lld\n", ans[i]);
	return 0;
}

只使用删除

有增加就有删除，或多或少，想一次分块到老，说增加太潦草。只不过前提是我们能够正确的先将整个序列加入莫队中，流程和之前差不多。

其实原来这里写的是” 教授说实现不了，于是不写了“，这么一段话。

我们先对原序列进行分块，并将所有询问以以左端点所在的块升序为第一关键字，以右端点降序为第二关键字的方式排序。

如果询问左端点所属块 和上一个询问的左端点所属块不同，那么将莫队区间的左端点初始化为 的左端点，将莫队区间的右端点初始化为 ，这是一个大区间。

还是对于一个左右端点在同一个块中的询问直接暴力扫描回答即可。

对于不在左右端点不在同一块的询问，其左端点可能是乱序的，每一次从 的左端点出发，只做删点操作，直到到达询问位置即可，一个询问最多加 次。回答完询问后撤销移动左端点的改动，使左端点回到 的左端点。

有一个长度为 的数组 。

次询问，每次询问一个区间内最小没有出现过的自然数。

思路就是用桶维护出现过的数字，那么 值就是第一个不在桶中出现的数字，既然是不增加莫队，那么就在刚开始把整个序列用桶维护并统计答案，撤销操作在桶中更新。

给出代码，改的东东不多：

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
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 1;

int n, m, bel[N], a[N], cnt[N], sq, t, ans[N];

int tot[N], res, L[N], R[N], minn;

struct Query {
	int l, r, id;
	bool friend operator < (Query x, Query y)
	{
		if (bel[x.l] ^ bel[y.l])
			return bel[x.l] < bel[y.l];
		else
			return x.r > y.r;
	}
} q[N];

inline void remove (int p, int &Minval) // 这是删点
{
	if (a[p] > n + 1)
		return ;
	cnt[a[p]] --;
	if (cnt[a[p]] == 0)
		Minval = min (Minval, a[p]);
} 

inline void resume (int p) // 这是撤
{
	if (a[p] > n + 1)
		return ;
	cnt[a[p]] ++;
}

void work () // 莫队板子不像这
{
	sort (q + 1, q + m + 1);
	int l = 1, r = n, pl = 0;
	for (int i = 1; i <= m; i ++)
	{
		if (bel[q[i].l] == bel[q[i].r]) // 同一块内询问 
		{
			for (int j = q[i].l; j <= q[i].r; j ++)
				if (a[j] <= n + 1)
					tot[a[j]] ++;
			int temp = 0;
			while (tot[temp])
				temp ++;
			ans[q[i].id] = temp;
			for (int j = q[i].l; j <= q[i].r; j ++)
				if (a[j] <= n + 1)
					tot[a[j]] --;
			continue;
		}
		if (bel[q[i].l] ^ pl) // 到了一个新块，先初始化左右端点 
		{
			while (r < n)
				resume (++ r);
			while (l < L[bel[q[i].l]])
				remove (l ++, res);
			minn = res;
			pl = bel[q[i].l];
		}
		while (r > q[i].r) // 移动右端点 
			remove (r --, minn);
		int temp = minn, cl = l;
		while (cl < q[i].l) // 移动左端点回答询问
			remove (cl ++, temp);
		while (cl > l) // 咱，撤！
			resume (-- cl);
		ans[q[i].id] = temp;
	}
}

int main ()
{
	scanf ("%d %d", &n, &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;
	}
	for (int i = 1; i <= n; i ++)
		if (a[i] <= n + 1)
			cnt[a[i]] ++; // 将整个序列加入桶，同时得到整体答案
	while (cnt[res])
		res ++;
	sq = sqrt (n);
	t = n / sq;
	for (int i = 1; i <= t; i ++)
	{
		if (i * sq > n)
			break;
		L[i] = (i - 1) * sq + 1;
		R[i] = i * sq;
	}
	if (R[t] < n)
	{
		t ++;
		L[t] = R[t - 1] + 1;
		R[t] = n; 
	}
	for (int i = 1; i <= t; i ++)
		for (int j = L[i]; j <= R[i]; j ++)
			bel[j] = i;
	work ();
	for (int i = 1; i <= m; i ++)
		printf ("%d\n", ans[i]);
	return 0;
}

二次离线莫队

您的好友已。

在使用莫队的时候，往往需要使用在线数据结构维护信息，但是有一些复杂的信息往往需要带有 复杂度的数据结构才能维护，使得整个算法的复杂度升高到了 。

基础

来看一道非常有意思而且老少皆宜的题目：

给出一个长为 的序列 ， 次询问，每次查询一个区间内的逆序对数。

这道题我们不得不用到树状数组，但是非常慢，所以我们可以开 来解决这个棘手的问题。

我们需要 次对某一数据结构实施动态的修改和查询操作。

所以既然询问都可以离线下来，为什么不能把操作离线下来呢？

操作离线

至于这个把操作离线的过程，我们要用一个 去实现，将所有指针 的移动，存到其移动前对应的 处，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Node {
	int p, l, r, id;
};

vector <Node> vec1[N], vec2[N];

inline void add1 (int x, int p, int k1, int k2, int id) // 存左端点查询
{
	vec1[x].push_back ((Node) {p, k1, k2, id});
}

inline void add2 (int x, int p, int k1, int k2, int id) // 存右端点查询
{
	vec2[x].push_back ((Node) {p, k1, k2, id});
}

去考虑莫队中四种移动，然后在主函数里这么调用：

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
for (int i = 1; i <= m; i ++)
{
	if (r < q[i].r)
	{
		ans[q[i].id] += (sum1[q[i].r] - sum1[r]);
		add1 (l, -1, r + 1, q[i].r, q[i].id);
		r = q[i].r;
	}
	if (r > q[i].r)
	{
		ans[q[i].id] -= (sum1[r] - sum1[q[i].r]);
		add1 (l, 1, q[i].r + 1, r, q[i].id);
		r = q[i].r;
	}
	if (l < q[i].l)
	{
		ans[q[i].id] -= (sum2[l] - sum2[q[i].l]);
		add2 (r, 1, l, q[i].l - 1, q[i].id);
		l = q[i].l;
	}
	if (l > q[i].l)
	{
		ans[q[i].id] += (sum2[q[i].l] - sum2[l]);
		add2 (r, -1, q[i].l, l - 1, q[i].id);
		l = q[i].l;
	}
}

这里我们每种情况拉出来细讲。

第一种，左指针向左移动，同时答案会增加 区间中比 小的个数：

1
2
3
4
5
6
if (l > q[i].l)
{
	ans[q[i].id] += (sum2[q[i].l] - sum2[l]);
	add2 (r, -1, q[i].l, l - 1, q[i].id);
	l = q[i].l;
}

第二种，左指针向右移动，同时答案会减少 中比 小的个数：

1
2
3
4
5
6
if (l < q[i].l)
{
	ans[q[i].id] -= (sum2[l] - sum2[q[i].l]); 
	add2 (r, 1, l, q[i].l - 1, q[i].id);
	l = q[i].l;
}

第三种，右指针向右移动，同时答案会增加 中比 大的个数：

1
2
3
4
5
6
if (r < q[i].r)
{
	ans[q[i].id] += (sum1[q[i].r] - sum1[r]);
	add1 (l, -1, r + 1, q[i].r, q[i].id);
	r = q[i].r;
}

第四种，右指针向左移动，同时答案会增加 中比 大的个数：

1
2
3
4
5
6
if (r > q[i].r)
{
	ans[q[i].id] -= (sum1[r] - sum1[q[i].r]);
	add1 (l, 1, q[i].r + 1, r, q[i].id);
	r = q[i].r;
}

预处理

然后关于预处理的事，这个很简单，同时利用差分， 中有多少个数比 大，也就是 中比 大的数的数量减去 中比 大的数的数量（等等这个是差分么，为什么这么像前缀和）：

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= n; i ++)
{
	num1[i] += (i - 1 - tr_sum (c[i]));
	tr_add (c[i], 1);
	sum1[i] = sum[i - 1] + num1[i];
}
for (int i = n; i >= 1; i --)
{
	num2[i] += tr_sum (c[i] - 1);
	tr_add (c[i], 1);
	sum2[i] = sum2[i + 1] + num2[i];
}

然后去写个数状数组的板子：

1
2
3
4
5
6
7
8
9
10
11
12
inline void tr_add (int x, int k)
{
	for (int i = x; i <= n; i += lowbit (i))
		tree[i] += k;
}
inline int tr_sum (int x)
{
	int res = 0;
	for (int i = x; i; i -= lowbit (i))
		res += tree[i];
	return res;
}

该做的已经做完了，但是！天王老子来了我都不会告诉你要调和时间复杂度！

好了现在告诉你，我们要：

调和时间复杂度

上面存了 组移动，也就是要处理 组询问，但是我们可以使用一些歪门邪道来平衡它的时间复杂度。

因为我们要处理 组询问，却只需要插入 组数，所以可以使用一个插入 ，查询 的数组结构——值域分块，最后复杂度会被平衡到 。

值域分块无非就是普通的分块加上前缀和，美名其曰值域分块，要注意的就是下标是数字，存的是贡献。

给出最后的代码：

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
void solve ()
{
	cnt = sqrt (idnum);
	sz = 1;
	L[sz] = 1;
	if (cnt * cnt < idnum)
		++ cnt; // 可能块长是不够的，得加 
	for (int i = 1; i <= idnum; i ++)
	{
		bel[i] = sz;
		if (i % cnt == 0)
		{
			R[sz] = i;
			L[++ sz] = i + 1;
		}
	}
	R[sz] = idnum; // 就最后一块的右端点，这个大家肯定都知道
	for (int i = 1; i <= n; i ++)
	{
		int siz = vec1[i].size () - 1, fr, ed, id, p;
		for (int j = 0; j <= siz; j ++)
		{
			id = vec1[i][j].id;
			p = vec1[i][j].p;
			fr = vec1[i][j].l
			ed = vec1[i][j].r;
			for (int k = fr; k <= ed; k ++)
				ans[id] += p * (ad[bel[c[k] + 1]] + w[c[k] + 1]);
		}
		pushup1 (c[i]);
	}
	memset (ad, 0, sizeof ad);
	memset (w, 0, sizeof w);
	for (int i = n; i >= 1; i --)
	{
		int siz = vec2[i].size () - 1, fr, ed, id, p;
		for (int j = 0; j <= siz; j ++)
		{
			id = vec2[i][j].id;
			p = vec2[i][j].p;
			fr = vec2[i][j].l;
			ed = vec2[i][j].r;
			for (int k = fr; k <= ed; k ++)
				ans[id] += p * (ad[bel[c[k] - 1]] + w[c[k] - 1]);
		}
		pushup2 (c[i]);
	}
}

给出完整代码：

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5; // 一言难尽  
const int M = 355;

int n, m, tot, idnum;

int tree[N];

int c[N], num1[N], num2[N], cnt, w[N], bel[N], sz, L[M], R[M], ad[M];

long long ans[N], sum1[N], sum2[N];

struct Query {
	int l, r, id;
} q[N], p[N];

struct Node {
	int p, l, r, id;
};

vector <Node> vec1[N], vec2[N];

inline bool cmp1 (Query a, Query b)
{
	return (a.l / tot == b.l / tot) ? a.r < b.r : a.l < b.l;
}

inline bool cmp2 (Query a, Query b)
{
	return a.l < b.l;
} 

inline int lowbit (int x)
{
	return x & -x;
}

inline void tr_add (int x, int k)
{
	for (int i = x; i <= n; i += lowbit (i))
		tree[i] += k;
}

inline int tr_sum (int x)
{
	int res = 0;
	for (int i = x; i; i -= lowbit (i))
		res += tree[i];
	return res;
}

inline void add1 (int x, int p, int k1, int k2, int id)
{
	vec1[x].push_back ((Node) {p, k1, k2, id});
}

inline void add2 (int x, int p, int k1, int k2, int id)
{
	vec2[x].push_back ((Node) {p, k1, k2, id});
}

void pushup1 (int x)
{
	if (ad[bel[x]])
		for (int i = L[bel[x]]; i <= R[bel[x]]; i ++)
			w[i] += ad[bel[x]];
	ad[bel[x]] = 0;
	for (int i = L[bel[x]]; i <= x; i ++)
		++ w[i];
	for (int i = 1; i <= bel[x] - 1; i ++)
		++ ad[i];
}

void pushup2 (int x)
{
	if (ad[bel[x]])
		for (int i = L[bel[x]]; i <= R[bel[x]]; i ++)
			w[i] += ad[bel[x]];
	ad[bel[x]] = 0;
	for (int i = x; i <= R[bel[x]]; i ++)
		++ w[i];
	for (int i = bel[x] + 1; i <= sz; i ++)
		++ ad[i];
}

void solve ()
{
	cnt = sqrt (idnum);
	sz = 1;
	L[sz] = 1;
	if (cnt * cnt < idnum)
		++ cnt;
	for (int i = 1; i <= idnum; i ++)
	{
		bel[i] = sz;
		if (i % cnt == 0)
		{
			R[sz] = i;
			L[++ sz] = i + 1;		
		}
	}
	R[sz] = idnum;
	for (int i = 1; i <= n; i ++)
	{
		int fr, ed, id;
		long long p;
		for (int j = 0; j < vec1[i].size (); j ++)
		{
			id = vec1[i][j].id;
			p = 1ll * vec1[i][j].p;
			fr = vec1[i][j].l;
			ed = vec1[i][j].r;
			for (int k = fr; k <= ed; k ++)
				ans[id] += 1ll * p * (ad[bel[c[k] + 1]] + w[c[k] + 1]);
		}
		pushup1 (c[i]);
	}
	memset (ad, 0, sizeof ad);
	memset (w, 0, sizeof w);
	for (int i = n; i >= 1; i --)
	{
		int fr, ed, id;
		long long p;
		for (int j = 0; j < vec2[i].size (); j ++)
		{
			id = vec2[i][j].id;
			p = 1ll * vec2[i][j].p;
			fr = vec2[i][j].l;
			ed = vec2[i][j].r;
			for (int k = fr; k <= ed; k ++)
				ans[id] += 1ll * p * (ad[bel[c[k] - 1]] + w[c[k] - 1]);
		}
		pushup2 (c[i]);
	}
}

int main ()
{ 
	scanf ("%d %d", &n, &m);
	tot = 355;
	for (int i = 1; i <= n; i ++)
	{
		scanf ("%d", &c[i]);
		p[i].l = c[i];
		p[i].id = i;
	}
	sort (p + 1, p + n + 1, cmp2);
	p[0].l = -1;
	for (int i = 1; i <= n; i ++)
		c[p[i].id] = (idnum += (p[i].l != p[i - 1].l));
	for (int i = 1; i <= m; i ++)
	{
		scanf ("%d %d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	for (int i = 1; i <= n; i ++)
	{
		num1[i] += (i - 1 - tr_sum (c[i]));
		tr_add (c[i], 1);
		sum1[i] = sum1[i - 1] + num1[i];
	}
	memset (tree, 0, sizeof tree);
	for (int i = n; i >= 1; i --)
	{
		num2[i] += tr_sum (c[i] - 1);
		tr_add (c[i], 1);
		sum2[i] = sum2[i + 1] + num2[i];
	}
	sort (q + 1, q + m + 1, cmp1);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i ++)
	{
		if (r < q[i].r)
		{
			ans[q[i].id] += (sum1[q[i].r] - sum1[r]);
			add1 (l, -1, r + 1, q[i].r, q[i].id);
			r = q[i].r;
		}
		if (r > q[i].r)
		{
			ans[q[i].id] -= (sum1[r] - sum1[q[i].r]);
			add1 (l, 1, q[i].r + 1, r, q[i].id);
			r = q[i].r;
		}
		if (l < q[i].l)
		{
			ans[q[i].id] -= (sum2[l] - sum2[q[i].l]);
			add2 (r, 1, l, q[i].l - 1, q[i].id);
			l = q[i].l;
		}
		if (l > q[i].l)
		{
			ans[q[i].id] += (sum2[q[i].l] - sum2[l]);
			add2 (r, -1, q[i].l, l - 1, q[i].id);
			l = q[i].l;
		}
	}
	solve ();
	for (int i = 1; i <= m; i ++)
		ans[q[i].id] += ans[q[i - 1].id];
	for (int i = 1; i <= m; i ++)
		printf ("%lld\n", ans[i]);
	return 0;
}

数据太阴间了，我开了 结果错一个点，开 才能过……一言难尽。

树上带修改二次离线动态回滚莫队

没有这玩意。