RT,以一个关注作为回报，求求了...马蜂不好请见谅..

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=133338;
const int MR=1e6+5;
int n,m,sq;
int x[MAXN];
struct ask{
	int l,r,id,la;
}a[MAXN];
struct change{
	int p,c;
}g[MAXN];
int l=1,r=0,t=0,p=0;
int u,v;
int cnt[MR];
int ans[MAXN];
bool cmp(ask x,ask y){
	if(x.l/sq!=y.l/sq) return x.l<y.l;
	if(x.l/sq&1) return x.r>y.r;
	return x.r<y.r;
}
void add(int k){
	if(cnt[k]++==0) p++;
}
void del(int k){
	if(--cnt[k]==0) p--;
}
void cha (int k){
	if(g[k].c>=l&&g[k].c<=r)
		del(x[g[k].p]),
		add(g[k].c);
	swap(x[g[k].p],g[k].c);
}
int main(){
	cin>>n>>m;
	sq=sqrt(n);
	for(int i=1;i<=n;i++)
		cin>>x[i];
	for(int i=1;i<=m;i++){
		char c;
		cin>>c;
		if(c=='Q'){
			u++;
			cin>>a[u].l>>a[u].r;
			a[u].id=u;
			a[u].la=v;
		}
		else{
			v++;
			cin>>g[v].p>>g[v].c;
		}
	}
	sort(a+1,a+u+1,cmp);
	for(int i=1;i<=u;i++){
		while(l>a[i].l) add(x[--l]);
		while(l<a[i].l) del(x[l++]);
		while(r<a[i].r) add(x[++r]);
		while(r>a[i].r) del(x[r--]);
		while(t>a[i].la) cha(t--);
		while(t<a[i].la) cha(++t);
		ans[a[i].id]=p;
	}
	for(int i=1;i<=u;i++)	
		cout<<ans[i]<<endl;
	return 0;
}