小萌新求助CDQ分治（悬赏关注）

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 2919810
#define int long long
using namespace std;
int n,m,tot,col[N];
struct node{
	int t,x,y,typ,a;
	bool operator <(const node &fifi)const{return t<fifi.t;}
}q[N],tmp[N];
int w=1e6;
struct bit{
	int t[N];
	void clear(){memset(t,0,sizeof(t));}
	int lowbit(int x){return x&-x;}
	void add(int x,int v){for(;x<=w;x+=lowbit(x))t[x]+=v;}
	int query(int x){
		int ans=0;
		for(;x;x-=lowbit(x))ans+=t[x]?1:0;
		return ans;
	}
	void assign(int x,int v){for(;x<=w;x+=lowbit(x))t[x]=v;}
}b; 
void cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)/2;
	cdq(l,mid);cdq(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(q[i].x<=q[j].x){
			if(q[i].typ==1)b.add(q[i].y,q[i].a);
		//	printf("test:%lld %lld %lld %lld %lld \n",q[i].t,q[i].x,q[i].y,q[i].typ,q[i].a);
			tmp[k++]=q[i++];
		}else{
			if(q[j].typ==2)q[j].a+=b.query(q[j].y);
		//	printf("test:%lld %lld %lld %lld %lld \n",q[j].t,q[j].x,q[j].y,q[j].typ,q[j].a);
			tmp[k++]=q[j++];
		}
	}
	while(i<=mid){
		if(q[i].typ==1)b.add(q[i].y,q[i].a);
	//	printf("test:%lld %lld %lld %lld %lld \n",q[i].t,q[i].x,q[i].y,q[i].typ,q[i].a);
		tmp[k++]=q[i++];
	}
	while(j<=r){
		if(q[j].typ==2)q[j].a+=b.query(q[j].y);
	//	printf("test:%lld %lld %lld %lld %lld \n",q[j].t,q[j].x,q[j].y,q[j].typ,q[j].a);
		tmp[k++]=q[j++];
	}
	
	for(int i=l;i<=mid;i++)if(q[i].typ==1)b.assign(q[i].y,0);
	for(int i=l;i<=r;i++)q[i]=tmp[i];
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		int a;
		scanf("%lld",&a);
		col[i]=a;
		q[++tot]={tot,i,a,1,1};
	}
	while(m--){
		char s[10];
		int x,y;
		scanf("%s%lld%lld",s,&x,&y);
		if(s[0]=='Q'){
			q[++tot]={tot,y,w,2,0};
			q[++tot]={tot,x-1,w,2,0};
		}else if(s[0]=='R'){
			q[++tot]={tot,x,col[x],1,-1};
			q[++tot]={tot,x,y,1,1};
			col[x]=y;
		}
	}
	//sort(q+1,q+tot+1);
	cdq(1,tot);
	sort(q+1,q+tot+1);
	for(int i=1;i<=tot;i++){
	//	printf("test:%lld %lld %lld %lld %lld \n",q[i].t,q[i].x,q[i].y,q[i].typ,q[i].a);
		if(q[i].typ==2){
			printf("%lld\n",q[i].a-q[i+1].a);
			i++;
		}
	}
	return 0;
}