BZOJ 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 Q 1 4 Q 2 6

Sample Output

4 4 3 4

HINT

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

2016.3.2新加数据两组by Nano_Ape

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

带修莫队~

莫队真是麻烦……注意点一大堆……鏼鏼发抖……

注意：

1.在线上的莫队（并不知道该叫什么）比起树上莫队要先修改q[1]的区间，否则连样例都过不了；

2.time总是比现在的时间大1；

3.变量用time在BZOJ 上会CE，估计在其他OJ上也一样（所以改成了诡异的timm）；

4.q[i].id和i要分清啊。

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int n,m,a[10001],tot,timm,ans[10001],aa[10001],num[1000001],now; bool b[10001]; char s[2]; struct node{ int l,r,id,tim; }q[10001],c[1001]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } bool operator < (node u,node v) { return u.l==v.l ? u.r<v.r:u.l<v.l; } void chancol(int u,int v) { if(!b[u]) a[u]=v; else { now-=(--num[a[u]]==0); a[u]=v; now+=(++num[a[u]]==1); } } void xo(int u) { if(b[u]) now-=(--num[a[u]]==0); else now+=(++num[a[u]]==1); b[u]^=1; } void chan(int l,int r,int k) { if(l>r) swap(l,r); for(int i=l;i<=r;i++) xo(i); if(!k) xo(r); else xo(l); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) aa[i]=a[i]=read(); for(int i=1;i<=m;i++) { scanf("%s",s); if(s[0]=='Q') q[++tot].l=read(),q[tot].r=read(),q[tot].id=tot,q[tot].tim=timm; else { c[++timm].l=read();c[timm].r=read(); c[timm].id=aa[c[timm].l];aa[c[timm].l]=c[timm].r; if(c[timm].r==c[timm].id) timm--; } } sort(q+1,q+tot+1);timm=1; for(int i=q[1].l;i<=q[1].r;i++) b[i]=1,now+=(++num[a[i]]==1); int l=q[1].l,r=q[1].r; if(timm<=q[1].tim) for(;timm<=q[1].tim;timm++) chancol(c[timm].l,c[timm].r); ans[q[1].id]=now; for(int i=2;i<=tot;i++) { if(q[i].l!=l) chan(q[i].l,l,0),l=q[i].l; if(q[i].r!=r) chan(q[i].r,r,1),r=q[i].r; if(timm<=q[i].tim) for(;timm<=q[i].tim;timm++) chancol(c[timm].l,c[timm].r); else if(timm>q[i].tim+1) for(;timm>q[i].tim+1;timm--) chancol(c[timm-1].l,c[timm-1].id); ans[q[i].id]=now; } for(int i=1;i<=tot;i++) printf("%d\n",ans[i]); return 0; }