rt，WA * 6，TLE * 4，不知道哪里出了问题。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll K,len,L[1000001],R[1000001],F[1000001],t,n;
void build(){
	len=exp((log(n)+log(t))/3),K=(n+len-1)/len;
	for(ll i=1;i<=K;i++)L[i]=R[i-1]+1,R[i]=L[i]+len-1;
	R[K]=n;
	for(ll i=1;i<=K;i++)
		for(ll j=L[i];j<=R[i];j++)F[j]=i;
}
struct query{
	ll l,r,t,id;
	bool operator<(const query& q) const{
		return F[l]==F[q.l]?(F[r]==F[q.r]?t<q.t:F[r]<F[q.r]):F[l]<F[q.l];
	}
}Q[1000001];
ll m,ans[1000001],ch[1000001][3],qlen,col[1000001],cnt[1000001];
ll sum,l=1,r=0;
inline void add(ll x){
	if(!cnt[col[x]])sum++;
	cnt[col[x]]++;
}
inline void del(ll x){
	cnt[col[x]]--;
	if(!cnt[col[x]])sum--;
}
inline void addc(ll x){
	if(l<=x&&x<=r)del(ch[x][0]);
	col[ch[x][0]]=ch[x][1];
	if(l<=x&&x<=r)add(ch[x][0]);
}
inline void delc(ll x){
	if(l<=x&&x<=r)del(ch[x][0]);
	col[ch[x][0]]=ch[x][2];
	if(l<=x&&x<=r)add(ch[x][0]);
}
inline void jmp(ll lp,ll rp,ll tp){
	while(l>lp)add(--l);
	while(r<rp)add(++r);
	while(l<lp)del(l++);
	while(r>rp)del(r--);
	while(t<tp)addc(++t);
	while(t>tp)delc(t--);
}

ll read() {
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
void write(ll x) {
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

int main(){
	n=read(),m=read();
	for(ll i=1;i<=n;i++)col[i]=read();
	for(ll i=1;i<=m;i++){
		char chr;
		cin>>chr;
		if(chr=='Q')qlen++,Q[qlen]={read(),read(),t,qlen};
		else 
			t++,ch[t][0]=read(),ch[t][1]=read(),ch[t][2]=col[ch[t][0]],col[ch[t][0]]=ch[t][1];
	}
	build();
	sort(Q+1,Q+1+qlen);
	for(ll i=1;i<=qlen;i++){
		jmp(Q[i].l,Q[i].r,Q[i].t);
		ans[Q[i].id]=sum;
	}
	for(ll i=1;i<=qlen;i++)write(ans[i]),putchar('\n');
	return 0;
}