带修莫队求条

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+17;
int n,m,cnt1,cnt2;
int a[N],bu[N],res[N];
struct node{
	int l,r,pre,bl,br,num;
}query[N],ch[N];
void init(){
	int block=sqrt(n);
	for(int i=1;i<=cnt1;i++){
		query[i].bl=query[i].l/block;
		query[i].br=query[i].r/block;
	}
}
bool cmp(node x,node y){
	if(x.bl>y.bl)return true;
	else if(x.br>y.br)return true;
	else return x.pre<y.pre;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		char q;
		cin>>q;
		if(q=='Q'){
			int l,r;
			cin>>l>>r;
			query[++cnt1].l=l,query[cnt1].r=r;
			query[cnt1].pre=cnt2;
			query[cnt1].num=i;
		}
		else{
			int x,y;
			cin>>x>>y;
			ch[++cnt2].l=x,ch[cnt2].r=y;
		} 
	}
	init();
	sort(query+1,query+cnt1+1,cmp);
	int block=sqrt(n);
	int l,r,t,ans=0;
	l=1,r=0,t=0;
	for(int i=1;i<=cnt1;i++){
		while(r<query[i].r){
			r++;
			bu[a[r]]++;
			if(bu[a[r]]==1)ans++;
		}
		while(l>query[i].l){
			l--;
			bu[a[l]]++;
			if(bu[a[l]]==1)ans++;
		}
		while(r>query[i].r){
			bu[a[r]]--;
			if(bu[a[r]]==0)ans--;
			r--;
		}
		while(l<query[i].l){
			bu[a[l]]--;
			if(bu[a[l]]==0)ans--;
			l++;
		}
		while(t<query[i].pre){
			t++;
			bu[ch[t].l]--;
			if(bu[ch[t].l]==0)ans--;
			bu[ch[t].r]++;
			if(bu[ch[t].r]==1)ans++;
		}
		while(t>query[i].pre){
			bu[ch[t].l]++;
			if(bu[ch[t].l]==1)ans++;
			bu[ch[t].r]--;
			if(bu[ch[t].r]==0)ans--;
			t--;
		}
		res[query[i].num]=ans;
	}
	for(int i=1;i<=cnt1;i++){
		cout<<res[i]<<endl;
	}
	return 0;
}