莫队算法 学习笔记

模板及讲解

莫队是什么

莫(膜)队是离线处理区间问题的一大武器,由莫队发明,其核心为最优化分块思想排序,用已知区间推区间的算法。

莫队解决什么问题

1、无修改或者修改不苛刻
2、离线
3、能用很小的复杂度从$[l,r]$转移到$[l-1, r], [l, r-1], [l+1, r], [l, r+1]$,例如$O(1), O(logn)$

莫队的实现

例题:Bzoj 1878

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

暴力

暴力是显然$O(n^2)$的,我们想想暴力是否会有很多重复的计算,比如说
$[1, 6]$和$[2,7]$,暴力会算$11$次,而实际需要那么多次吗?当然不需要,我们直接在询问$[1, 6]$基础上删掉$1$处的贡献,增加$7$处的贡献就可以得到,只用算$8$次。这就是莫队的思想。

暴力优化

我们尝试把询问区间离线按$l$排序,则会有一定的优化,但是看下面的例子:
$[1, 100], [2, 4], [3, 101]$
这会使得当前右边界时大时小,影响效率。
怎么办?我们可以取一下平均,$l$不最优,$r$不最优,但总体最优的情况。

莫队

我们把询问数组分块,分成$n / \sqrt n$块,然后进行以下的排序:

1
2
3
4
bool cmp1(const query &a, const query &b) {//莫队排序
if (bl[a.l] == bl[b.l]) return a.r < b.r;
return bl[a.l] < bl[b.l];
}

其中$bl[i]$表示$i$所在的块。化作文字即为:如果两个询问区间的$l$在同一块中,就按$r$为关键字排序,否则用所在块的编号排序。
这样就能达到比较”好”的复杂度,但是这个复杂度是什么呢?

复杂度证明

对于$l$: 如果下一个询问区间$l$不在这个块里,则需要最多$2 \times \sqrt n$次
对于$r$: $r$在一个块里单调递增,所以$r$在每个块中最多$n$次,有$n / \sqrt n$个块,所以最多需要$n \times n / \sqrt n$次

综上所述,莫队算法的复杂度为$O(n\sqrt n)​$

代码

Bzoj 1878的代码:

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
const int MAXN = 1000000 + 5;
int m, n, totblo, ai[MAXN], bl[MAXN];
struct query {
int l, r, id, ans;//询问左边界,右边界,第几个询问,答案
}q[MAXN];
bool cmp1(const query &a, const query &b) {//莫队排序
if (bl[a.l] == bl[b.l]) return a.r < b.r;
return bl[a.l] < bl[b.l];
}
bool cmp2(const query &a, const query &b) {
return a.id < b.id;
}
int nl, nr, nans, tax[MAXN];//当前l位置,当前r位置,当前答案,桶
void clean() {nl = nr = nans = 0, ms(tax, 0);}
void adjust(int x, int add) {
if (tax[ai[x]] == 0 && add == 1) nans++;
tax[ai[x]] += add;
if (tax[ai[x]] == 0 && add == -1) nans--;
/*一定要指明add
否则 对于询问区间1 3后询问5 8 会炸
*/
}
int solve() {
clean();
totblo = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%d", &ai[i]);
bl[i] = (i - 1) / totblo + 1;
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q + 1, q + 1 + m, cmp1);
nl = 1, nr = 0;
for (int i = 1; i <= m; i++) {
while (nl < q[i].l) adjust(nl , -1), nl++;
while (nl > q[i].l) adjust(nl - 1, +1), nl--;
while (nr < q[i].r) adjust(nr + 1, +1), nr++;
while (nr > q[i].r) adjust(nr , -1), nr--;
q[i].ans = nans;//进行调整
}
sort(q + 1, q + 1 + m, cmp2);
for (int i = 1; i <= m; i++) printf("%d\n", q[i].ans);
return 0;
}
int main() {
scanf("%d", &n), solve();
return 0;
}

