抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

莫队学习笔记

发布于：2019年10月1日

其实这是一篇咕了很久的学习笔记。

本人比较喜欢莫队这种根号算法。

以上是博主瞎扯淡，下面正文开始。

莫队基本原理

何为莫队，莫队可不是一个队列，他是以集训队大佬莫涛为名的暴力算法（又称对询问分块）。

其实思路比较简单，我们现在得到了查询[l1,r1][l_1,r_1]的答案，想要通过比较少的代价获得[l2,r2][l_2,r_2]的答案，怎么办。

一个很简单的思路，就是先把l1l_1移动到l2l_2的位置，同时从当前状态减去[l1,l2−1][l_1,l_2-1]对应的元素，再把r1r_1移动到r2r_2的位置，从当前状态加上[r1+1,r2][r_1+1,r_2]对应的元素。

可能你会比较懵逼，什么叫做加上，减去？

以区间询问不同的数的个数为例，加上这个数的同时更新cnt[]cnt[]数组，还要更新答案，如下：

1
2
3
4
inline void Add(int x){
    ++cnt[x];
    if (cnt[x]==1) ans++;//这个数是最新出现的
}

减去也是同理

1
2
3
4
inline void Del(int x){
    --cnt[x];
    if (cnt[x]==0) ans--;//这个数被减没了
}

核心代码：

1
2
3
4
while (l<Q[i].l) Del(seq[l++]);
while (l>Q[i].l) Add(seq[--l]);
while (r<Q[i].r) Add(seq[++r]);
while (r>Q[i].r) Del(seq[r--]);

好了，貌似这样更新答案，能少很多运算过程。

No!No!，考虑这样的询问：

l1=1,r1=1l_1=1,r_1=1

l2=n,r2=nl_2=n,r_2=n

l3=1,r3=1l_3=1,r_3=1

……

显然每次询问是O(n)O(n)的，加上询问变成O(nm)O(nm)的，gg。

这时，莫涛大佬不禁说：“对询问离线，然后排序！”

经过大佬的指点，很多人都可以口胡出一个貌似时间复杂度正确的解法：

对询问离线，然后按照左端点为第一关键字，右端点为第二关键字排序！

代码如下：

1
2
3
4
inline bool operator < (const Query &A,const Query &B){
	if (A.l==B.l) return A.r<B.r;
    else return A.l<B.l;
}

然鹅，这个是错误的。

考虑这样的询问：

l1=1,r1=1l_1=1,r_1=1

l2=2,r2=nl_2=2,r_2=n

l3=3,r3=1l_3=3,r_3=1

l4=4,r4=nl_4=4,r_4=n

……

每次询问还是O(n)O(n)。

这下怎么搞？

莫涛大佬有一个非常毒瘤的ideaidea。

考虑分块，大小为n\sqrt n，

对询问离线，然后按照左端点所在块编号为第一关键字排序，右端点为第二关键字排序。

代码如下：

1
2
3
4
inline bool operator < (const Query &A,const Query &B){
	if (id[A.l]==id[B.l]) return A.r<B.r;
	else return id[A.l]<id[B.l];
}

这样为什么是对的呢？

假设我们整体来看，会发现只要左端点每次移动的距离不会超过2×n2 \times \sqrt n（可能是在同一个块里面移动，也有可能是从一个块跳到相邻的块），然后右端点整个询问全部加起来也不会移动超过nnn\sqrt n次（因为左端点在同一个块的时候，右端点移动的距离不会超过nn，而且只有n\sqrt n个块），均摊n\sqrt n。

于是发现询问的平均时间复杂度为O(n)O(\sqrt n)。

妙不妙？

优化方法

同时，我还要介绍莫队的优化方法（奇偶性排序）。

