莫队 学习笔记

我没死,真的……真的……虽说已经在退役的边缘了……

话说看到lyd神犇的评论要把我吓死了啊woccc

久违的学点新东西吧。

不过说真的莫队这玩意是当年一系列学失败的东西之一啊……

莫队算法的引入

先来看一道最经典的例题。

有一个数列${a}$,现在给出$m$次询问,每次查询在$[L, R]$区间内出现次数是$k$的数字种数。

$n \leq 100000, a_i \leq 100000, m \leq 100000$

先来考虑一个朴素算法:暴力枚举。显然emmmm

接着来考虑这样一种思想:

1
2
3
4
5
6
7
8
9
10
11
inline void add(int pos) {
cnt[a[pos]]++;
if(cnt[a[pos]] == k) ++qwq;
if(cnt[a[pos]] == k + 1) --qwq;
}

inline void remove(int pos) {
cnt[a[pos]]--;
if(cnt[a[pos]] == k) ++qwq;
if(cnt[a[pos]] == k - 1) --qwq;
}

上面这两个函数用来做一件显然的事情:当$a_{pos}$从某个区间中加入或删除时发生的事情。于是我们就有了这么一个奇妙的思路:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline void extend_R(int pos, int aim) {
while(pos < aim) ++pos, add(pos);
}

inline void narrow_R(int pos, int aim) {
while(pos > aim) remove(pos), pos--;
}

inline void extend_L(int pos, int aim) {
while(pos > aim) --pos, add(pos);
}

inline void narrow_L(int pos, int aim) {
while(pos < aim) remove(pos), pos++;
}

这四个函数用来扩展一个区间的左右端点。如果我们现在已经知道$[L_1, R_1]$的答案,想要知道$[L_2, R_2]$的,只需要不断的扩展左右端点并不断更新答案。

但显然这样的算法复杂度仍然是$O(n^2)$的,而莫队算法最神奇的事情就是,它通过转换枚举顺序,将复杂度降到了$O((n + m) \sqrt n)$。

我们先来说结论。令$block = \sqrt n$,即分成$\sqrt n$块,我们将区间以下列顺序排序:

  • 如果$L_i, L_j$不属于同一块,则按照$L$的顺序升序排列

  • 如果$L_i, L_j$属于同一块,则按照$R$的顺序升序排列

结束了?结束了。其正确性如下:

考虑摊还分析。我们可以将该算法理解成左指针和右指针在不断移动的过程,那么:
对于右指针,在每个块中移动最多$N$次,在到下一个块时移动$N$次,一共有$\sqrt N$块,所以复杂度为$O(N \sqrt N)$;
对于左指针,由于每个块内是可以乱动的,但是块的长度是$O(\sqrt N)$的,对于$M$次查询,最多移动$O(N + M\sqrt N)$次。
所以综上所述,莫队的复杂度是$O((N + M)\sqrt N)$

优雅的暴力,没错吧。

几道例题

SP3267 DQuery

q次询问,每次求$[L_i, R_i]$有多少数对

莫队的难点就在于写add和delete函数。对于这道题,我们要做的就是找到如何从$[L_1, R_1]$转移到$[L_2, R_2]$。

我们可以维护一个cnt数组,维护在一个区间中某个数出现了多少次。如果变成0,就表示出现次数是0;如果变成1,就表示新出现了。

于是就可切了。注意离散化。

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

using namespace std;

int a[30003], b[30003], cnt[30003], n, q, qwq, block, ans[300003];

struct node{
int id, L, R;
}query[300003];

inline void read(int& x) {
x = 0; char c = getchar();
while(!isdigit(c)) x = 0, c = getchar();
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
}

inline void output(int a) {
if(a > 9) output(a / 10);
putchar(a % 10 + '0');
}

inline void add(int pos) {
cnt[a[pos]]++;
if(cnt[a[pos]] == 1) ++qwq;
}

inline void rem(int pos) {
cnt[a[pos]]--;
if(cnt[a[pos]] == 0) --qwq;
}

bool cmp(node a, node b) {
if((a.L / block) == (b.L / block)) return a.R < b.R;
return a.L < b.L;
}

int main() {
read(n); for(int i = 1; i <= n; ++i) read(b[i]), a[i] = b[i];
block = (int)sqrt(1.0 * n);
sort(b + 1, b + n + 1);
int un = unique(b + 1, b + n + 1) - b;
for(int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + un + 1, a[i]) - b;
read(q); for(int i = 1; i <= q; ++i) read(query[i].L), read(query[i].R), query[i].id = i;
sort(query + 1, query + 1 + q, cmp);
int ln = 1, rn = 1; add(1);
for(int i = 1; i <= q; ++i) {
int lt = query[i].L, rt = query[i].R;
while(ln < lt) rem(ln), ++ln;
while(ln > lt) --ln, add(ln);
while(rn < rt) ++rn, add(rn);
while(rn > rt) rem(rn), --rn;
ans[query[i].id] = qwq;
}
for(int i = 1; i <= q; ++i) output(ans[i]), puts("");
return 0;
}

