墨墨购买了一套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支画笔中共有几种不同颜色的画笔。
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
4
4
3
4
分析：
一开始不会打带修改莫队，就直接打了个不带分块的普通莫队，然后在洛谷水了40分，然后看了某位大佬的博客以后，会了带修改莫队，结果被洛谷数据卡常卡了一个小时，这数据也太可怕了吧。。。给出数据的人跪了Orz。。。（BZOJ上的数据一遍就过了。。。）把能用的优化都丢进去了，然后8000+ms过的。。。如果不会带修改莫队，请参考这位大佬的博客。这里蒟蒻就只放代码了。
Code：
1 //It is made by HolseLee on 31st May 2018 2 //Luogu.org P1903 3 #include<bits/stdc++.h> 4 #define swap(x,y) x^=y,y^=x,x^=y 5 using namespace std; 6 const int N=5e4+7; 7 const int M=1e6+7; 8 int n,m,s,L,R,tot,ans[N]; 9 int a[N],c[M],rn,qn; 10 struct Node{ 11 int x,y,id,pos; 12 friend bool operator < (const Node a,const Node b){ 13 if((a.x-1)/s!=(b.x-1)/s)return ((a.x-1)/s)<((b.x-1)/s); 14 if((a.y-1)/s!=(b.y-1)/s)return ((a.y-1)/s)<((b.y-1)/s); 15 return a.id<b.id; 16 } 17 }Q[N]; 18 struct Num{ 19 int x,y;}C[N]; 20 char obuf[1<<24], *O=obuf; 21 inline int read() 22 { 23 char ch=getchar();int num=0; 24 while(ch<‘0‘||ch>‘9‘)ch=getchar(); 25 while(ch>=‘0‘&&ch<=‘9‘){ 26 num=num*10+ch-‘0‘;ch=getchar();} 27 return num; 28 } 29 inline void print(int x) 30 { 31 if(x>9)print(x/10); 32 *O++ = x%10+‘0‘; 33 } 34 inline void change(int x,int i) 35 { 36 if(Q[i].x<=C[x].x&&C[x].x<=Q[i].y){ 37 if(--c[a[C[x].x]]==0)tot--; 38 if(++c[C[x].y]==1)tot++; } 39 swap(a[C[x].x],C[x].y); 40 } 41 inline void add(int x) 42 {if(++c[a[x]]==1)tot++;} 43 inline void del(int x) 44 {if(--c[a[x]]==0)tot--;} 45 inline void work() 46 { 47 sort(Q+1,Q+qn+1);int now=0; 48 for(int i=1;i<=qn;i++){ 49 while(L<Q[i].x)del(L++); 50 while(L>Q[i].x)add(--L); 51 while(R<Q[i].y)add(++R); 52 while(R>Q[i].y)del(R--); 53 while(now<Q[i].id){change(++now,i);} 54 while(now>Q[i].id){change(now--,i);} 55 ans[Q[i].pos]=tot;} 56 for(int i=1;i<=qn;i++) 57 {print(ans[i]);*O++ = ‘\n‘;} 58 } 59 int main() 60 { 61 n=read();m=read(); 62 for(int i=1;i<=n;i++)a[i]=read(); 63 for(int i=1;i<=m;i++){ 64 char ch[5];scanf("%s",ch); 65 int x=read();int y=read(); 66 if(ch[0]==‘R‘){C[++rn].x=x;C[rn].y=y;} 67 else {Q[++qn].x=x;Q[qn].y=y; 68 Q[qn].id=rn;Q[qn].pos=qn;}} 69 s=ceil(exp((log(n)+log(qn))/3));L=1;R=0; 70 work();fwrite(obuf, O-obuf, 1, stdout); 71 return 0; 72 }
BZOJ2120/洛谷P1903 [国家集训队] 数颜色 [带修改莫队]
原文：https://www.cnblogs.com/cytus/p/9118974.html