考虑我们左端点从一个块跳到右边相邻的块的过程，在左端点在前一个块的时候，我们的右端点已经到达了一个编号较大的位置，但是左端点一跳到相邻的块，右端点就要跳到一个编号较小的位置，这样虽然不影响时间复杂度，但是总觉得有些浪费，于是我们想，相邻的块和前一个块右端点按照不同的方式排序（比如前一个块从小到大，后一个块从大到小），常数就可以减少。

代码如下：

1
2
3
4
5
6
7
inline bool operator < (const Query &A,const Query &B){
	if (id[A.l]==id[B.l]){
		if (id[A.l]&1) return A.r<B.r;
		else return A.r>B.r;
	}
	else return id[A.l]<id[B.l];
}

按照这种方法排序，听说常数能够减少很多。

下面进入快乐的刷题时间：

普通莫队

先从简单的普通莫队练起。

（HH的项链卡莫队，所以没有放进例题）

例题1

P3901 数列找不同

只要区间出现次数超过22的数就可以搞定了（代码中是cnt2cnt2）。

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>
#define MAXN 100005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct Query{
    int l,r,id;
}q[MAXN];
int pos[MAXN];
inline bool operator < (const Query &a,const Query &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));//奇偶性排序的压行写法
}
int a[MAXN],cnt[MAXN],cnt2;
inline void Add(int x){
    ++cnt[x];
    if (cnt[x]==2) cnt2++;
}
inline void Del(int x){
    --cnt[x];
    if (cnt[x]==1) cnt2--;
}
int Ans[MAXN];
int main(){
    int n=read(),m=read();
    int Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        a[i]=read();
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        q[i]=Query{read(),read(),i};
    }
    sort(q+1,q+1+m);
    int l=1,r=0;
    for (register int i=1;i<=m;++i){
		while (l<Q[i].l) Del(seq[l++]);
		while (l>Q[i].l) Add(seq[--l]);
		while (r<Q[i].r) Add(seq[++r]);
		while (r>Q[i].r) Del(seq[r--]);
        Ans[q[i].id]=(cnt2==0);
    }
    for (register int i=1;i<=m;++i){
        puts(Ans[i]?"Yes":"No");
    }
}

例题2

P1494 [国家集训队]小Z的袜子

设[L,R][L,R]所有袜子构成的集合是SS，设f(x)=x×(x−1)/2f(x)=x \times (x-1)/2，显然$ans=\sum _{x \in S} (f(cnt(x))) / f(L-R+1) $。

注意到可以消掉那个22，并且拆开x×(x−1)x \times (x-1)，变成(∑x∈S(cnt(x)2)−∑x∈Scnt(x))/(R−L+1)×(R−L)(\sum_{x \in S}(cnt(x)^2)-\sum_{x \in S} cnt(x)) / (R-L+1) \times (R-L)

注意到∑x∈Scnt(x)=R−L+1\sum _{x \in S} cnt(x) = R-L+1。

于是我们要求的就是∑x∈S(cnt(x)2)\sum_{x \in S}(cnt(x)^2)。

可以大力算出来。

