rt，tle on#7#8#9#10

#include<bits/stdc++.h>
using namespace std;
struct query{
	int l,r,id,t;
}q[133340];
struct replace{
	int loc,col;
}r[133340];
int n,m,sz,cnt,a[133340],b[1000005],ans[133340];
char s;
bool cmp(query a,query b){
	if(a.l/sz==b.l/sz){
		if(a.r/sz==b.r)a.t<b.t;
		return a.r<b.r;
	}
	return a.l<b.l;
}
void del(int x){
	b[x]--;
	if(b[x]==0)cnt--;
}
void add(int x){
	if(b[x]==0)cnt++;
	b[x]++;
}
void update(int que,int t){
	if(r[t].loc>=q[que].l&&r[t].loc<=q[que].r){
		del(a[r[t].loc]);
		add(r[t].col);
	}
	swap(a[r[t].loc],r[t].col);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	int cntQ=0,cntR=0;
	for(int i=1;i<=m;i++){
		cin>>s;
		if(s=='Q'){
			cntQ++;
			scanf("%d%d",&q[cntQ].l,&q[cntQ].r);
			q[cntQ].t=cntR,q[cntQ].id=cntQ;
		}
		else {
			cntR++;
			scanf("%d%d",&r[cntR].loc,&r[cntR].col);
		}
	}
	sz=pow(n,0.666);
	sort(q+1,q+cntQ+1,cmp);
	int l=0,r=0,t=0;
	for(int i=1;i<=cntQ;i++){
		while(l<q[i].l)del(a[l++]);
		while(l>q[i].l)add(a[--l]);
		while(r<q[i].r)add(a[++r]);
		while(r>q[i].r)del(a[r--]);
		while(t>q[i].t)update(i,t--);
		while(t<q[i].t)update(i,++t);
		ans[q[i].id]=cnt; 
	}
	for(int i=1;i<=cntQ;i++){
		printf("%d\n",ans[i]);
	}
	return 0;
}