学习笔记 - 莫队算法

因为某次 ABC 的 F 题考了树上莫队,当时我做了 $80$ 分钟硬是没做出来……于是老师就把莫队提前讲了。

众所周知——莫队是优雅的暴力


前言

据说很多算法的发明是因为选手不知道正解,想要卡过去,然后就 AC 了……于是莫队也是如此诞生了,经过一堆严谨的证明,它的时间复杂度也是达到了 $O(n\sqrt n)$(普通莫队),出奇地优异。

但是它也有一些缺陷,比如一般的莫队,就只能离线;当然莫队也有大量的变种——例如带修莫队,回滚莫队,树上莫队等等……


普通莫队

莫队用于解决一类区间问题(或者你也可以看作是直角坐标系上的点在移动,后面会有这样一道题),它的实现基于 滑动窗口

不如以一道实际的问题引入——

例题 - D-query 【SPOJ

题意

给定长度为 $N$ 的序列,进行 $M$ 次询问,每次询问给定区间 $[L,R]$ ,求 $[L,R]$ 内不同值的个数。

数据规模:$1\leq N\le 30000$,$1\leq M\leq 200000$ ;

为了好好学莫队,我们这里把原题的数据规模改成:$1\leq M\leq 30000$,也就是说 $M,N$ 的数量级相同。

分析

(我知道学过主席树的reader们能砍掉这道题,但是我们冷静一下,想下别的方法)

当然不可能每个区间都扫描一遍,于是我们想到——假设我们现在求出了区间 $[L,R]$ 的答案,能不能利用这一答案求出 $[L’,R’]$ 的答案?

当然可以,就是滑动窗口。我们用数组 cnt 记录每个元素在当前窗口中出现了几次、用 ans 记录当前窗口的答案;当窗口向外扩展一个元素时,更新 cnt ,同时更新 ans,对于窗口缩小时也是一样的操作;这些修改都是 $O(1)$ (莫队喜欢 $O(1)$ 修改,不然常数变大后莫队就不优秀了)。

但是如果我们不对询问进行一些处理,当 $[L,R]$ 变到 $[L’,R’]$ 时,左右两个指针的移动在最坏情况下都是 $O(N)$ 的,于是滑窗就退化成了 $O(N^2)$(准确说是 $O(NM)$ ,因为有 $M$ 次询问,而每次询问都会有 $O(N)$ 的移动,但 $N,M$ 的数量级一样) !

我们开心地发现——询问是可以离线的,于是我们可以改变询问的顺序;一些 reader 们可能会想:把左端点排序,如果左端点相同再按右端点排序?然而这样的排序是无效的,我们可以构造出一串询问,使得左端点递增,但右端点在极左端和极右端徘徊……这样右端点的移动仍是 $O(N)$ 的,整体仍是 $O(N^2)$ ,没有效果。来看看我们优秀的莫队如何实现只将询问排序,就将时间复杂度降到 $O(N\sqrt N)$ 的:

考虑将原数列分块,确定块的大小为 $t=\left\lceil\sqrt N\right\rceil$ (我习惯上取整,没有严格证明),那么原数列就分为了长度约为 $\sqrt N$ 的 $\sqrt N$ 个区间;
对于一个询问,如果询问的左端点在某一区间内,我们称该询问属于该区间。
对于属于同一个区间的所有询问,我们把这些询问按右端点排序。
举个栗子:

gif1

em……

对,莫队的主体就这么做完了……排完序就开始滑窗了。想必各位也很懵逼为什么这样就是 $O(N\sqrt N)$ 了?

时间复杂度的证明

我们假设将原序列分为 $\frac nt$ 个长度为 $t$ 的块(假定 $n$ 是 $t$ 的倍数)。

那么对于属于同一个块的所有询问,左端点的每次移动是 $O(t)$ 的,因为左端点只会在块内移动;而右端点的所有移动是 $O(n)$ 的,因为同一个块的询问的右端点是不降序的,最多只会从极左端移动到极右端。