（好久以前的代码，码风请原谅）

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 50005
#define int long long
using namespace std;
int num[MAXN];
struct fen{
    int a,b;
    inline void yue(){
        int g=__gcd(a,b);
        a/=g,b/=g;
    }
}ans[MAXN];
int pos[MAXN];
struct query{
    int l,r,id;
    inline int len(){
        return r-l+1;
    }
}querys[MAXN];
bool operator < (const query &a,const query &b){
    if (pos[a.l]==pos[b.l]){
        return a.r<b.r;
    }
    else{
        return a.l<b.l;
    }
}
int cnt[MAXN];
inline void Change(int &curans,const int &id,const int &val){
    curans-=cnt[num[id]]*cnt[num[id]];
    cnt[num[id]]+=val;
    curans+=cnt[num[id]]*cnt[num[id]];
}
#undef int
int main(){
#define int long long
    int n,m;
    scanf("%lld%lld",&n,&m);
    int sz=sqrt(n);
    for (int i=1;i<=n;++i){
        pos[i]=(i-1)/sz+1;
    }
    for (int i=1;i<=n;++i){
        scanf("%lld",&num[i]);
    }
    for (int i=1;i<=m;++i){
        scanf("%d%d",&querys[i].l,&querys[i].r);
        querys[i].id=i;
    }
    sort(querys+1,querys+1+m);
    int l=1,r=0;
    int curans=0;
    for (int i=1;i<=m;++i){
        while (r<querys[i].r) Change(curans,++r,1);
        while (r>querys[i].r) Change(curans,r--,-1);
        while (l>querys[i].l) Change(curans,--l,1);
        while (l<querys[i].l) Change(curans,++l,-1);
        if (querys[i].l==querys[i].r){
            ans[querys[i].id].a=0,ans[querys[i].id].b=1;
        }
        else {
            ans[querys[i].id].a=curans-(querys[i].len());
            ans[querys[i].id].b=querys[i].len()*(querys[i].len()-1);
            ans[querys[i].id].yue();
        }
    }
    for (int i=1;i<=m;++i){
        printf("%lld/%lld\n",ans[i].a,ans[i].b);
    }
}

有技巧的莫队

莫队算法套路千变万化，有必要掌握几个常用的技巧。

例题3

P3674 小清新人渣的本愿

莫队还能和bitset\rm bitset结合？

这道题需要运用一些小技巧。

设现在莫队指针l,rl,r维护的区间中不同的数组成的集合为a1,a2,a3...an{a_1,a_2,a_3...a_n}

我们维护这样一个bitset\rm bitsetss，对于aia_i，s[ai]=1s[a_i]=1

Query1

考虑如何实现查询x−y=nx-y=n，发现x=y+nx=y+n，所以对于所有出现在aa集合中的数aia_i，查询ai+na_i+n在aa集合中有没有出现即可。

这个可以通过操作(s \text{&} (s<<n)).any()实现，其中any()any()查询bitset\rm bitset中有没有11

Query2

考虑实现查询x+y=nx+y=n，其实本质和上面一种一样，就是化成x=−y+nx=-y+n，再维护一个下标为−ai-a_i的bitset\rm bitsets1s1即可，但是这样做会有一个严重的问题，bitset\rm bitset下标不能为负数。

考虑给−ai-a_i加上一个很大的正数NN，这里使用MAXN−1MAXN-1

把s1s1维护的数变为集合bi=−ai+Nb_i=-a_i+N，原来的式子化成x=−y+N+n−Nx=-y+N+n-N

查询的操作转换成查询bi+n−Nb_i+n-N有没有在aia_i中出现。

注意到n−Nn-N为负数，于是左移n−Nn-N转换成右移N−nN-n。

通过操作(s \text{&} (s1>>(N-n))).any()实现。

Query3

这个比较简单，将xy=nxy=n转换成x=\frac{n\dfrac，于是O(\sqrt{n})枚举枚举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
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
bitset<MAXN>s,s1;
int a[MAXN],cnt[MAXN],pos[MAXN];
inline void Add(int x){
    if (cnt[x]++==0) s[x]=1,s1[MAXN-1-x]=1;
}
inline void Del(int x){
    if (--cnt[x]==0) s[x]=0,s1[MAXN-1-x]=0;
}
struct Query{
    int opt,l,r,x,id;
}q[MAXN];
inline bool operator < (const Query &a,const Query &b){
	return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);
}
int ans[MAXN];
int main(){
    int n=read(),m=read();
    int Size=(int)(sqrt(n));
    for (register int i=1;i<=n;++i){
        a[i]=read();
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        int opt=read(),l=read(),r=read(),x=read();
        q[i]=Query{opt,l,r,x,i};
    }
    sort(q+1,q+1+m);
    int l=1,r=0;
    for (register int i=1;i<=m;++i){
        while (l<q[i].l) Del(a[l++]);
        while (l>q[i].l) Add(a[--l]);
        while (r>q[i].r) Del(a[r--]);
        while (r<q[i].r) Add(a[++r]);
        if (q[i].opt==1){
            ans[q[i].id]=(s&(s<<(q[i].x))).any();
        }
        else if (q[i].opt==2){
            ans[q[i].id]=(s&(s1>>(MAXN-1-q[i].x))).any();
        }
        else if (q[i].opt==3){
            for (register int j=1;j*j<=q[i].x;++j){
                if (q[i].x%j!=0) continue;
                if (s[j]&&s[q[i].x/j]){
                    ans[q[i].id]=1;
                    break;
                }
            }
        }
    }
    for (register int i=1;i<=m;++i){
        puts(ans[i]==1?"hana":"bi");
    }
}

