莫队算法（普通，带修，回滚，树上）_树上莫队

这是用来复习的博客，不太建议想要初学普通莫队的人看这篇博客，不过要是想快速复习一遍，这个博客可能比较适合你。

莫队算法

莫队算法是一种通过对询问多关键字排序来降低时间复杂度的算法，当一些可离线题目满足 一个询问[l,r]的答案可以由[l-1,r]/[l+1,r]/[l,r-1]/[l,r+1]更新得到 时，可以考虑莫队算法。普通莫队不支持修改，不过如果是简单的修改可以用带修莫队/回滚莫队解决，至于树上问题则需要引入树上莫队。莫队实现简洁，应用面大，非常值得一学。

---

一、普通莫队

普通莫队需要将询问按左端点所属块为第一关键字、右端点位置为第二关键字进行排序，这里是奇偶化排序，即编号为奇数的块和编号为偶数的块编号单调性不同，能带来很可观的优化。通常来说按照Block=sqrt(n)定义块的大小即可。代码非常简洁，calc加了点小优化，这里贴上模板的代码。
洛谷P1494 [国家集训队] 小 Z 的袜子
注意一下奇偶化排序

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
typedef long long LL;
il int read(){
   
	int s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){
    if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){
    s=(s<<1)+(s<<3)+c-'0';c=getchar();}
	return s*w;
} 
il LL read_ll(){
   
	LL s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){
    if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){
    s=(s<<1)+(s<<3)+c-'0';c=getchar();}
	return s*w;
} 
const int N=5e4+10;
int n,m,c[N],ans[N][5],now_ans;
namespace Modui{
   
	int Block,ID[N],t[N];
	bool vis[N];
	struct node{
    int l,r,id;}Q[N]; int qt;
	il bool cmp(node c,node d){
   //奇偶化排序 
		if(ID[c.l]!=ID[d.l]) return ID[c.l]<ID[d.l];
		return ID[c.l]&1?c.r<d.r:c.r>d.r;
	}
	il void calc(int x){
   
		if(!vis[x]) now_ans+=t[c[x]],++t[c[x]];
		else --t[c[x]],now_ans-=t[c[x]];
		vis[x]^=1;
	}
} using namespace Modui;
il int gcd(int x,int y){
   
	if(x<y) swap(x,y);
	return y==0?x:gcd(y,x%y);
}
int main()
{
   
	n=read(),m=read(),Block=sqrt(n);
	for(re int i=1;i<=n;i++)
		c[i]=read(),ID[i]=(i-1)/Block+1;
	for(re int i=1;i<=m;i++){
   
		Q[++qt]=(node){
   read(),read(),i};
		if(Q[qt].l==Q[qt].r) ans[i][1]=0,ans[i][2]=1,--qt;
	}
	sort(Q+1,Q+1+qt,cmp);
	for(re int i=1,l=1,r=0;i<=qt;i++){
   
		while(l>Q[i].l) calc(--l);
		while(r<Q[i].r) calc(++r);
		while(l<Q[i].l) calc(l++);
		while(r>Q[i].r) calc(r--);
		ans[Q[i].id][1]=now_ans,ans[Q[i].id][2]=1LL*(Q[i].r-Q[i].l)*(Q[i].r-Q[i].l+1)>>1LL;
		int GCD=gcd(ans[Q[i].id][1],ans[Q[i].id][2]);
		ans[Q[i].id][1]/=GCD,ans[Q[i].id][2]/=GCD;
	}
	for(re int i=1;i<=m;i++) printf("%d/%d\n",ans[i][1],ans[i][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

一道练习题

---

二、带修莫队

带修莫队较于普通莫队有如下修改：

• 对询问加入时间戳t（即该操作在第t个修改操作之后），并添加一个时间指针，在移动指针时优先移动时间指针。
• 排序方式转变为：以左端点所在块为第一关键字，右端点所在块为第二关键字，时间戳为第三关键字进行排序
• 块长定义为n^2/3 ，总复杂度复杂度为O(n^5/3 )级别。

由上述定义可以发现，普通莫队由于没有修改，时间戳均为0，所以我们可以将普通莫队看作带修莫队的一个特殊情况。这也就是说，只有两个询问处于同一个时间点，我们才能放心大胆地移动指向询问的指针。我们发现，在移动完时间指针后，上一个询问与当前询问便会处于同一个时间点内，即两个询问之间没有修改，于是问题被转化成了普通莫队。（希望我说明白了）
至于时间复杂度分析，大部分时候都不会需要，想了解可以看看《信息学奥赛一本通 金牌导航》里面的讲解。

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

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
typedef long long LL;
il int read(){
   
	int s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){
    if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){
    s=(s<<1)+(s<<3)+c-'0';c=getchar();}
	return s*w;
} 
il LL read_ll(){
   
	LL s=0,w=1;char c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16