文件详细信息

下载本文件

本文件的大小为 2033 字节。

#include<algorithm>
#include<cmath>
#include<cstdio>
template<typename T>
void read(T&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
void write(T a){
	static int ch[20],cnt=0;
	if(a==0)putchar('0');
	while(a)ch[cnt++]=a%10|48,a/=10;
	while(cnt)putchar(ch[--cnt]);
}
void my_getchar(char&ch){
	do ch=getchar();
	while(ch!='R'&&ch!='Q');
}
template<typename T>
inline T min(const T a,const T b){
	return a<b?a:b;
}
typedef double real;
const int maxn=133333,maxtot=52,maxm=133333,maxval=1000000;
int n,m,c,q,B,tot,a[maxn+1],belong[maxn+1],l[maxtot+1],r[maxtot+1],cnt[maxval+1],cur,ans[maxm+1];
struct OP{
	char op;
	int x,y,z,id;
}op[maxm+1];
bool operator<(const OP a,const OP b){
	if(a.op!=b.op)return a.op>b.op;
	if(a.op=='Q')return belong[a.x]!=belong[b.x]?a.x<b.x:belong[a.y]!=belong[b.y]?a.y<b.y:a.z<b.z;
	return a.id<b.id;
}
void add(const int x){
	if(++cnt[a[x]]==1)cur++;
}
void del(const int x){
	if(--cnt[a[x]]==0)cur--;
}
int main(){
	read(n),read(m);
	B=cbrt((real)n*n),tot=(n+B-1)/B;
	for(int i=1;i<=n;i++)read(a[i]);
	for(int i=1;i<=tot;i++){
		l[i]=r[i-1]+1,r[i]=min(r[i-1]+B,n);
		for(int j=l[i];j<=r[i];j++)belong[j]=i;
	}
	for(int i=1;i<=m;i++){
		my_getchar(op[i].op),read(op[i].x),read(op[i].y);
		if(op[i].op=='R'){
			op[i].z=a[op[i].x];
			a[op[i].x]=op[i].y;
			op[i].id=i;
			c++;
		}else{
			op[i].id=++q;
			op[i].z=c;
		}
	}
	std::sort(op+1,op+m+1);
	int l=1,r=0,x=c;
	for(int i=c+1;i<=m;i++){
		while(l<op[i].x)del(l++);
		while(l>op[i].x)add(--l);
		while(r<op[i].y)add(++r);
		while(r>op[i].y)del(r--);
		while(x>op[i].z){
			if(l<=op[x].x&&op[x].x<=r){
				del(op[x].x);
				a[op[x].x]=op[x].z;
				add(op[x].x);
			}else a[op[x].x]=op[x].z;
			x--;
		}
		while(x<op[i].z){
			x++;
			if(l<=op[x].x&&op[x].x<=r){
				del(op[x].x);
				a[op[x].x]=op[x].y;
				add(op[x].x);
			}else a[op[x].x]=op[x].y;
		}
		ans[op[i].id]=cur;
	}
	for(int i=1;i<=q;i++)write(ans[i]),putchar('\n');
	return 0;
}