记录编号	455043	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.051 s
提交时间	2017-09-30 21:51:58	内存使用	3.42 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=10000+10;
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 int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
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 DK(){
	freopen("nt2011_color.in","r",stdin);
    freopen("nt2011_color.out","w",stdout);
	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 dk=DK();
int main(){;}