记录编号	144612	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.880 s
提交时间	2014-12-24 16:59:22	内存使用	0.51 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
#include<cmath>
using namespace std;
const int SIZEN=11010,SIZEM=10010;
typedef bitset<SIZEN> Bset;
int N,M;
int A[SIZEN];//初始颜色
class Quest{
public:
	char cmd[3];
	int a,b;
}Q[SIZEM];
void change(int x,int t){
	A[x]=t;
}
int query(int a,int b){
	static Bset ans;
	ans.reset();
	for(int i=a;i<=b;i++) ans[A[i]]=true;
	return ans.count();
}
void work(void){
	for(int i=1;i<=M;i++){
		if(Q[i].cmd[0]=='Q') printf("%d\n",query(Q[i].a,Q[i].b));
		else change(Q[i].a,Q[i].b);
	}
}
void read(void){
	static int cols[SIZEN],CN=0;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++){
		scanf("%d",&A[i]);
		cols[CN++]=A[i];
	}
	for(int i=1;i<=M;i++){
		scanf("%s",Q[i].cmd);
		scanf("%d%d",&Q[i].a,&Q[i].b);
		if(Q[i].cmd[0]=='R') cols[CN++]=Q[i].b;
	}
	sort(cols,cols+CN);
	for(int i=1;i<=N;i++) A[i]=lower_bound(cols,cols+CN,A[i])-cols;
	for(int i=1;i<=M;i++)
		if(Q[i].cmd[0]=='R') Q[i].b=lower_bound(cols,cols+CN,Q[i].b)-cols;
}
int main(){
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
	read();
	work();
	return 0;
}