又因为左端点会移动 $m$ 次(每次询问都会移动),所以左端点移动的复杂度就是 $O(mt)$ ,在 $n,m$ 数量级相同的情况下,也就是 $O(nt)$ ;总共有 $\frac nt$ 个块,每个块内右端点移动的复杂度是 $O(n)$,所以右端点移动的总复杂度是 $O(\frac nt \cdot n)$ ;不难发现当 $t$ 取 $\sqrt n$ 时,总时间复杂度最小为 $O(n\sqrt 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
/*Lucky_Glass*/
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=30000,M=200000,NUM=1e6;
const double sqrtN=sqrt(30000);

struct QUERY{int Lef,Rig,id;};
bool cmpQUERY(const QUERY cpr1,const QUERY cpr2){return cpr1.Rig<cpr2.Rig;}

vector<QUERY> vec[(int)(sqrtN)+3];
int num[N+5],qry[M+5];
int n,m,ans;
int exi[NUM+5];

void Remove(int pos){
exi[num[pos]]--;
if(!exi[num[pos]]) ans--;
}
void Add(int pos){
exi[num[pos]]++;
if(exi[num[pos]]==1) ans++;
}

int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r;scanf("%d%d",&l,&r);
int knd=(int)(ceil(l/sqrtN)+1e-6);
vec[knd].push_back((QUERY){l,r,i});
}
for(int i=1;i<=sqrtN;i++)
sort(vec[i].begin(),vec[i].end(),cmpQUERY);
int lef=1,rig=0;
for(int i=1;i<=(int)ceil(sqrtN);i++){
for(int j=0;j<vec[i].size();j++){
while(lef<vec[i][j].Lef) Remove(lef++);
while(lef>vec[i][j].Lef) Add(--lef);
while(rig<vec[i][j].Rig) Add(++rig);
while(rig>vec[i][j].Rig) Remove(rig--);
qry[vec[i][j].id]=ans;
}
}
for(int i=1;i<=m;i++)
printf("%d\n",qry[i]);
return 0;
}

带修莫队

Q:不是说莫队不能修改吗?
A:只是说不能在线,谁说不能修改了……

仍然以一道题切入——支持单点修改!

例题 - Dynamic len(set(a[L:R])) 【UVa

题意

给定一个长度为 $N$ 的序列,对它按顺序进行 $M$ 次操作,操作有两个:

  1. 给定区间 $[L,R]$,求序列的不同元素个数;
  2. 指定一个位置 $x$ ,将该位置修改为 $y$。

分析

虽然题目要求按顺序,但是显然,由于题目直接提供了所有的操作(没有加密),我们仍然可以对操作进行排序。

那么我们能否继续像之前这样先按左端点分块,同一块中再按右端点排序呢?我们可以对每个询问再加一个时间戳 $t_i$,表示进行第 $i$ 次询问之前进行了多少次修改。在滑动窗口时,我们除了记录当前区间的左右端点,还要记录一个时间戳 $t$,表示当前的序列已经进行了 $t$ 次操作,如果发现 $t>t_i$ ,我们就撤回操作,如果 $t<t_i$ ,就继续进行操作

然而这样是否可以呢?考虑下面的情况:

假设询问全在一个块内,右端点不降序排列。

第一个询问的时间戳很小,比如 $t_1=0$;第二个时间戳很大,比如 $t_2=n$ ;第三个的时间戳又很小……(极小极大交替出现)

如果我们直接这样做,从第 $i$ 个操作转移到第 $i+1$ 个操作,区间移动虽然小,但是不得不 进行或撤回 $n$ 次修改。这样时间复杂度就又退化成了 $O(n^2)$

So……How to solve this problem?

从上面举的例子中,不难发现时间戳是除了左右端点外另外一个重要的标记——于是排序时不能只考虑左右端点。那么带修莫队就为我们提供了另外一种排序方案:

假设现在有两个询问 $[L_1,R_1,t_1],[L_2,R_2,t_2]$ ($t_i$ 是询问的时间戳)
如果 $L_1,L_2$ 不属于同一个块,则 $L$ 较小的排在前面;
如果 $L_1,L_2$ 属于同一个块,但是 $R_1,R_2$ 不属于同一个块,则 $R$ 小的排在前面;
如果 $L_1,L_2$ 和 $R_1,R_2$ 都在同一个块,则 $t$ 较小的排在前面。

写成这样一个 cmp 函数:

1
2
3
4
bool cmp(const QUERY A,const QUERY B){
//blk[i]表示i位置属于哪个块
return blk[A.L]==blk[B.L]? (blk[A.R]==blk[B.R]? A.t<B.t:A.R<B.R):A.L<B.L;
}

分析时间复杂度

设分块的大小为 $d$。

由于在同一个块内,左指针不保证有序,所以左指针块内转移一次是 $O(d)$ 的,每次都是这样转移,共有 $m$ 次,故左指针移动是 $O(dm)$ 的,也就是 $O(dn)$。

