墨墨购买了一套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≤10000,M≤10000,修改操作不多于1000次,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
来源:bzoj2120
本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。
裸的带修改的莫队
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<cstdlib>
7 #include<ctime>
8 using namespace std;
9 const int MAXN=10001;
10 static void read(int &n)
11 {
12 char c='+';int x=0;bool flag=0;
13 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
14 while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
15 flag==1?n=-x:n=x;
16 }
17 int n,m;
18 int a[MAXN];
19 struct CX
20 {
21 int l,r,id,tm;// tm上一次的更改操作
22 }cx[MAXN];
23 int cxnum;
24 struct GG
25 {
26 int pos,val,pre;
27 }gg[MAXN];
28 int ggnum;
29 int head[MAXN];
30 int where[MAXN];
31 int base;
32 int vis[MAXN];// 是否有更改操作
33 int color[MAXN];
34 int ans=0;
35 int out[MAXN];
36 int comp(const CX &a,const CX &b)
37 {
38 if(where[a.l]==where[b.l])
39 return a.r<b.r;
40 else
41 return where[a.l]<where[b.l];
42 }
43 int calc(int x)
44 {
45 if(vis[x])
46 {
47 if(--color[a[x]]==0)
48 ans--;
49 }
50 else
51 {
52 if(++color[a[x]]==1)
53 ans++;
54 }
55 vis[x]=!vis[x];
56 }
57 void change(int p,int v)
58 {
59 if(vis[p])
60 {
61 calc(p);
62 a[p]=v;
63 calc(p);
64 }
65 else
66 a[p]=v;
67 }
68
69 int main()
70 {
71 read(n);read(m);
72 for(int i=1;i<=n;i++)
73 read(a[i]),head[i]=a[i];
74 base=sqrt(n);
75 for(int i=1;i<=n;i++)
76 where[i]=(i-1)/base+1;
77 for(int i=1;i<=m;i++)
78 {
79 char c;
80 int x,y;
81 cin>>c;
82 read(x);read(y);
83 if(c=='Q')// 查询
84 {
85 cxnum++;
86 cx[cxnum].l=x;
87 cx[cxnum].r=y;
88 cx[cxnum].id=cxnum;
89 cx[cxnum].tm=ggnum;
90 }
91 else
92 {
93 ggnum++;
94 gg[ggnum].pos=x;
95 gg[ggnum].val=y;
96 gg[ggnum].pre=head[x];
97 head[x]=y;
98 }
99 }
100 sort(cx+1,cx+cxnum+1,comp);
101 int l=1,r=0;
102 for(int i=1;i<=cxnum;i++)
103 {
104 for(int j=cx[i-1].tm+1;j<=cx[i].tm;j++)
105 change(gg[j].pos,gg[j].val);
106 for(int j=cx[i-1].tm;j>=cx[i].tm+1;j--)
107 change(gg[j].pos,gg[j].pre);// 此处是pre,不是val!!!
108 for(;l<cx[i].l;l++)
109 calc(l);
110 for(;l>cx[i].l;l--)
111 calc(l-1);
112 for(;r<cx[i].r;r++)
113 calc(r+1);
114 for(;r>cx[i].r;r--)
115 calc(r);
116 out[cx[i].id]=ans;
117 }
118 for(int i=1;i<=cxnum;i++)
119 printf("%d\n",out[i]);
120 return 0;
121 }