p.s.我按着讨论区把能优化的都优化了，还是T...

#include<bits/stdc++.h>
using namespace std;
const int N=133335,M=1000005;
struct node{
	int l,r,id,tim;
}q[N];
struct upd{
	int pre,col,pos;
}c[N];
int read(){
	int num=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')  f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num*f;
}
int n,m,k,ql=0,cl=0;
int a[N],idx[N],t[M];
int last[N];
int ans[N];
bool cmp1(const node &x,const node &y){
	if(idx[x.l]!=idx[y.l])  return idx[x.l]<idx[y.l];
	if(x.r!=y.r)  return x.r<y.r;
	return x.tim<y.tim;
}
void work(){
	int l=1,r=1,s=1,now=0;
	t[a[1]]++;
	for(int i=1;i<=ql;++i){
		for(int j=now+1;j<=q[i].tim;++j){
			if(c[j].pos>=l&&c[j].pos<=r){
				t[c[j].pre]--;
				if(t[c[j].pre]==0)  s--;
				t[c[j].col]++;
				if(t[c[j].col]==1)  s++;
			}
			a[c[j].pos]=c[j].col;
		}
		for(int j=now;j>=q[i].tim+1;--j){
			if(c[j].pos>=l&&c[j].pos<=r){
				t[c[j].col]--;
				if(t[c[j].col]==0)  s--;
				t[c[j].pre]++;
				if(t[c[j].pre]==1)  s++;
			}
			a[c[j].pos]=c[j].pre;
		}
		while(l>q[i].l){
			l--;
			t[a[l]]++;
			if(t[a[l]]==1)  s++;
		}
		while(r<q[i].r){
			r++;
			t[a[r]]++;
			if(t[a[r]]==1)  s++;
		}
		while(l<q[i].l){
			t[a[l]]--;
			if(t[a[l]]==0)  s--;
			l++;
		}
		while(r>q[i].r){
			t[a[r]]--;
			if(t[a[r]]==0)  s--;
			r--;
		}
		ans[q[i].id]=s;
		now=q[i].tim;
	}
}
int main(){
	n=read();m=read();
	memset(t,0,sizeof(t));
	k=pow(n,0.666);
	for(int i=1;i<=n;++i){
		a[i]=read();
		last[i]=a[i];
		idx[i]=(i-1)/k+1;
	}
	for(int i=1;i<=m;++i){
		char opt[3];
		cin>>opt;
		int xi=read(),yi=read();
		if(opt[0]=='Q'){
			q[++ql].l=xi;
			q[ql].r=yi;
			q[ql].id=ql;
			q[ql].tim=cl;
		}
		else{
			c[++cl].pre=last[xi];
			c[cl].col=yi;
			c[cl].pos=xi;
			last[xi]=yi;
		}
	}
	sort(q+1,q+ql+1,cmp1);
	work();
	for(int i=1;i<=ql;++i)
	  printf("%d\n",ans[i]);
	return 0;
}