学习笔记 - 莫队算法 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - 莫队算法

发表于 更新于 分类于 Valine：

因为某次 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 ，欢迎提问~