例题4

U80812 相同颜色对

莫队可以套上容斥，达到44个指针$\to $$2$个指针的效果。

题解

例题5

P5071 [Ynoi2015]此时此刻的光辉

小范围前缀和，大范围莫队是哪个毒瘤想出来的？

题解

例题6

P4689 [Ynoi2016]这是我自己的发明

子树拍平，变成“上树莫队”。

题解

带修莫队

只要再维护一个修改的指针就可以辣！

例题7

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

我们来想一想莫队如何支持修改，我们把查询和修改操作离线下来，如图，将查询标为蓝色，将修改标为红色。

假设我们要查询六号查询的答案，考虑哪些修改会影响答案，肯定是在六号之前的修改，且这些修改的下标indind在六号查询的区间[l,r][l,r]之内，如图中22，44号修改，要把这些修改全部做完，才能得到正确的结果。

所以，我们在每个查询中除了l,r,idl,r,id，还要记录一个lastlast，代表最近的修改位置，查询时，我们要把lastlast前面的修改全部做完，如代码。

1
2
3
struct Query{
    int l,r,id,last;//last为最近的修改位置
}q[MAXN];

同时记录每个修改操作，只用记录修改的下标indind和修改的值valval即可。

1
2
3
struct Update{
    int ind,val;//把ind修改成val
}u[MAXN];

为了做带修莫队，我们记录一个指针pp ，代表我们把[1,p][1,p]的修改操作全部做完了，做莫队的时候，除了常规的莫队操作，还要有下面两行：

1
2
while (p<q[i].last) Upd(++p,i);
while (p>q[i].last) Upd(p--,i);

如果操作做少了，那么我们调用Upd(++p,i)Upd(++p,i)，多做一次操作，如果操作做少了，我们调用Upd(p−−,i)Upd(p--,i)，撤销一次操作。

那么这个撤销怎么弄呢？

很容易想到的是，我们在每个UpdateUpdate结构体里面再多存一个flagflag，代表当前是增加操作还是撤销操作，如果是撤销操作，那么我们删除u[p].valu[p].val，加入num[u[p].ind]num[u[p].ind]，每次操作后，flagflag取反，即撤销操作变成加入操作，加入操作变成撤销操作。

但是呢，这样代码量不但增加，常数也增多了，这道题你可能TLETLE，考虑有没有更加简洁优美的方法替代flagflag。

有！

我们每次操作之后，将num[u[p].ind]num[u[p].ind]和u[p].valu[p].val对调，我们再撤销回去的时候，就相当于将u[p].valu[p].val改成num[u[p].ind]num[u[p].ind]，非常巧妙。

实现如下，注意只有修改的下标在现在查询范围之内才会对答案造成影响：

1
2
3
4
5
6
inline void Upd(int p,int i){
    if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
        Del(num[u[p].ind]),Add(u[p].val);//修改，先删去原有的，再加进val
    }
    swap(num[u[p].ind],u[p].val);
}

