正文
BZOJ2120 数颜色（带修改的莫队算法）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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 Input6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
Sample Output4
4
3
4
HINT对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
Output对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
Sample Input6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
Sample Output4
4
3
4
HINT对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
对于每一个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
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
Sample Output4
4
3
4
HINT对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
4
3
4
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
————————————————————————————————————————————————————————————————————————————————
1、莫队一般情况下是进行数据修改的。如果需要修改时，则在问题的二元组（l,r）中加入第三项pre，构成三元组（l,r,pre）。其中pre表示已经修改过几次。并在排序中加入第三关键字pre。
2、记录每一次更改，并记录每次更改前后的数据。当由一种询问变到另一种询问时，只要先将pre通过记录的更改变成下一次询问的pre，然后再按照一般莫队算法依次修改 l 和 r，得到最终结果 。
3、注意：
a、每次pre的修改，如果修改点在上次查询的范围内，则应当把把对应的ans进行修改。
b、每次修改都会对记录数组时行改变。但是查询的状态需要对应状态pre。
难懂！也就是在查询初始状态时（l=2,r=1）它对应还没有修改过的笔的状态；不能用改了某些笔的姿态来进行查询。
————————————————————————————————————————————————————————————————————————————————
1 #include<bits/stdc++.h>
2
3 using namespace std;
4 const int maxn=1e4+7;
5 int n,m,siz;
6 int cl[maxn],clf[maxn];
7 int clh[1000007];
8 char s[2];
9 struct que
10 {
11 int l,r,id,belong,chgd;
12 }q[maxn];
13 struct chang
14 {
15 int ps,pre,nex,id;
16 }ch[maxn];
17 int l,r,c,ans,da[maxn];
18
19 void readint(int &x)
20 {
21 char c=getchar();
22 int f=1;
23 for(;c>'9'||c<'0';c=getchar())if(c=='-')f=-f;
24 x=0;
25 for(;c<='9' && c>='0';c=getchar())x=(x<<1)+(x<<3)+c-'0';
26 x=x*f;
27 }
28 bool cmp(que a,que b)
29 {
30 if(a.belong<b.belong)return 1;
31 if(a.belong==b.belong &&a.r<b.r)return 1;
32 if(a.belong==b.belong &&a.r==b.r &&a.chgd<b.chgd)return 1;
33 return 0;
34 }
35 void del(int ps)
36 {
37 ps=clf[ps];
38 clh[ps]--;
39 if(clh[ps]==0)ans--;
40 }
41 void add(int ps)
42 {
43 ps=clf[ps];
44 clh[ps]++;
45 if(clh[ps]==1)ans++;
46 }
47 int main()
48 {
49 readint(n);readint(m);
50 for(int i=1;i<=n;i++)
51 {
52 readint(cl[i]);clf[i]=cl[i];
53 }
54 int bs=sqrt(n+0.5);
55 int cjs=0,qjs=0;
56 for(int a,b,i=0;i<m;i++)
57 {
58 scanf("%s",s);readint(a);readint(b);
59 if(s[0]=='Q')
60 {
61 q[qjs].l=a;q[qjs].r=b;
62 q[qjs].id=qjs;q[qjs].belong=(a-1)/bs;
63 q[qjs].chgd=cjs;
64 qjs++;
65 }
66 else
67 {
68 ch[cjs].id=cjs;
69 ch[cjs].ps=a;
70 ch[cjs].nex=b;
71 ch[cjs].pre=cl[a];
72 cl[a]=b;
73 cjs++;
74 }
75 }
76 sort(q,q+qjs,cmp);
77 l=2;r=1;ans=0;c=0;
78 for(int i=0;i<qjs;i++)
79 {
80 while(c<q[i].chgd)
81 {
82 if(ch[c].ps>=l && ch[c].ps<=r)
83 {
84 clh[ch[c].pre]--;
85 if(clh[ch[c].pre]==0)ans--;
86 clh[ch[c].nex]++;
87 if(clh[ch[c].nex]==1)ans++;
88 }
89 clf[ch[c].ps]=ch[c].nex;
90 c++;
91 }
92 while(c>q[i].chgd)
93 {
94 c--;
95 if(ch[c].ps>=l &&ch[c].ps<=r)
96 {
97 clh[ch[c].pre]++;
98 if(clh[ch[c].pre]==1)ans++;
99 clh[ch[c].nex]--;
100 if(clh[ch[c].nex]==0)ans--;
101 }
102 clf[ch[c].ps]=ch[c].pre;
103 }
104 while(l<q[i].l)
105 {
106 del(l);l++;
107 }
108 while(l>q[i].l)
109 {
110 l--;add(l);
111 }
112 while(r<q[i].r)
113 {
114 r++;add(r);
115 }
116 while(r>q[i].r)
117 {
118 del(r);r--;
119 }
120 da[q[i].id]=ans;
121 }
122 for(int i=0;i<qjs;i++)printf("%d\n",da[i]);
123 return 0;
124 }
