原理：https://www.cnblogs.com/Paul-Guderian/p/6933799.html
1.普通莫队
https://www.luogu.org/problemnew/show/P1494
对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。若该概率为0则输出0/1，否则输出的A/B必须为最简分数。
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
using namespace std;
typedef long long LL;
struct node {
int l,r,ID;
} qu[50005];
int be[50005],color[50005],sum[50005];
LL ans1[50005],ans2[50005],ans;
int l,r;
int n,m,bs;
bool cmp(node a,node b) {
if (be[a.l]!=be[b.l]) return a.l<b.l;
return a.r<b.r;
}
inline void update(int col,int val) {
if (val==-1) ans-=2*sum[col]-2,sum[col]--;
else ans+=2*sum[col],sum[col]++;
}
LL gcd(LL a,LL b) {
if (b==0) return a;
return gcd(b,a%b);
}
int main() {
scanf("%d%d",&n,&m);bs=sqrt(n);
for (int i=1;i<=n;i++) {scanf("%d",&color[i]);be[i]=(i-1)/bs+1;}
for (int i=1;i<=m;i++) {scanf("%d%d",&qu[i].l,&qu[i].r);qu[i].ID=i;}
sort(qu+1,qu+m+1,cmp);
l=1,r=0;//先把区间记空
for (int i=1;i<=m;i++) {
while (l>qu[i].l) update(color[l-1],1),l--;
while (r<qu[i].r) update(color[r+1],1),r++;
while (l<qu[i].l) update(color[l],-1),l++;
while (r>qu[i].r) update(color[r],-1),r--;
int ID=qu[i].ID;
ans1[ID]=ans;ans2[ID]=(LL)(qu[i].r-qu[i].l+1)*(qu[i].r-qu[i].l);
if (ans==0) ans2[ID]=1;
LL tmp=gcd(ans1[ID],ans2[ID]);
ans1[ID]/=tmp;ans2[ID]/=tmp;
}
for (int i=1;i<=m;i++) printf("%lld/%lld\n",ans1[i],ans2[i]);
return 0;
}
/*
-1:(sum-1)*(sum-2)-(sum)*(sum-1)=-2*sum+2
+1:(sum+1)*(sum)-(sum)*(sum-1)=2*sum
*/
2.带修莫队
https://www.luogu.org/problemnew/show/P1903
Q L R 代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
R P Col 把第P支画笔替换为颜色Col。 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
using namespace std;
typedef long long LL;
struct node1 {
int l,r,ti,ID;
} query[50005];
struct node2 {
int x,newc,oldc;
} change[50005];
int be[50005],color[50005],cc[50005],cnt[1000005];
int Ans[50005],ans;
int l,r,num,Time;
int n,m,bs;
bool cmp(node1 a,node1 b) {
if (be[a.l]!=be[b.l]) return a.l<b.l;
if (be[a.r]!=be[b.r]) return a.r<b.r;
return a.ti<b.ti;
}
inline void update1(int col,int val) {
cnt[col]+=val;
if (val==-1) ans-=(cnt[col]==0);
else ans+=(cnt[col]==1);
}
inline void update2(int po,int newc) {
if (l<=po && po<=r) update1(color[po],-1),update1(newc,1);
color[po]=newc;
}
int main() {
scanf("%d%d",&n,&m);bs=pow(n,0.666667);
for (int i=1;i<=n;i++) {
scanf("%d",&color[i]);
cc[i]=color[i];
be[i]=(i-1)/bs+1;
}
for (int i=1;i<=m;i++) {
char op=0;int x,y;
while (op!='Q'&&op!='R') op=getchar();
scanf("%d%d",&x,&y);
if (op=='Q') query[++num]=(node1){x,y,Time,num};
else change[++Time]=(node2){x,y,cc[x]},cc[x]=y;
}
sort(query+1,query+num+1,cmp);
Time=0;
l=1,r=0;//先把区间记空
for (int i=1;i<=num;i++) {
while (Time<query[i].ti) update2(change[Time+1].x,change[Time+1].newc),Time++;
while (Time>query[i].ti) update2(change[Time].x,change[Time].oldc),Time--;
while (l>query[i].l) update1(color[l-1],1),l--;
while (r<query[i].r) update1(color[r+1],1),r++;
while (l<query[i].l) update1(color[l],-1),l++;
while (r>query[i].r) update1(color[r],-1),r--;
Ans[query[i].ID]=ans;
}
for (int i=1;i<=num;i++) printf("%d\n",Ans[i]);
return 0;
}
3.树形莫队
用栈维护当前节点作为父节点，访问它的子节点，当栈顶到父节点的距离大于blocksize时，弹出这部分元素分为一块。根节点附近剩下的一坨点，最后再分一块。
用vis[x]判断是否在区间内，注意指针移动对LCA的影响。
关于指针移动的关键代码： 1
2
3
4
5
6
7
8
9void Run(int u) {
if (vis[u]) Data.Del(a[u]),vis[u]=0;
else Data.Add(a[u]),vis[u]=1;
}
void move(int x,int y) {
if (deep[x]<deep[y]) swap(x,y);
while (deep[x]>deep[y]) Run(x),x=fa[x][0];
while (x!=y) Run(x),Run(y),x=fa[x][0],y=fa[y][0];
}
