RT

#include <bits/stdc++.h>
using namespace std;
const int N=133338;
struct node{
	int x,y,t,id,answ;
}a[N],b[N];//a修改b查询 
int n,m,T,p1,p2,ans; 
int col[N],buk[N];
int bef1[N],bef2[10*N];
int opt(int p){
	return (p+T-1)/T; 
} 
void add(int p){
	if(buk[p]==0) ans++;
	buk[p]++;
}
void del(int p){
	if(buk[p]==1) ans--;
	buk[p]--;
}
bool cmp1(node p,node q){
	if(opt(p.x)!=opt(q.x)) return p.x<q.x;
	if(opt(p.y)!=opt(q.y)) return p.y<q.y;
	return p.t<q.t;
}
bool cmp2(node p,node q){
	return p.id<q.id;
}
int main () {
	cin>>n>>m;
	T=pow(n,0.7);
	for(int i=1;i<=n;i++){
		cin>>col[i];
		bef1[i]=col[i];	
	}
	for(int i=1;i<=m;i++){
		char tp;
		int u,v;
		cin>>tp>>u>>v;
		if(tp=='Q'){
			p1++;
			a[p1]=(node){u,v,p2,i,0};
		}else{
			p2++;
			b[p2]=(node){u,v,p2,i,0};
			bef2[u]=bef1[u];
			bef1[u]=v;
		}
	}
	sort(a+1,a+p1+1,cmp1);
	int l=1,r=0,t=0;
	for(int i=1;i<=p1;i++){
		//cout<<a[i].id<<endl; 
		while(l>a[i].x) add(col[--l]);
		while(r<a[i].y) add(col[++r]);
		while(l<a[i].x) del(col[l++]);
		while(r>a[i].y) del(col[r--]);
		//cout<<ans<<endl;
		//还原 
		while(t>a[i].t&&t!=1){
			t--;
			int af=bef2[b[t].x];
			int be=bef1[b[t].x];
			if(b[t].x>=l&&b[t].x<=r){
				add(af);
				del(be);
			}
			col[b[t].x]=af;
		}
		//增加 
		while(t<a[i].t&&t!=p2){
			t++;
			int af=bef1[b[t].x];
			int be=bef2[b[t].x];
			//cout<<t<<" "<<af<<" "<<be<<endl;
			//cout<<t<<" "<<l<<" "<<r<<" "<<ans<<endl; 
			if(b[t].x>=l&&b[t].x<=r){
				add(af);
				del(be);
			}
			col[b[t].x]=af;
		}
		a[i].answ=ans;
	} 
	sort(a+1,a+p1+1,cmp2);
	for(int i=1;i<=p1;i++){
		cout<<a[i].answ<<"\n";
	}
	return 0;
}