记录编号	297997	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	0.462 s
提交时间	2016-08-19 19:56:27	内存使用	17.90 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;

int i,n,m,cn=0,cnt=0,ans=0,x,y,block;
int s[1000010]={0},c[10010],b[10010],last[10010];
int Ans[10010];
bool v[10010];
char k[500];
struct zht{
	int l,r,id,n;
}q[10010];
struct Zht{
	int pos,c,p;
}d[10010];

bool cmp(zht A,zht B){
	if (b[A.l]==b[B.l]) return A.r<B.r;	else return A.l<B.l;
}

inline void update(int x){
	if (v[x]){
		if (!--s[c[x]])	ans--;
	}	else {
		if (++s[c[x]]==1)	ans++;
	}
	v[x]^=1;
	return;
}

inline void Change(int x,int y){
	if (v[x]){
		update(x);	c[x]=y;	update(x);
	}	else c[x]=y;
	return;
}

inline void Solve(){
	int i=0,j=0,l=1,r=1;
	update(l);
	for (i=1;i<=cn;i++){
		for (j=q[i-1].n+1;j<=q[i].n;j++)
		Change(d[j].pos,d[j].c);
        for (j=q[i-1].n;j>q[i].n;j--)
        Change(d[j].pos,d[j].p);
        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]=ans;
	}
	return;
}

int main(){
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++){
		scanf("%d",&c[i]);	last[i]=c[i];
	}
	for (i=1;i<=m;i++){
		scanf("%s",&k);	scanf("%d%d",&x,&y);
		if (k[0]=='Q')	{
			q[++cn].l=x;	q[cn].r=y;	q[cn].id=cn;	q[cn].n=cnt;
		}	else {
			d[++cnt].pos=x;	d[cnt].c=y;	d[cnt].p=last[x];
			last[x]=y;
		}
	}
	block=sqrt(n);
	for (i=1;i<=n;i++)	b[i]=(i-1)/block+1;
	sort(q+1,q+1+cn,cmp);
	Solve();
	for (i=1;i<=cn;i++)	printf("%d\n",Ans[i]);
	return 0;
}