记录编号	155282	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.353 s
提交时间	2015-03-28 09:51:02	内存使用	6.66 MiB

#include<cstdio>
#include<algorithm>
const int sizen=400,maxn=11010;
char chin[2000000],chout[100000],*pin=chin,*pout=chout;
int n,m,ansnow,cnt[maxn],col[maxn],ans[maxn],last[maxn],used[1000001];
bool vis[maxn];
struct node{
	int l,r,bl,br,id,tim;
}q[maxn];
struct change{
	int pos,col,last;
}c[maxn];
void in(int &x){
	x=0;
	while(*pin<48) pin++;
	while(*pin>47) x=x*10+*pin++-48;
}
bool cmp(node a,node b){
	if(a.bl!=b.bl) return a.l<b.l;
	if(a.br!=b.br) return a.r<b.r;
	return a.id<b.id; 
}
void out(int x){
	if(!x)*pout++='0';
	int p=0;char buf[10];
	while(x) buf[++p]=x%10+'0',x/=10;
	while(p) *pout++=buf[p--];
	*pout++='\n';
}
void update(int x){
	if(vis[x]){
		cnt[col[x]]--;
		if(!cnt[col[x]]) ansnow--;
	}
	else{
		if(!cnt[col[x]]) ansnow++;
		cnt[col[x]]++;
	}
	vis[x]^=1;
}
void modify(int u,int v){
	if(vis[u]) update(u),col[u]=v,update(u);
	else col[u]=v;
}
int main(){
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
	fread(pin,1,2000000,stdin);
	int i,j,l,r,tim=0,totq=0,totc=0,timnow=1;
	in(n),in(m);
	for(i=1;i<=n;i++){
		in(j);
		if(!used[j]) used[j]=++tim;
		col[i]=last[i]=used[j];
	}
	for(i=1;i<=m;i++){
		while(*pin<60) pin++;
		if(*pin=='Q') pin++,in(l),in(r),totq++,q[totq]=(node){l,r,l/sizen,r/sizen,totq,totc};
		else{
			pin++,in(l),in(r);
			if(!used[r]) used[r]=++tim;
			r=used[r],c[++totc].pos=l,c[totc].last=last[l],c[totc].col=last[l]=r;
		}
	}
	std::sort(q+1,q+totq+1,cmp);
	while(timnow<=q[1].tim) modify(c[timnow].pos,c[timnow].col),timnow++;
	for(i=q[1].l;i<=q[1].r;i++) update(i);
	l=q[1].l,r=q[1].r,ans[q[1].id]=ansnow;
	for(i=2;i<=totq;i++){
		while(timnow<=q[i].tim) modify(c[timnow].pos,c[timnow].col),timnow++;
		while(timnow>q[i].tim+1)modify(c[timnow-1].pos,c[timnow-1].last),timnow--;
		while(l<q[i].l) update(l++);
		while(l>q[i].l) update(--l);
		while(r<q[i].r) update(++r);
		while(r>q[i].r) update(r--);
		ans[q[i].id]=ansnow;
	}
	for(int i=1;i<=totq;i++) out(ans[i]);
	fwrite(chout,1,pout-chout,stdout);
}