小Z的袜子

一切的起源。

有一个数列${a}$,有$q$次查询,查询$[L_i, R_i]$中任取两个数相同的概率。

在$[L, R]$取到相同的概率是

$$\frac{\sum^n{i = 1} C{cnti}^2}{C{len}^2}$$

其中$cnt_i > 2$。于是分母可以随便求一求,关键是怎样处理分子。

我们考虑一下从$R$到$R+1$发生了什么:首先$cnt_x++$,如若$cnt_x > 1$那么就相当于从$Cn^2$转移到了$C{n+1}^2$,加上了一个$C_n^1 = 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
60
61
#include <bits/stdc++.h>

using namespace std;

#define LL long long

int n, m, a[50003], cnt[50003], block;

LL ans;

struct node{
int L, R, id;
}query[50003];

struct fraction{
long long denominator, numerator;
}qwq[50003];

inline LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}

inline void add(int pos) {
cnt[a[pos]]++;
if(cnt[a[pos]] >= 2) ans += (cnt[a[pos]] - 1);
}

inline void rem(int pos) {
cnt[a[pos]]--;
if(cnt[a[pos]] >= 1) ans -= cnt[a[pos]];
}

bool cmp(node a, node b) {
if((a.L / block) == (b.L / block)) return a.R < b.R;
return a.L < b.L;
}

int main() {
scanf("%d%d", &n, &m);
block = (int)sqrt(2.0 * m / 3.0);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= m; ++i) scanf("%d%d", &query[i].L, &query[i].R), query[i].id = i;
sort(query + 1, query + 1 + m, cmp);
int ln = 1, rn = 1; add(1);
for(int i = 1; i <= m; ++i) {
int lt = query[i].L, rt = query[i].R;
while(ln < lt) rem(ln), ++ln;
while(ln > lt) --ln, add(ln);
while(rn < rt) ++rn, add(rn);
while(rn > rt) rem(rn), --rn;
if(ans == 0)
qwq[query[i].id].numerator = 0, qwq[query[i].id].denominator = 1;
else {
long long deno = (1LL * (rt - lt) * (rt - lt + 1)) / 2;
long long tmp = gcd(deno, ans);
qwq[query[i].id].numerator = ans / tmp, qwq[query[i].id].denominator = deno / tmp;
}
}
for(int i = 1; i <= m; ++i)
printf("%lld/%lld\n", qwq[i].numerator, qwq[i].denominator);
}

luogu4137 mex/RMQ Problem

给一个数列${a}$,q次查询,每次查在$[a_L, a_R]$范围未被覆盖的最小自然数

非常经典的题目。这题出的时候莫队还没有普及,如果到了现在也许会卡吧。不过莫队可以过……

这题的思路稍微有些迷。

首先我们用莫队维护一波值域。于是我们考虑从$[L_1, R_1]$转移到$[L_2, R_2]$。

我们发现,如果删除一个元素x,只需要比较$min(x, ans)$;而如果插入一个元素x,对小于x的元素没有影响,换言之,如果$x > ans$没有影响。如果$x = ans$的话呢?简单粗暴,直接暴力!

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

using namespace std;

#define LL long long

int n, m, a[200003], block, ans, result[200003], vis[200003];

struct node{
int L, R, id;
}query[200003];

inline LL gcd(LL a, LL b) {
return b ? gcd(b, a % b) : a;
}

inline void add(int pos) {
vis[a[pos]]++;
if(a[pos] == ans) {
int i = a[pos];
while(vis[i]) i++;
ans = i;
}
}

inline void rem(int pos) {
vis[a[pos]]--;
if(!vis[a[pos]]) ans = min(ans, a[pos]);
}

bool cmp(node a, node b) {
if((a.L / block) == (b.L / block)) return a.R < b.R;
return a.L < b.L;
}

int main() {
scanf("%d%d", &n, &m);
block = (int)sqrt(m);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= m; ++i) scanf("%d%d", &query[i].L, &query[i].R), query[i].id = i;
sort(query + 1, query + 1 + m, cmp);
int ln = 1, rn = 1; add(1);
for(int i = 1; i <= m; ++i) {
int lt = query[i].L, rt = query[i].R;
while(ln < lt) rem(ln), ++ln;
while(ln > lt) --ln, add(ln);
while(rn < rt) ++rn, add(rn);
while(rn > rt) rem(rn), --rn;
result[query[i].id] = ans;
}
for(int i = 1; i <= m; ++i)
printf("%d\n", result[i]);
return 0;
}

tyvj4866 摆摊

给数列${a}$,每次查$[a_L, a_R]$未被覆盖的最小的连续两个自然数

好像是一样的题。。

cf86D Powerful Array

给一个数列${a}$,每次查$[L, R]$中$cnt_{a_i}^2 \cdot a_i$

好像也是一样的题。。

Share