注意:莫队的扩充区间放在缩小区间前可以避免出现某些问题,比如

1
2
3
4
while (nl < q[i].l) adjust(nl , -1), nl++;
while (nl > q[i].l) adjust(nl - 1, +1), nl--;
while (nr < q[i].r) adjust(nr + 1, +1), nr++;
while (nr > q[i].r) adjust(nr , -1), nr--;

改为

1
2
3
4
while (nl < q[i].l) adjust(nl , -1), nl++;
while (nr < q[i].r) adjust(nr + 1, +1), nr++;
while (nl > q[i].l) adjust(nl - 1, +1), nl--;
while (nr > q[i].r) adjust(nr , -1), nr--;

带修莫队

例题:Bzoj 2120

墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?

大意:多个区间询问,询问$[l,r]$中颜色的种类数。可以单点修改颜色

莫队怎么支持修改?我们可以引入一个时间$t$, 来记录某个询问是顺序修改了几次后的。
然后就可以按照莫队的思路,根据$t$不断地更新/回退修改,以达到目的。但是直接改复杂度不能保证,所以我们要用以下排序方法:

1
2
3
4
5
bool cmp1(const query &a, const query &b) {//莫队带修排序
if (bl[a.l] == bl[b.l])
return (bl[a.r] == bl[b.r] ? a.t < b.t : a.r < b.r);
return bl[a.l] < bl[b.l];
}

这样就能保证复杂度了。

复杂度证明

($totblo$为块长,不等于$\sqrt n$)
对于$l$和$r$,与不带修得莫队相同。
对于$t$: 考虑有几个单调段,假设最坏情况每个块中的$t$都不单调,则会有$(n / totblo)^2$个单调段,每个单调段互相转移的时间是$O(n)$,所以最后的复杂度为$O(n(n / totblo)^2)$

综上所述,在$totblo=n^{\frac23}$时带修莫队算法的复杂度为$O(n^{\frac53})$,一般能过$10000$及以下的数据(只比暴力好一点点)。

代码

Bzoj 2120的代码:

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
const int MAXN = 10000 + 5;
int n, m, bl[MAXN], totblo, n_q, n_u, ai[MAXN], oai[MAXN], ans[MAXN], lst[MAXN], tax[1000000 + 5];
//n_q, n_u分别为q,u数组大小(询问,修改个数)
//oai为原数组,lst为该位置现在的值是哪个修改修改的(没有修改为0)
//tax为桶
struct query {//询问
int l, r, t, id;
//t为时间戳
bool operator < (const query &b) const {//带修莫队排序
if (bl[l] == bl[b.l])
return (bl[r] == bl[b.r] ? t < b.t : r < b.r);
return bl[l] < bl[b.l];
}
}q[MAXN];
struct update {//修改
int p, col, lst;//位置、颜色、上一个该位置(p)的修改 (没有修改为0)
}u[MAXN];
int nt, nl, nr, nans;
void clean() {
n_q = n_u = 0;
ms(tax, 0);
}
void adjust(int x, int add) {
tax[ai[x]] += add;
if (add == 1 && tax[ai[x]] == 1) nans++;
if (add == -1 && tax[ai[x]] == 0) nans--;
}
void update_update(int type, int id, int x) {
//1撤销,2更新
if (type == 1) {
if (nl <= x && x <= nr) adjust(x, -1);//nl <= x && x <= nr才adjust!!!!!
if (u[id].lst == 0) ai[x] = oai[x]; else ai[x] = u[u[id].lst].col;
if (nl <= x && x <= nr) adjust(x, +1);//nl <= x && x <= nr才adjust!!!!!
lst[x] = u[id].lst;
} else {
u[id].lst = lst[x];
lst[x] = id;
if (nl <= x && x <= nr) adjust(x, -1);//nl <= x && x <= nr才adjust!!!!!
ai[x] = u[id].col;
if (nl <= x && x <= nr) adjust(x, +1);//nl <= x && x <= nr才adjust!!!!!
}
}
int solve() {
clean();
totblo = pow(n, 0.66666666);
for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), oai[i] = ai[i];
for (int i = 1; i <= m; i++) {
char opt[10];
scanf("%s", opt);
if (opt[0] == 'Q') {
n_q++;
q[n_q].id = n_q, q[n_q].t = n_u;
scanf("%d%d", &q[n_q].l, &q[n_q].r);
} else {
n_u++, lst[n_u] = 0, u[n_u].lst = 0;
scanf("%d%d", &u[n_u].p, &u[n_u].col);
}
}
sort(q + 1, q + 1 + n_q);
nt = 0, nl = 1, nr = 0, nans = 0;
for (int i = 1; i <= n_q; i++) {
while (nt > q[i].t) update_update(1, nt, u[nt].p), nt--;//撤销
while (nt < q[i].t) update_update(2, nt + 1, u[nt + 1].p), nt++;//更新
while (nl < q[i].l) adjust(nl , -1), nl++;
while (nl > q[i].l) adjust(nl - 1, +1), nl--;
while (nr < q[i].r) adjust(nr + 1, +1), nr++;
while (nr > q[i].r) adjust(nr , -1), nr--;
ans[q[i].id] = nans;
}
for (int i = 1; i <= n_q; i++) printf("%d\n", ans[i]);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}
/*
不判 nl <= x && x <= nr WA的数据
6 8
1 2 3 4 5 5
R 4 4
R 2 3
Q 1 4
R 1 2
Q 1 4
R 3 5
R 5 8
Q 1 4
*/

