带修莫队

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int a[maxn],x[maxn],res[maxn],cnt[maxn],ans;
char op;
struct quest{
	int l,r,tim,id;
}q[maxn];
struct Node{
	int pos,val;
}d[maxn];
bool cmp(quest a,quest b){
	if(x[a.l]!=x[b.l]) return x[a.l]<x[b.l];
	if(x[a.r]!=x[b.r]) return x[a.r]<x[a.r];
	return a.tim<b.tim;
} 
void add(int u){
	if(++cnt[a[u]]==1) ans++;
}
void del(int u){
	if(--cnt[a[u]]==0) ans--;
}
void upd(int tim,int i){
	if(d[tim].pos>=q[i].l&&d[tim].pos<=q[i].r){
		if((--cnt[a[d[tim].pos]])==0) ans--;
		if((++cnt[d[tim].val])==1) ans++;
	}
	swap(d[tim].val,a[d[tim].pos]);
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n,m,l,r,size,TIME,CNT,now;
	while(cin>>n>>m){
		size=pow(n,0.666); 
		for(register int i=1;i<=n;i++)
			cin>>a[i],x[i]=(i-1)/size+1;
		TIME=0; CNT=0;	
		for(register int i=1;i<=m;i++){
			cin>>op;
			if(op=='Q'){
				CNT++;
				cin>>q[CNT].l>>q[CNT].r;
				q[CNT].id=CNT; q[CNT].tim=TIME;
			}
			if(op=='R'){
				TIME++;
				cin>>d[TIME].pos>>d[TIME].val;
			}
		}
		sort(q+1,q+CNT+1,cmp);
		l=1; r=0; now=0; ans=0;
		memset(cnt,0,sizeof(cnt));
		for(register int i=1;i<=CNT;i++)
		{
			int ql=q[i].l,qr=q[i].r,qt=q[i].tim;
			while(l<ql) del(l++); 
			while(l>ql) add(--l); 
			while(r<qr) add(++r); 
			while(r>qr) del(r--); 
			while(now<qt) upd(++now,i); 
			while(now>qt) upd(now--,i); 
			res[q[i].id]=ans;
		}
		for(register int i=1;i<=CNT;i++)
			cout<<res[i]<<endl;
	}
}

58分，蒟蒻不会卡常QAQ

请求大佬教教