【算法笔记】莫队算法（基础莫队，带修莫队，回滚莫队，树上莫队，二次离线莫队）_在线莫队代码

整理的算法模板合集： ACM模板

来这里学习莫队以及神奇的证明：莫队算法 --算法竞赛专题解析（26）

我们首先考虑双指针的暴力法，发现很容易就会被卡成$O(nm)$，这时候我们的莫队出现了，莫队说，我可以像变魔术一样，把$O(nm)$的算法通过一个神奇的排序方式，使得我们最坏的情况下，时间复杂度也会非常优秀：$O(n\sqrt{n})$。

莫队算法是一个离线的算法，我们先将所有的询问全部存下来，然后排序。我们的每一个询问都是一个左右区间，$(l,r)$

我们的排序方法为双关键字排序，我们将每个询问的左端点 $l$ 分块。
第一关键字为左端点分块的编号从小到大，第二关键字为右端点的下标从小到大。

编码时，还可以对排序做一个小优化：奇偶性排序，让奇数块和偶数块的排序相反。例如左端点L都在奇数块，则对R从大到小排序；若L在偶数块，则对R从小到大排序（反过来也可以：奇数块从小到大，偶数块从大到小）。

1. 基础莫队

AcWing 2492. HH的项链

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>

using namespace std;
const int N = 50007, M = 200007, S = 1000007;

int n, m;
int w[N];
int block;
int cnt[S];
int ans[M];

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

int get_block(int x){
   
    return x / block;//这里是从0开始
}

bool cmp(const Query& x, const Query& y){
   
    int a = get_block(x.l);
    int b = get_block(y.l);
    if(a != b)return a < b;
    return x.r < y.r;
}

void add(int x, int &res){
   
    if(cnt[x] == 0)res ++ ;
    cnt[x] ++ ;
}

void del(int x, int &res){
   
    cnt[x] -- ;
    if(cnt[x] == 0)res -- ;
}

int main()
{
   
    scanf("%d", &n);
    
    for(int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    
    scanf("%d", &m);
    block = sqrt((double)n * n / m);//1488 ms
    //block = sqrt(n);             //1700 ms
    
    for(int i = 0; i < m; ++ i){
   
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {
   i, l, r};
    }
    sort(q, q + m, cmp);
    
    for(int k = 0, i = 0, j = 1, res = 0; k < m; ++ k){
   
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while(i < r)add(w[ ++ i], res);
        while(i > r)del(w[i -- ], res);
        while(j < l)del(w[j ++ ], res);
        while(j > l)add(w[ -- j], res);//注意这里的细节，自己模拟一遍
        ans[id] = res;
    }
    
    for(int i = 0; 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
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

玄学优化版，成功卡过了洛谷上的这道题

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cmath>

using namespace std;
const int N = 1000007, M = 1000007, S = 1000007;

int n, m;
int w[N];
int block;
int cnt[S];
int ans[M];

inline int read()
{
   
    int x = 0, f = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0'){
   if(ch == '-')f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9'){
   x = x * 10 + ch - '0';ch = getchar();}
    return x * f;
}

inline void write(int res){
   
	if(res<0){
   
		putchar('-');
		res=-res;
	}
	if(res>9)
		write(res/10);
	putchar(res%10+'0');
}

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

inline 
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