总共有 $\frac nd$ 个块,右端点每次移动的最坏时间复杂度是 $O(n)$ (即所有排序都按左端点排序,右端点乱序),所以右端点移动是 $O(\frac {n^2}d)$ 的。

只有左端点在同一个块、右端点也在同一个块时,才会按时间戳排序(可怜的时间戳),最坏情况下,每个块都有左端点,而左端点相同时,每个块内都有右端点,那么就会有 $(\frac nd)^2$ 的情况时间戳是乱序的,乱序就意味着 $O(n)$ ,故时间戳的时间复杂度是 $O(\frac {n^3}{d^2})$ 的。

综上,时间复杂度为 $O(dn+\frac {n^2}d+\frac{n^3}{d^2})$ ……(参考大米饼的博客,我也不知道为什么是 $d=n^\frac 23$)当 $d=n^{\frac 23}$ 时,时间复杂度最优为 $O(n^{\frac 53})$ 。

至于撤回、进行操作都是 $O(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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*Lucky_Glass*/
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=50000,SQRTN=230,NUM=1000000;

struct QUERY{int lef,rig,tim,id;};
struct MODIFY{int pos,val,las;};
bool cmpQUERY(const QUERY cur1,const QUERY cur2){
int blkL1=cur1.lef/SQRTN,blkL2=cur2.lef/SQRTN,
blkR1=cur2.rig/SQRTN,blkR2=cur2.rig/SQRTN;
return blkL1==blkL2? (blkR1==blkR2? cur1.tim<cur2.tim:cur1.rig<cur2.rig):cur1.lef<cur2.lef;
}

vector<QUERY> qry[SQRTN+5];
vector<MODIFY> mdy;
int num[N+5],cnt[NUM+5],_ans[N+5];
int n,m,nqry,ans,Lef,Rig,Mdy;

void Modify(int pos,int val){
if(Lef<=pos && pos<=Rig){
cnt[num[pos]]--;
if(cnt[num[pos]]==0) ans--;
cnt[num[pos]=val]++;
if(cnt[num[pos]]==1) ans++;
}
else num[pos]=val;
}
void Add(int pos){
cnt[num[pos]]++;
if(cnt[num[pos]]==1) ans++;
}
void Remove(int pos){
cnt[num[pos]]--;
if(cnt[num[pos]]==0) ans--;
}

int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&num[i]),_ans[i]=num[i];
for(int i=1;i<=m;i++){
char cmd[2]="";int cur1,cur2;
scanf("%s%d%d",cmd,&cur1,&cur2);cur1++;
if(cmd[0]=='Q'){
int knd=(cur1-1)/SQRTN;
qry[knd].push_back((QUERY){cur1,cur2,mdy.size()-1,nqry++});
}
else{
mdy.push_back((MODIFY){cur1,cur2,_ans[cur1]});
_ans[cur1]=cur2;
}
}
Lef=1,Rig=0,Mdy=-1;
for(int i=0;i<=SQRTN;i++){
sort(qry[i].begin(),qry[i].end(),cmpQUERY);
for(int j=0;j<qry[i].size();j++){
QUERY now=qry[i][j];
while(Mdy<now.tim) ++Mdy,Modify(mdy[Mdy].pos,mdy[Mdy].val);
while(Mdy>now.tim) Modify(mdy[Mdy].pos,mdy[Mdy].las),Mdy--;
while(Lef<now.lef) Remove(Lef++);
while(Lef>now.lef) Add(--Lef);
while(Rig<now.rig) Add(++Rig);
while(Rig>now.rig) Remove(Rig--);
_ans[now.id]=ans;
}
}
for(int i=0;i<nqry;i++) printf("%d\n",_ans[i]);
return 0;
}

回滚莫队

这是一个陌生的名词……似乎很少有人搞这玩意