注意要加sortsort，（虽然我不加sortsort也卡过）

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 <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct Query{
    int l,r,id,last;//last为最近的修改位置
}q[MAXN];
struct Update{
    int ind,val;//把ind修改成val
}u[MAXN];
int pos[MAXN],num[MAXN];
inline bool operator < (const Query &x,const Query &y){
	if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
	if(pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];
	return x.last<y.last;
}
int cntq,cntu;
inline char gc(){
    char ch=getchar();
    while (ch!='Q'&&ch!='R') ch=getchar();
    return ch;
}
int ans,Ans[MAXN];
static int cnt[MAXN];
#define Add(x) (++cnt[x]==1)?++ans:0
#define Del(x) (--cnt[x]==0)?--ans:0
inline void Upd(int p,int i){
    if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
        Del(num[u[p].ind]),Add(u[p].val);//修改，先删去原有的，再加进val
    }
    swap(num[u[p].ind],u[p].val);
}
inline void Print(register int x){
    if (x>=10ll) Print(x/10ll);
    putchar(x%10ll+48ll);
}
inline void print(register int x,const char ch){
    if (x<0){x=-x,putchar('-');}
    if (x==0){putchar('0');putchar(ch);return ;}
    Print(x);putchar(ch);
}
int main(){
    int n=read(),m=read();
    const int Size=pow(n,(double)0.666666666);
    for (register int i=1;i<=n;++i){
        num[i]=read();
    }
    for (register int i=1;i<=m;++i){
        char opr=gc();
        if (opr=='Q') q[++cntq]=Query{read(),read(),cntq,cntu};
        else u[++cntu]=Update{read(),read()};
    }
    for (register int i=1;i<=n;++i){
        pos[i]=(i-1)/Size+1;
	}
    sort(q+1,q+1+cntq);
    register int l=1,r=0;
    register int p=0;//修改的操作
    for (register int i=1;i<=m;++i){
        while (l<q[i].l) Del(num[l++]);
        while (l>q[i].l) Add(num[--l]);
        while (r<q[i].r) Add(num[++r]);
        while (r>q[i].r) Del(num[r--]);
        while (p<q[i].last) Upd(++p,i);
        while (p>q[i].last) Upd(p--,i);
        Ans[q[i].id]=ans;
    }
    for (register int i=1;i<=cntq;++i){
        print(Ans[i],'\n');
    }
}

树上莫队

普通莫队是在一个一个地移动指针，树上莫队是一个一个爬节点—-SXYZ巨佬

例题8

BZOJ苹果树

这才是真的树上莫队。

题解

例题9

SP10707 COT2 - Count on a tree II

