记录编号	454648	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.325 s
提交时间	2017-09-29 11:28:19	内存使用	4.45 MiB

#include<bits/stdc++.h>//再写一遍带修莫队
using namespace std;
int n,m,col[10005],pos[10005],cnt[1000005],b[10005],m1,m2;
struct Ques{
	int l,r,id,ans,tim;
	bool operator < (const Ques &o)const{
		if(pos[l]!=pos[o.l])return l<o.l;
		if(pos[r]!=pos[o.r])return r<o.r;
		return tim<o.tim;
	}
}q[10005];
struct change{
	int id,to,from;
}c[1005];
bool cmp(Ques x,Ques y){
	return x.id<y.id;
}
int main()
{
	freopen("nt2011_color.in","r",stdin);freopen("nt2011_color.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&col[i]),b[i]=col[i];
	for(int i=1;i<=m;i++){
		char s[5];int x,y;
		scanf("%s%d%d",s,&x,&y);
		if(s[0]=='Q'){
			q[++m1].id=i;q[m1].l=x;q[m1].r=y;q[m1].tim=m2;
		}
		else{
			c[++m2].id=x;c[m2].from=b[x];c[m2].to=y;b[x]=y;//这里x错打成了i还过了12个点... 
		}
	}
	int len=pow(n,0.666666);
	for(int i=1;i<=n;i++)pos[i]=(i-1)/len+1;
	sort(q+1,q+m1+1);
	int now=0,l=1,r=0,ans=0;
	for(int i=1;i<=m1;i++){
		while(now<q[i].tim){
			now++;
			col[c[now].id]=c[now].to;
			if(c[now].id>=l&&c[now].id<=r){
				cnt[c[now].from]--;if(!cnt[c[now].from])ans--;
				cnt[c[now].to]++;if(cnt[c[now].to]==1)ans++;
			}
		}
		while(now>q[i].tim){
			col[c[now].id]=c[now].from;
			if(c[now].id>=l&&c[now].id<=r){
				cnt[c[now].from]++;if(cnt[c[now].from]==1)ans++;
				cnt[c[now].to]--;if(!cnt[c[now].to])ans--;
			}
			now--;
		}
		while(l<q[i].l){
			cnt[col[l]]--;if(!cnt[col[l]])ans--;
			l++;
		}
		while(l>q[i].l){
			l--;
			cnt[col[l]]++;if(cnt[col[l]]==1)ans++;
		}
		while(r<q[i].r){
			r++;
			cnt[col[r]]++;if(cnt[col[r]]==1)ans++;
		}
		while(r>q[i].r){
			cnt[col[r]]--;if(!cnt[col[r]])ans--;
			r--;
		}
		q[i].ans=ans;
	}
	sort(q+1,q+m1+1,cmp);
	for(int i=1;i<=m1;i++)printf("%d\n",q[i].ans);
	return 0;
}