记录编号	313741	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.792 s
提交时间	2016-10-02 06:27:17	内存使用	4.68 MiB

#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=100000;
int b[maxn],num[1050000],n,m;
void Init();

int main(){
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	int l=1,r=1,tot=1;num[b[1]]=1;
	for(int i=1;i<=m;i++){
		char ch;int L,R,X,Y;
		scanf(" %c",&ch);
		if(ch=='Q'){
			scanf("%d%d",&L,&R);
			while(l<L){
				num[b[l]]--;
				if(num[b[l]]==0)tot--;
				l++;
			}
			while(l>L){
				l--;num[b[l]]++;
				if(num[b[l]]==1)tot++;
			}
			while(r>R){
				num[b[r]]--;
				if(num[b[r]]==0)tot--;
				r--;
			}
			while(r<R){
				r++;num[b[r]]++;
				if(num[b[r]]==1)tot++;
			}
			printf("%d\n",tot);
		}
		else {
			scanf("%d%d",&X,&Y);
			if(l<=X && r>=X){
				num[b[X]]--;
				if(num[b[X]]==0)tot--;
				if(++num[Y]==1)tot++;
				b[X]=Y;
			}
			else b[X]=Y;
		}
	}
}