记录。

#include<bits/stdc++.h> 
//#define int long long
#define doub long double
#define m_p make_pair
#define up(i,l,r) for(int (i)=(l);(i)<=(r);(i)++)
#define dn(i,l,r) for(int (i)=(l);(i)>=(r);(i)--)
using namespace std;
const int maxn=1.5e5;
int n,m;
int B;
int a[maxn];
int b[maxn];
int ans;
int L=1,R=0;
int T=0;
int cnt[1000007];
struct qry{
	int l,r,t,id;
}qq[maxn];
struct rpd{
	int x,r,p;
}qc[maxn];
int qa[maxn];
int upd(int p,int tg){
	if(tg==1){
		if(!cnt[a[p]])ans++;
		cnt[a[p]]++;
	}
	else if(tg==-1){
		cnt[a[p]]--;
		if(!cnt[a[p]])ans--;
	}
}
bool cmp1(qry x,qry y){
	if(x.l/B==y.l/B){
		if(x.r/B==y.r/B)return x.t<y.t;
		return x.r/B<y.r/B;
	}
	return x.l/B<y.l/B;
}
void slv(int l,int r,int t){
	while(L>l)upd(--L,1);
	while(L<l)upd(L++,-1);
	while(R<r)upd(++R,1);
	while(R>r)upd(R--,-1);
	while(T<t){
		T++;
		if(qc[T].x>=L&&qc[T].x<=R){
			cnt[a[qc[T].x]]--;
			if(!cnt[a[qc[T].x]])ans--;
			a[qc[T].x]=qc[T].p;
			if(!cnt[a[qc[T].x]])ans++;
			cnt[a[qc[T].x]]++;
		}
		else{
			a[qc[T].x]=qc[T].p;
		}
	}
	while(T>t){
		if(qc[T].x>=L&&qc[T].x<=R){
			cnt[a[qc[T].x]]--;
			if(!cnt[a[qc[T].x]])ans--;
			a[qc[T].x]=qc[T].r;
			if(!cnt[a[qc[T].x]])ans++;
			cnt[a[qc[T].x]]++;
		}
		else{
			a[qc[T].x]=qc[T].r;
		}
		T--;
	}
}
int tt=0;
int qqc=0;
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	for(int i=1;i<=m;i++){
		char op;
		cin>>op;
		if(op=='Q'){
			int l,r;
			cin>>l>>r;
			qq[qqc+1]=(qry){l,r,tt,qqc+1};
			qqc++;
		}
		else{
			tt++;
			int x,p;
			cin>>x>>p;
			rpd R={x,b[x],p};
			qc[tt]=R;
			b[x]=p;
		}
	}
	B=pow(n,2.0/3);
	sort(qq+1,qq+qqc+1,cmp1);
	for(int i=1;i<=qqc;i++){
		slv(qq[i].l,qq[i].r,qq[i].t);
		qa[qq[i].id]=ans;
	}
	for(int i=1;i<=qqc;i++)cout<<qa[i]<<endl;
}