莫队64分，TLE7-12，求调>_<

#include<bits/stdc++.h>
using namespace std;
#define ci(a) scanf("%lld",&a);
#define fo(i,a,b) for(ll i=a;i<=b;i++) 
typedef long long ll;
struct WRC{
	ll l,r,id,pre;
}w[1000000];
struct R{
	ll p,v;
}r[1000000];
ll n,m,k,a[1000000],block,res[1000000],cnt[1000000];
ll q,num,belong[1000000],ans,sum[1000000];
bool comp(WRC a,WRC b){
	if(a.l!=b.l) return belong[a.l]<belong[b.l];
	if(a.r!=b.r) return belong[a.r]<belong[b.r];
	return a.pre<b.pre;
}
void add(ll x){
	if(cnt[x]==0) ans++;
	cnt[x]++;
}
void app(ll x){
	cnt[x]--;
	if(cnt[x]==0) ans--;
} 
int main(){
	ci(n); ci(m);
	block=sqrt(n);
	fo(i,1,n) {
		ci(a[i]);
		belong[i]=i/block;
	}
	fo(i,1,m){
		char st; cin>>st;
		if(st=='Q'){
			num++;
			ci(w[num].l); ci(w[num].r);
			w[num].id=num; w[num].pre=q;
		}
		else{
			q++;
			ci(r[q].p); ci(r[q].v);
		}
	}
	sort(w+1,w+1+num,comp);
	int x=1,y=0,now=0;
	fo(i,1,num){
		ll l=w[i].l,r1=w[i].r;
		while(x>l){
			if(cnt[a[--x]]==0) 
			ans++;
			cnt[a[--x]]++;
		}
		while(x<l) {
			if(cnt[a[x++]]==0) 
			ans++;
			cnt[a[x++]]++;
		}
		while(y>r1) {
			if(cnt[a[y--]]==0) 
			ans++;
			cnt[a[y--]]++;
		}
		while(y<r1) {
			if(cnt[a[++y]]==0) 
			ans++;
			cnt[a[++y]]++;
		}
while(now<w[i].pre) {
	++now;
	if(r[now].p>=w[i].l&&r[now].p<=w[i].r){
		--cnt[a[r[now].p]];
		++cnt[r[now].v];
		if(cnt[a[r[now].p]]==0) ans--;
		if(cnt[r[now].v]==1) ans++; 
	}
	swap(r[now].v,a[r[now].p]);
}
while(now>w[i].pre){
if(r[now].p>=w[i].l&&r[now].p<=w[i].r){
	--cnt[a[r[now].p]];
	++cnt[r[now].v];
    if(cnt[a[r[now].p]]==0) ans--;
    if(cnt[r[now].v]==1) ans++; 
}
	    	swap(r[now].v,a[r[now].p]);
	    	now--;
	    }
        sum[w[i].id]=ans;
	}
	fo(i,1,num) printf("%lld\n",sum[i]);
	return 0;
}