记录编号	147801	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.243 s
提交时间	2015-02-04 09:01:14	内存使用	1.71 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define Maxn 30010
using namespace std;
struct asks{
	int l,r,t,pos;
}A[Maxn];
int n,m,a[Maxn],blcsiz,totb=0,tot=0,tota=0,cnt[Maxn]={0},a0[Maxn],ans=0;
int chav[Maxn],chax[Maxn],last[Maxn]={0},a1[Maxn],ansv[Maxn],Sq3[Maxn];
char str[2];
bool cmpx(asks a,asks b){
	if(Sq3[a.l]!=Sq3[b.l]) return a.l<b.l;
	if(Sq3[a.r]!=Sq3[b.r]) return a.r<b.r;
	return a.t<b.t;
}
int main(){
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),a0[i]=a1[i]=a[i],Sq3[i]=(int)pow(i+0.5,1.0/3.0);
	for(int i=1,x,y;i<=m;i++){
		scanf("%s%d%d",str,&x,&y);
		if(str[0]=='Q') A[++tota]=(asks){min(x,y),max(x,y),totb,tota};
		else chax[++totb]=x,chav[totb]=y,last[totb]=a[x],a[x]=y;
	}
	sort(A+1,A+tota+1,cmpx);
	tot=n;
	for(int i=1;i<=totb;i++) a0[++tot]=chav[i];
	sort(a0+1,a0+tot+1); int N=1;
	for(int i=2;i<=tot;i++) if(a0[i]!=a0[i-1]) a0[++N]=a0[i];
	//for(int i=1;i<=N;i++) cout<<a0[i]<<' '; cout<<endl;
	for(int i=1;i<=totb;i++){
		chav[i]=lower_bound(a0+1,a0+N+1,chav[i])-a0;
		last[i]=lower_bound(a0+1,a0+N+1,last[i])-a0;
	}
	for(int i=1;i<=n;i++) a[i]=lower_bound(a0+1,a0+N+1,a1[i])-a0;
	//for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl;
	int l=1,r=0,t=0;
	for(int i=1;i<=tota;i++){
		while(t<A[i].t){
			t++;
			if(chax[t]<=r&&chax[t]>=l){
				cnt[last[t]]--;
				if(!cnt[last[t]]) ans--;
				if(!cnt[chav[t]]) ans++;
				cnt[chav[t]]++;
			}
			a[chax[t]]=chav[t];
		}
		while(t>A[i].t){
            a[chax[t]]=last[t];
            if(chax[t]<=r&&chax[t]>=l){
				cnt[chav[t]]--;
				if(!cnt[chav[t]]) ans--;
				if(!cnt[last[t]]) ans++;
				cnt[last[t]]++;
			}
			t--;
		}
		while(l>A[i].l){
			l--;
			if(!cnt[a[l]]) ans++;
			cnt[a[l]]++;
		}
		while(l<A[i].l){
			cnt[a[l]]--;
			if(!cnt[a[l]]) ans--;
			l++;
		}
		while(r<A[i].r){
			r++;
			if(!cnt[a[r]]) ans++;
			cnt[a[r]]++;
		}
		while(r>A[i].r){
			cnt[a[r]]--;
			if(!cnt[a[r]]) ans--;
			r--;
		}
		//for(int j=1;j<=n;j++) cout<<cnt[j]<<' '; cout<<endl;
		//cout<<l<<' '<<r<<' '<<t<<endl;
		ansv[A[i].pos]=ans;
	}
	for(int i=1;i<=tota;i++) printf("%d\n",ansv[i]);
	return 0;
}