莫队 从零基础到入门 超详细

莫队是由莫涛大神提出，一种解决区间问题的骗分神器。一般来说询问是离线的。基础的莫队结构简单，复杂度优秀，理解之后会发现，没有想象中的那么高大上难。

前置芝士

1. 分块的思想
2. 一些 $STL$ 的使用
3. 树上求 $LCA$，欧拉序等操作
4. 离散化

$What$ $is$ 莫队

从一道例题来说。洛谷 P1972 [SDOI2009] HH的项链


这道题数据卡了莫队，不过弱化版可以过。

$1.$ 最暴力的方法，对于每一个区间 $O(n)$ 来扫，时间复杂度接近 $O(n^2)$，显然跑不起。

$2.$ 小优化，我们弄两个指针 $l$ 和 $r$，每次移动 $l$ 和 $r$ 直到与询问的区间重合，边移动边修改 $cnt$，最后输出答案。如果想到这个方法，那么离最后的莫队也不远了。
先来看为什么这个方法会被卡，这张图展现的淋漓尽致。

隔一个询问，$l$ 和 $r$ 就得满序列跑，最坏情况下移动 $O(nm)$ 次，也过不去。
那怎么办，难道没有办法了吗？这个时候，莫队算法出现了。

莫队算法的实现

$1.$ 预处理

莫队算法的核心是分块和排序。我们将大小为 $n$ 的序列分成 $\sqrt{n}$ 个块，从 $1$ 到 $\sqrt{n}$ 编号，然后根据这个查询区间进行排序。一种方法是把查询区间按照左端点所在块的序号排个序，如果左端点所在块相同，再按右端点排序。排序完再按照上面的移动两个指针操作。看起来似乎没啥用，但实际上，它的复杂度是 $O(\sqrt{n})$。具体证明可以去看大佬们的博客，我就简单说一下，排序复杂度是 $O(n\log n)$，左右指针的移动可以证明都是 $O(n\sqrt{n})$。

因此总时间复杂度为 $O(n\log n)+O(n\sqrt{n})+O(n\sqrt{n})=O(n\sqrt{n})$。

$2.$ 玄学优化技巧

大佬们会算每一个块多长的时候最优，但本蒟蒻不会，就默认块长为 $\sqrt{n}$。然而，最玄学的优化方法在排序上。具体来说，对于左端点在同一奇数块的区间，右端点按升序排序，反之降序。它的主要原理便是右指针跳完奇数块往回跳时在同一个方向能顺路把偶数块跳完，然后跳完这个偶数块又能顺带把下一个奇数块跳完。理论上主算法运行时间减半，实际情况有所偏差。

if(belong[a.l] == belong[b.l]){
   
	if(belong[a.l]&1) return a.r < b.r;
	return a.r > b.r;
}
return a.l < b.l;

至此，上面那道例题的代码就很好写出来了。

#include
#define re register
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^48) ; ch=getchar();}
	return x*f;
}
inline void print(int x){
   
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
const int M = 2e6+10;
int n,m,now;
int belong[M],ans[M],a[M],cnt[M];
struct query{
   
	int l,r,id;
}q[M];
bool cmp(query x,query y){
   
	return belong[x.l]==belong[y.l] ? x.r < y.r : belong[x.l] < belong[y.l];
}
void add(int pos){
   
	if(!cnt[a[pos]]) ++now;
	++cnt[a[pos]];
}
void del(int pos){
   
	--cnt[a[pos]];
	if(!cnt[a[pos]]) --now;
}
signed main(){
   
	n=read();
	int siz = sqrt(n),num = ceil((double)n/siz);
	for(re int i(1) ; i<=num ; ++i){
   
		for(re int j((i-1)*siz+1) ; j<=i*siz ; ++j){
   
			belong[j] = i;
		}
	}
	for(re int i(1) ; i<=n ; ++i) a[i] = read();
	m=read();
	for(re int i(1) ; i<=m ; ++i){
   
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id = i;
	}
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(re int i(1) ; i<=m ; ++i){
   
		int ql = q[i].l,qr = q[i].r;
		while(l < ql) del(l++);
		while(l > ql) add(--l);
		while(r < qr) add(++r);
		while(r > qr) del(r--);
		ans[q[i].id] = now;
	}
	for(re int i(1) ; i<=m ; ++i) print(ans[i]),putchar('\n');
	return 0;
}

莫队算法扩展——带修莫队

先给出例题。洛谷 P1903 [国家集训队] 数颜色 / 维护队列

前文中说过，一般来说，莫队算法适用于询问是离线的情况。但如果有修改，就真的不可以用莫队了吗？事实未必如此。这时候，带修莫队出现了。
具体来说，带修莫队的做法，就是把莫队加上一维，把修改操作编号，称为时间戳，查询操作的时间戳沿用之前最近修改操作的时间戳。跑主算法时定义当前时间戳为 $t$，对于每个查询操作，如果当前时间戳太大了，说明已经进行的修改操作比要求的多，就往前改回来，反之往后改。当查询区间与当前区间的左右端点，时间戳都相同的时候，才能认定区间重合，此时的答案即为本次查询的答案。
通俗来说，一般的莫队两个指针，带修莫队三个指针，移动方向从四个变成六个，其余操作和一般的莫队类似，具体看代码好理解。

#include
#define re register
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^48) ; ch=getchar();}
	return x*f;
}
inline void print(int x){
   
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
const int M = 1e6+10;
int n,m,cntq,cntc;
int cnt[M],belong[M],a[M],ans[M];
char s[M];
struct query{
   
	int l,r,tim,id;
	friend bool operator < (query x,query y){
   
		if(belong[x.l]^belong[y.l]) return belong[x.l] < belong[y.l];
		else if(belong[x.r]^belong[y.r]) return belong[x.r] < belong[y.r];
		else return x.tim < y.tim;
	}
}q[M];
struct modify{
   
	int pos,color,last;
}c[M];
signed main(){
   	
	n=read(),m=read();
	int siz = pow(n,2.0/3.0),num = ceil((double)n/siz);
	for(re int i(1) ; i<=num ; ++i){
   
		for(re int j((i-1)*siz+1) ; j<=i*siz ; ++j){
   
			belong[j] = i;
		}
	}
	for(re int i(1) ; i<=n ; ++i) a[i] = read();
	for(re int i(1) ; i<=m ; ++i){
   
		scanf("%s",s);
		if(s[0] == 'Q'){
   
			q[++cntq].l = read();
			q[cntq].r = read();
			q[cntq].tim = cntc;
			q[cntq].id = cntq;
		}
		else{
   
			c[++cntc].pos = read();
			c[cntc].color = read();
		}
	}
	sort(q+1,q+cntq+1);
	int l=1,r=0,tim=0,now=0;
	for(re int i(1) ; i<=cntq ; ++i){
   
		int ql=q[i].l,qr=q[i].r,qt=q[i].tim;
		while(l < ql) now -= !--cnt[a[l++]];
		while(l > ql) now += !cnt[a[--l