记录编号	191470	评测结果	AAAAAAAAAAAATAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	95
用户昵称	战神联盟雷神雷伊	是否通过	未通过
代码语言	C++	运行时间	8.693 s
提交时间	2015-10-07 19:57:57	内存使用	2.28 MiB

#include<cstdio>
#include<vector>
#include<queue>
#include<vector>
#include<iostream>
#include<cstdlib>
#include<bitset>
#include<algorithm>
#define ll long long
using namespace std;
typedef bitset<200001> Bset;
int n,m;
int a[10001];
struct sd{
	char ch;int x,y;
}c[100001];
int tot=0,col[200001];
int ask(int x,int y)
{
	static Bset ans;
	ans.reset();
	for(int i=x;i<=y;i++) ans[a[i]]=true;
	return ans.count();
}
int main()
{
	freopen("nt2011_color.in","r",stdin);
	freopen("nt2011_color.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		col[tot++]=a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>c[i].ch>>c[i].x>>c[i].y;
		if(c[i].ch=='R')col[tot++]=c[i].y;
	}
	sort(col,col+tot);
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(col,col+tot,a[i])-col;
	}
	for(int i=0;i<tot;i++)
	{
		if(c[i].ch=='R')
		c[i].y=lower_bound(col,col+tot,c[i].y)-col;
	}
	for(int i=1;i<=m;i++)
	{
		if(c[i].ch=='Q')
		printf("%d\n",ask(c[i].x,c[i].y));
		else
		a[c[i].x]=c[i].y;
	}
//	for(;;);
}