題目描述
墨墨購買了一套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 #include <bits/stdc++.h>
2 using namespace std;
3 const int maxn=10000+10;
4 struct Query{
5 int l,r,Tim,ID;
6 }q[maxn];
7 struct Change{
8 int pos,New,Old;
9 }c[maxn];
10 int s[maxn],Be[maxn];
11 int now[maxn],ans[maxn];
12 int color[maxn*100];
13 int Ans,l=1,r;
14 bool cmp(Query a,Query b)
15 {
16 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;
17 }
18 void revise(int x,int d)
19 {
20 color[x]+=d; //此種顔色的種類數+1或-1；
21 if(d>0) Ans+=color[x]==1; //如果目前此種類為1，證明為剛加上去的，則種類數+1；
22 if(d<0) Ans-=color[x]==0; //如果目前此種類為0，證明為剛減的種類數-1；
23 }
24 void going(int x,int d)
25 {
26 if(l<=x&&x<=r){ //改變的位置在目前的區間内
27 revise(d,1); //改變後的數的種類數改變
28 revise(s[x],-1); //被改變的數字去改變；
29 }
30 s[x]=d; //把這個位置的權值改變
31 }
32 int main()
33 {
34 int n,m;
35 scanf("%d%d",&n,&m);
36 int unit=pow(n,2.0/3);
37 for(int i=1;i<=n;i++){
38 scanf("%d",&s[i]);
39 now[i]=s[i];
40 Be[i]=i/unit+1; //分塊,用于排序優化，具體原理不懂；
41 }
42 int Time=0,t=0;
43 while(m--){
44 char sign; int x,y;
45 scanf(" %c %d%d",&sign,&x,&y);
46 if(sign=='Q') q[++t]=(Query){x,y,Time,t};
47 else c[++Time]=(Change){x,y,now[x]},now[x]=y;
48 }
49 sort(q+1,q+t+1,cmp);
50 int T=0;ANS=0; //初始化 時間 以及答案。
51 for(int i=1;i<=t;i++){
52
53 while(T<q[i].Tim) going(c[T+1].pos,c[T+1].New),T++;
54 while(T>q[i].Tim) going(c[T].pos,c[T].Old),T--;
55
56 while(l<q[i].l) revise(s[l],-1),l++;
57 while(l>q[i].l) revise(s[l-1],1),l--;
58 while(r<q[i].r) revise(s[r+1],1),r++;
59 while(r>q[i].r) revise(s[r],-1),r--;
60
61 ans[q[i].ID]=Ans;
62 }
63 for(int i=1;i<=t;i++)
64 printf("%d\n",ans[i]);
65 return 0;
66 }