树上莫队

例题:SPOJ COT2

给一棵树,每个点有一个权值。多次询问路径$(u, v)$上有多少个权值不同的点。

树上莫队的资料
考虑树上莫队。难点在于怎么将树搬到序列中。将树的括号序求出来,树的括号序就是维护一个序列,这个序列是dfs这棵树时,每个节点在dfs到的时候将本身加入序列,然后离开该节点(返回父节点)也将本身加入序列的一个序列(具体可以看资料,有图解)。
我们设$st,ed$分别为某个点最开始在序列出现位置和最后出现在序列的位置。对于一条路径$(u,v)$(这里$st_u \leq st_v$):
如果$LCA=u$,那么路径信息就是$st_u$到$st_v$之间一段中出现次数为奇数次的点的信息。
否则,路径就是$ed_u$到$st_v$之间一段中出现次数为奇数次的点。注意这一段并不包含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
81
82
83
84
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 40000 + 5, logs = 18;
int n, m, whw, blolen, bl[MAXN * 2], ai[MAXN], st[MAXN], ed[MAXN], T[MAXN * 2], tax[MAXN], sz;
int dep[MAXN], vis[MAXN], nl, nr, nans, pre[MAXN][22], ans[100000 + 5];
vector<int> G[MAXN];
struct data {
int l, r, u, v, id, lca;
bool operator < (const data &b) const {
if (bl[l] == bl[b.l]) return r < b.r;
return bl[l] < bl[b.l];
}
}xw[100000 + 5];
void dfs(int u, int pa) {
dep[u] = dep[pa] + 1, T[++sz] = u, st[u] = sz, pre[u][0] = pa;
for (int i = 1; i <= logs; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
for (int i = 0; i < (int)G[u].size(); i++) {
int v = G[u][i];
if (v != pa) dfs(v, u);
}
T[++sz] = u, ed[u] = sz;
}
void ins(int a, int b) {G[a].push_back(b), G[b].push_back(a);}
int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i = logs; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
if (a == b) return a;
for (int i = logs; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
void adjust(int x) {
tax[T[x]] = 1 - tax[T[x]];
if (tax[T[x]] % 2) {
vis[ai[T[x]]]++;
if (vis[ai[T[x]]] == 1) nans++;
} else {
vis[ai[T[x]]]--;
if (vis[ai[T[x]]] == 0) nans--;
}
}
void clean() {
ms(dep, 0), sz = 0;
}
int solve() {
clean();
blolen = (int)sqrt(2 * n);
for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), tax[i] = ai[i];
for (int i = 1; i <= 2 * n; i++) bl[i] = (i - 1) / blolen + 1;
sort(tax + 1, tax + 1 + n), whw = unique(tax + 1, tax + 1 + n) - tax - 1;
for (int i = 1; i <= n; i++) ai[i] = lower_bound(tax + 1, tax + 1 + whw, ai[i]) - tax;
for (int u, v, i = 1; i < n; i++) scanf("%d%d", &u, &v), ins(u, v);
dfs(1, 0);
for (int i = 1; i <= m; i++) scanf("%d%d", &xw[i].u, &xw[i].v), xw[i].id = i, xw[i].lca = LCA(xw[i].u, xw[i].v);
for (int i = 1; i <= m; i++) {
if (st[xw[i].u] > st[xw[i].v]) swap(xw[i].u, xw[i].v);
if (xw[i].lca != xw[i].u) xw[i].l = ed[xw[i].u], xw[i].r = st[xw[i].v];
else xw[i].l = st[xw[i].u], xw[i].r = st[xw[i].v];
}//转到括号序上
sort(xw + 1, xw + 1 + m);
ms(tax, 0), ms(vis, 0), nl = 1, nr = 0, nans = 0;
for (int i = 1; i <= m; i++) {
while (nl < xw[i].l) adjust(nl), nl++;
while (nl > xw[i].l) adjust(nl - 1), nl--;
while (nr < xw[i].r) adjust(nr + 1), nr++;
while (nr > xw[i].r) adjust(nr), nr--;
ans[xw[i].id] = nans;
if (xw[i].lca != xw[i].u) {
if (vis[ai[xw[i].lca]] == 0) ans[xw[i].id]++;//加上LCA
}
}
for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
return 0;
}
int main() {
scanf("%d%d", &n, &m), solve();
return 0;
}

回滚莫队

用于一些不方便删除或者添加更新答案的离线区间题目。比如Bzoj 4241

有一个长度为$n$的序列,有$m$个询问,每次询问$[l, r]$内每个数值乘以该数值出现次数的最大值。

由于删除更新答案不方便,那么这里可以用回滚莫队。按照原莫队方法排序,那么左端点在一块的询问就到了一起,并且右端点单调递增,右端点只有增加,考虑左端点。要使得左端点只能增加,我们把所有在一个块的左端点的询问一起处理,都将莫队中的左端点移到块最右边,每次查询的时候就从最右边开始向左延伸,记录答案,然后再回退到块最右边,这样就避免了删除。一个块处理完后,因为右端点会有删除的情况,所以直接抛弃之前的所有答案,重新从新询问开始记录答案。对于左右端点在同块的询问,直接暴力即可。
时间复杂度分析:
1、对于左右端点在同块的询问,其时间复杂度最坏为$O(m\sqrt n)$
2、在同块中处理时,右端点单调递增,最多增加$n$次,复杂度$O(n\sqrt n)$。左端点回滚,由于在块中,最多滚动$\sqrt n$次,复杂度$O(m\sqrt n)$。
3、对于左端点不同块之间的转换,清除记录数组时间复杂度$O(n\sqrt n)$
由于$m,n$同级,所有算法复杂度为$O(n\sqrt n)$

常见题型

1、维护区间离线,无修改
Q:维护区间离线无修改
解:见讲解的莫队实现
例题:Bzoj 1878
2、维护区间离线,有简单修改(带修莫队)
Q:维护区间离线有简单修改
解:见讲解的带修莫队实现
例题:Bzoj 2120
3、维护树离线(树上莫队)
Q:见讲解
解:见讲解
例题:SPOJ COT2
4、维护区间离线,删除/添加更新答案不方便(回滚莫队)
Q:见讲解
解:见讲解
例题:Bzoj 4241

------ 本文结束 ------