和上面那题几乎一样，这里只放代码：

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
#include <bits/stdc++.h>
#define MAXN 200005
#define MAXM 17
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
    G[u].push_back(v);
}
int c[MAXN];//每个点的颜色
int anc[MAXN][MAXM],dep[MAXN];
int euler[MAXN];//欧拉序(出栈入栈都要记录)
int L[MAXN],R[MAXN];//左右端点
int tot;
void dfs(int u,int father){
    dep[u]=dep[father]+1;
    anc[u][0]=father;
    euler[L[u]=++tot]=u;
    for (register int i=1;i<MAXM;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
    for (register int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if (v!=father) dfs(v,u);
    }
    euler[R[u]=++tot]=u;
}
inline int LCA(int u,int v){
    if (dep[u]<dep[v]) swap(u,v);
    for (register int i=MAXM-1;i>=0;--i){
        if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
    }
    if (u==v) return u;
    for (register int i=MAXM-1;i>=0;--i){
        if (anc[u][i]!=anc[v][i]){
            u=anc[u][i],v=anc[v][i];
        }
    }
    return anc[u][0];
}

int n,m;
inline void discrete(){
    int tempc[MAXN];
    for (register int i=1;i<=n;++i) tempc[i]=c[i];
    sort(tempc+1,tempc+1+n);
    for (register int i=1;i<=n;++i){
        c[i]=lower_bound(tempc+1,tempc+1+n,c[i])-tempc;
    }
}

int b[MAXN];//块编号
struct Query{
    int u,v,lca,id;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){//莫队的玄学优化
    return (b[A.u]^b[B.u])?b[A.u]<b[B.u]:((b[A.u]&1)?A.v<B.v:A.v>B.v);
}
int inq[MAXN];//在不在莫队维护的范围内
int ans,cnt[MAXN];
inline void Update(int i){//相应地加上/减去元素
    if (!inq[i]){//加上
        cnt[c[i]]++;
        if (cnt[c[i]]==1) ans++;
        inq[i]=true;
    }
    else {
        cnt[c[i]]--;
        if (cnt[c[i]]==0) ans--;
        inq[i]=false;
    }
}
int Ans[MAXN];
inline Query make_q(int u,int v,int lca,int id){
    Query temp;
    temp.id=id;
    temp.u=u,temp.v=v;
    temp.lca=lca;
    return temp;
}
int main(){
    n=read(),m=read();int Size=sqrt(n);//块大小
    for (register int i=0;i<MAXN;++i){
        b[i]=i/Size+1;
    }
    for (register int i=1;i<=n;++i){
        c[i]=read();
    }
    discrete();
    for (register int i=1;i<n;++i){
        int u=read(),v=read();
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs(1,1);
    for (register int i=1;i<=m;++i){
        int u=read(),v=read();
        if (L[u]>L[v]) swap(u,v);//保证这条链是从左往右
        int lca=LCA(u,v);
        if (u==lca) q[i]=make_q(L[u],L[v],0,i);//u为这条链的顶点
        else q[i]=make_q(R[u],L[v],lca,i);
    }
    sort(q+1,q+1+m);
    int l=1,r=0;//模仿STL队列
    for (register int i=1;i<=m;++i){
        while (l<q[i].u) Update(euler[l++]);
        while (l>q[i].u) Update(euler[--l]);
        while (r<q[i].v) Update(euler[++r]);
        while (r>q[i].v) Update(euler[r--]);
        if (q[i].lca) Update(q[i].lca);//注意处理lca
        Ans[q[i].id]=ans;
        if (q[i].lca) Update(q[i].lca);
    }
    for (register int i=1;i<=m;++i){
        printf("%d ",Ans[i]);
    }
}

回滚莫队

回滚莫队这个名字好可爱呀！

有时候加上一个元素可以O(1)O(1)算出答案，但是减去一个元素不能O(1)O(1)算出，而一些加上或者减去时间复杂度O(log⁡n)O(\log n)的算法会被卡成狗，此时回滚莫队就派上用场了。

事实上就是ll端点移动的部分每一次都重新计算。

分只增不减和只减不增两个种类。

例题10

AT1219 歴史の研究

回滚莫队的基础题。

题解

例题11

BZOJ 4358 permu

我的解法绝对是全网最易懂的。

题解

例题12

P4137 Rmq Problem / mex

虽然权值线段树也是可做的。

只减不增的回滚莫队（虽然我智障写了一个只增不减的版本）

题解

例题13

SP20644 ZQUERY - Zero Query

另一种鬼畜的莫队套路。

题解

分块+莫队

分块O(n)O(\sqrt n)的怎么会跑得比O(log⁡n)O(\log n)的线段树/树状数组快？

结合莫队算法的特性，发现有时候使用分块+莫队会使得复杂度少一个log⁡\log避免被卡。

例题14

P4867 Gty的二逼妹子序列

洛谷数据水，O(nnlog⁡n)O(n \sqrt n \log n)的做法也可以卡过。

但是这个就是一个$\log $的差距：

题解

例题15

P4396 [AHOI2013]作业

一样的套路呀

题解

总结：莫队是一种扩展性极强的算法，而且常数小极难被卡，缺点是必须在线，强制在线就gg了（虽然有在线莫队这种东西）。掌握还是非常必要的。

相关文章
AT1219 歴史の研究BZOJ 4358 permuP1903 [国家集训队]数颜色 / 维护队列P3674 小清新人渣的本愿基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/3be44324.html

更新于：2022年6月14日

莫队

评论