墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
输入格式：
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
输出格式：
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
输入样例#1： 复制
6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6输出样例#1： 复制
4 4 3 4对于100%的数据，N≤50000，M≤50000，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
本题可能轻微卡常数
带修莫队和普通莫队的区别在于多加了一个时间 多了俩个时间的while
#include<bits/stdc++.h> using namespace std; const int maxn=5e4+5; int Be[maxn],col[maxn],x,y,n,m,color[maxn*100],Ans[maxn],ans,l=1,r,T,unit,t,Time,now[maxn]; char sign; struct node { int l,r,Tim,ID,sum; } q[maxn]; struct aa { int pos,New,Old; } c[maxn]; bool cmp(node a,node b) { return Be[a.l]==Be[b.l]?(Be[a.r]==Be[b.r]?a.Tim<b.Tim:a.r<b.r):a.l<b.l; }//分块排序 bool Cmp(node x,node y) { return x.ID<y.ID; }//按id大小排序 准备输出 void revise(int x,int d) { if(color[x]!=0) ans--;//只有在这个颜色有的时候才消去一下影响 color[x]+=d; if(color[x]!=0) ans++;//只有在这个颜色有的时候才加上影响 } void gogoing(int x,int d) { if(l<=x&&x<=r)//如果更新时间的时候这个点在要求区间中 { revise(d,1);//加上d revise(col[x],-1);//消去col[x]; } col[x]=d;//更改 } int main() { scanf("%d%d",&n,&m); unit=pow(n,0.666666);//最优分块方法 for(int i=1; i<=n; i++) { scanf("%d",&col[i]); Be[i]=i/unit+1; now[i]=col[i]; } for(int i=1; i<=m; i++) { scanf(" %c %d%d",&sign,&x,&y); if(sign=='Q') { q[++t]=(node) { x,y,Time,t };//存数 } if(sign=='R') { c[++Time]=(aa) { x,y,now[x] }; now[x]=y; }//存数 } sort(q+1,q+t+1,cmp); for(int i=1; i<=t; i++) { //按时间和左右边界进行美丽的暴力 while(T<q[i].Tim) gogoing(c[T+1].pos,c[T+1].New),T++; while(T>q[i].Tim) gogoing(c[T].pos,c[T].Old),T--; while(l<q[i].l)revise(col[l],-1),l++; while(l>q[i].l)revise(col[l-1],1),l--; while(r<q[i].r)revise(col[r+1],1),r++; while(r>q[i].r)revise(col[r],-1),r--; q[i].sum=ans;//存答案 } sort(q+1,q+t+1,Cmp); for(int i=1; i<=t; i++) { printf("%d\n",q[i].sum); } return 0; }