例题在网上搜题解,全是 LCT、可持久化并查集((((((((((((っ・ω・)っ Σ(σ`・ω・´)σ 起飞!)

最后还是靠一个学长的博客学懂了这个方案。

不列题了,直接讲。

有时候我们维护当前区间的信息时,会用到一些不支持删除的数据结构,典型即 并查集。那么区间缩小时就会出事情……怎么办?我们发现对于(几乎)所有数据结构,我们只要记录下操作的上一步,我们就可以实现可回退化!典型仍然是 并查集

对于所有询问,我们仍然用普通莫队的方法排序,但是我们把滑窗改一下

对于属于第 $i$ 个块 的询问,把询问分两类——

  1. 左右端点属于一个块:这样的块我们直接枚举左端点到右端点的所有数,加入并查集中,统计答案,然后在并查集中撤回这些操作

  2. 左右端点不属于一个块:这些块一定是按右端点排序的 —— 那么,我们定义一个指针 $R$ 表示现在的并查集中储存了从 $i+1$ 块的第一个数到 $R$ 的所有数字,每次询问 $R$ 向右移,添加数字到并查集中。

    然后我们再把 从当前询问的左端点到第 $i$ 个块的最后一个数字 添加到并查集中。添加完后,并查集中就恰好是当前询问包含的数字了,于是统计答案。最后我们把 这些(指的是从当前询问的左端点到第 $i$ 个块的最后一个数字)操作撤回

再举个栗子:

em……

似乎一些reader不知道并查集怎么撤回?

观察并查集的代码,如果是一般的并查集,我们合并一次只会修改很少的变量,我们只要储存上一次修改是修改了哪些变量、这些变量原来的值就 Okey 了;撤回的时候就顺次恢复变量原来的值就可以了(Hint. 这些东西是可以用栈来储存的~)。

例题 - Chef and Graph Queries 【CodeChef

源代码

【点击展开/折叠代码
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
/*Lucky_Glass*/
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int SIZ=200000;

struct OPERATOR{int Fu,Fv,rnkFv;};

stack<OPERATOR> stk;
int ncase,npnt,nedg,nqry,ans,Rig;
int edg[SIZ+3][2],_ans[SIZ+3];

struct QUERY{int lef,rig,id,blg;}qry[SIZ+3];
bool cmpQUERY(const QUERY cpr1,const QUERY cpr2){return cpr1.blg==cpr2.blg? cpr1.rig<cpr2.rig:cpr1.blg<cpr2.blg;}
struct MERGESET{
int pre[SIZ+3],rnk[SIZ+3];
int FindPre(int u){return pre[u]==u? u:FindPre(pre[u]);}
int Merge(int u,int v,bool deltag){
int Fu=FindPre(u),Fv=FindPre(v);
if(Fu==Fv) return -1;
if(rnk[Fu]>rnk[Fv]) swap(Fu,Fv);
if(deltag) stk.push((OPERATOR){Fu,Fv,rnk[Fv]});
if(rnk[Fu]==rnk[Fv]) rnk[Fv]++;
pre[Fu]=Fv;
ans--;
return 1;
}
void Reset(int lim){
for(int i=1;i<=lim;i++)
pre[i]=i,rnk[i]=0;
}
}mrg;

void Delete(){
while(!stk.empty()){
OPERATOR opr=stk.top();stk.pop();
ans++;
mrg.rnk[opr.Fv]=opr.rnkFv;
mrg.pre[opr.Fu]=opr.Fu,mrg.pre[opr.Fv]=opr.Fv;
}
}

int main(){
scanf("%d",&ncase);
while(ncase--){
scanf("%d%d%d",&npnt,&nedg,&nqry);
int blk=(int)(ceil(sqrt(nedg))+1e-7);
for(int i=1;i<=nedg;i++){
int u,v;scanf("%d%d",&u,&v);
edg[i][0]=u;edg[i][1]=v;
}
for(int i=1;i<=nqry;i++){
int lef,rig;scanf("%d%d",&lef,&rig);
qry[i]=(QUERY){lef,rig,i,lef/blk+1};
}
sort(qry+1,qry+1+nqry,cmpQUERY);
qry[0].blg=-1;
for(int i=1;i<=nqry;i++){
if(qry[i].blg!=qry[i-1].blg){
ans=npnt;
mrg.Reset(npnt);
Rig=qry[i].blg*blk-1;
}
while(Rig<qry[i].rig)
Rig++,
mrg.Merge(edg[Rig][0],edg[Rig][1],false);
for(int j=qry[i].lef;j<=qry[i].rig && j<qry[i].blg*blk;j++)
mrg.Merge(edg[j][0],edg[j][1],true);
_ans[qry[i].id]=ans;
Delete();
}
for(int i=1;i<=nqry;i++)
printf("%d\n",_ans[i]);
}
return 0;
}

树上莫队

(木有学……留个坑在这儿,如果记得起来就填一填吧 Tab. 万年挖坑不填)


The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%