2120. [國家集訓隊]數顔色【帶修莫隊】

Description

墨墨購買了一套N支彩色畫筆（其中有些顔色可能相同），擺成一排，你需要回答墨墨的提問。墨墨會像你釋出如下指令： 1、 Q L R代表詢問你從第L支畫筆到第R支畫筆中共有幾種不同顔色的畫筆。 2、 R P Col 把第P支畫筆替換為顔色Col。為了滿足墨墨的要求，你知道你需要幹什麼了嗎？

Input

第1行兩個整數N，M，分别代表初始畫筆的數量以及墨墨會做的事情的個數。第2行N個整數，分别代表初始畫筆排中第i支畫筆的顔色。第3行到第2+M行，每行分别代表墨墨會做的一件事情，格式見題幹部分。

Output

對于每一個Query的詢問，你需要在對應的行中給出一個數字，代表第L支畫筆到第R支畫筆中共有幾種不同顔色的畫筆。

Sample Input

6 5

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Sample Output

4

3

HINT

對于100%的資料，N≤10000，M≤10000，修改操作不多于1000次，所有的輸入資料中出現的所有整數均大于等于1且不超過10^6。

1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<algorithm>
 6 #define N (50000+100)
 7 using namespace std;
 8 
 9 struct Qu{int x,y,t,num,ans;}Q[N];
10 struct Up{int pre,pos,val;}U[N];
11 int n,m,a[N],Q_num,U_num,l=1,r=0,Color,now,Keg[N*20],x,y,id[N];
12 char opt[3];
13 bool cmp1(Qu a,Qu b){return id[a.x]==id[b.x]?(id[a.y]==id[b.y]?a.t<b.t:id[a.y]<id[b.y]):id[a.x]<id[b.x];}
14 bool cmp2(Qu a,Qu b){return a.num<b.num;}
15 
16 void Ins(int x){++Keg[x]; if (Keg[x]==1) Color++;}
17 void Del(int x){--Keg[x]; if (Keg[x]==0) Color--;}
18 
19 void Recovery(int pos,int val)
20 {
21     if (pos>=l && pos<=r) Del(a[pos]),Ins(val);
22     a[pos]=val;
23 }
24 
25 void MoQueue()
26 {
27     for (int i=1; i<=Q_num; ++i)
28     {
29         while (now<Q[i].t) Recovery(U[now+1].pos,U[now+1].val),now++;
30         while (now>Q[i].t) Recovery(U[now].pos,U[now].pre),now--;
31         while (l<Q[i].x) Del(a[l++]);
32         while (l>Q[i].x) Ins(a[--l]);
33         while (r<Q[i].y) Ins(a[++r]);
34         while (r>Q[i].y) Del(a[r--]);
35         Q[i].ans=Color;
36     }
37 }
38 
39 int main()
40 {
41     scanf("%d%d",&n,&m);
42     int unit=pow(n,2.0/3.0);
43     for (int i=1; i<=n; ++i)
44         scanf("%d",&a[i]),id[i]=i/unit;
45     for (int i=1; i<=m; ++i)
46     {
47         scanf("%s%d%d",opt,&x,&y);
48         if (opt[0]=='Q')
49         {
50             Q[++Q_num].x=x;
51             Q[Q_num].y=y;
52             Q[Q_num].t=U_num;
53             Q[Q_num].num=i;
54         }
55         else
56         {
57             U[++U_num].pos=x;
58             U[U_num].pre=a[x];
59             U[U_num].val=y;
60             a[x]=y;
61         }
62     }
63     for (int i=U_num; i>=1; --i)
64             a[U[i].pos]=U[i].pre;
65     sort(Q+1,Q+Q_num+1,cmp1);
66     MoQueue();
67     sort(Q+1,Q+Q_num+1,cmp2);
68     for (int i=1; i<=Q_num; ++i)
69         printf("%d\n",Q[i].ans);
70 }