记录编号	474248	评测结果	WWWWWWWWWWWWWWWWWWWW
题目名称	[国家集训队2011]数颜色	最终得分	0
用户昵称	BaDBoY	是否通过	未通过
代码语言	C++	运行时间	0.001 s
提交时间	2017-11-09 20:15:32	内存使用	0.00 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=10000+10;
char buf[M*30], *ptr=buf-1;
inline int read(){
    register int x=0,f=1,c=*++ptr;
    while (c<48) c=='-'&&(f=-1),c=*++ptr;
    while (c>47) x=x*10+c-48,c=*++ptr;
    return x * f;
}
const int qrt=200;
int l=1,r=0,t=0;
int n,m,blo,tot,num,an;
int block[M],val[M],ge[M*100],tmp[M],ans[M];
struct DATE{int l,r,tim,id;}date[M];
struct C{int pos,v,last;}c[M];
inline bool cmp(DATE a,DATE b){
	if(block[a.l]==block[b.l]) return block[a.r]==block[b.r]?a.tim<b.tim:block[a.r]<block[b.r];
	return block[a.l]<block[b.l];
}
inline void add(int x) {an+=(++ge[x]==1);}
inline void del(int x) {an-=(--ge[x]==0);}
inline void update(int pos,int to) {if(l<=pos&&pos<=r) add(to),del(val[pos]); val[pos]=to;}
int NOIP(){
	freopen("nt2011_color.in","r",stdin);
    freopen("nt2011_color.out","w",stdout);
    fread(buf,1,sizeof(buf),stdin);
	n=read();m=read();char s[2];int xx,yy;
	for(int i=1;i<=n;++i) tmp[i]=val[i]=read(),block[i]=(i-1)/qrt+1;
	while(m--){
		scanf("%s",s);xx=read();yy=read();
		if(s[0]=='Q') date[++tot]=(DATE){xx,yy,num,tot};
		else {c[++num]=(C){xx,yy,tmp[xx]};tmp[xx]=yy;}
	}sort(date+1,date+tot+1,cmp);
	for(int i=1;i<=tot;++i){
		int L=date[i].l,R=date[i].r,T=date[i].tim;
		for(;t<T;++t) update(c[t+1].pos,c[t+1].v);
		for(;t>T;--t) update(c[t].pos,c[t].last);
		for(;r<R;++r) add(val[r+1]);
		for(;r>R;--r) del(val[r]);
		for(;l<L;++l) del(val[l]);
		for(;l>L;--l) add(val[l-1]);
		ans[date[i].id]=an;
	}for(int i=1;i<=tot;++i) printf("%d\n",ans[i]);
	return 0;
}
int NOIPRP=NOIP();
int main(){;}