#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read();
const int N=200005;
int pos[N],a[N],num[1000005],cntq,cntg,l,r,res,tim,ans[N],n,m,cnt;
char c;
struct node{
	int l,r,ID,time;
	bool operator < (const node &b)const{
		return (pos[l]^pos[b.l])?pos[l]<pos[b.l]:(pos[r]^pos[b.r])?pos[r]<pos[b.r]:time<b.time;
	}
}q[N];
struct note{
	int wz,color;
}g[N];
void add(int w){
	if(num[a[w]]==0) ++res;
	++num[a[w]];
}
void sub(int w){
	if(num[a[w]]==1) --res;
	--num[a[w]];
}
signed main()
{
	n=read();m=read();
	cnt=pow(n,(double)2/(double)3);
	for(int i=1;i<=n;++i) {
		a[i]=read();
		pos[i]=(i-1)/cnt+1;
	}
	for(int i=1;i<=m;++i){
		cin>>c;
		if(c=='R'){
			g[++cntg].wz=read();
			g[cntg].color=read();
		}
		else {
			q[++cntq].l=read();
			q[cntq].r=read();
			q[cntq].time=cntg;
			q[cntq].ID=cntq;
		}
	}
	sort(q+1,q+1+cntq);
	l=1;r=0;res=0;tim=0;
	for(int i=1;i<=cntq;++i)
	{
		while(q[i].l<l) add(--l);
		while(q[i].r>r) add(++r);
		while(q[i].l>l) sub(l++);
		while(q[i].r<r) sub(r--);
		while(q[i].time>tim){
			++tim;
			if(q[i].l<=g[tim].wz&&q[i].r>=g[tim].wz)
			{
				if(num[a[g[tim].wz]]==1) --res;
				--num[a[g[tim].wz]];
				if(num[a[g[tim].color]]==0) ++res;
				++num[a[g[tim].color]];
			}
			swap(a[g[tim].color],g[tim].color);
		}
		while(q[i].time<tim){
			if(q[i].l<=g[tim].wz&&q[i].r>=g[tim].wz)
			{
				if(num[a[g[tim].color]]==1) --res;
				--num[a[g[tim].color]];
				if(num[a[g[tim].wz]]==0) ++res;
				++num[a[g[tim].wz]];
			}
			--tim;
			swap(a[g[tim].color],g[tim].color);
		}
		ans[q[i].ID]=res;
	}
	for(int i=1;i<=cntq;++i)
		printf("%lld\n",ans[i]);
	return 0;
}
inline int read(){
	int x=0;int b=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-') b=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*b;
}

0 条评论

目前还没有评论...