RT，和一些整体二分AC代码对过了，感觉没啥区别，下面是代码：

#include<bits/stdc++.h>
const int INF=1e9;
using namespace std;
struct node{
	int op,x,y,z;
}q[2000005],lq[2000005],rq[2000005];
int ans[1000005],sum[1000005],a[1000005],pd[1000005],n,m,t,mm;
char c;
inline int lowbit(int x){
	return x&(-x);
}
inline void update(int x,int y){
	while(x<n){
		sum[x]+=y;
		x+=lowbit(x);
	}
}
inline int query(int x){
	int ans=0;
	while(x){
		ans+=sum[x];
		x-=lowbit(x);
	}
	return ans;
}
void divide(int l,int r,int s,int t){
	if(s>t)return;
	if(l==r){
		for(int i=s;i<=t;i++)
			if(q[i].op>0)ans[q[i].op]=l;
		return;
	}
	int mid=l+r>>1;
	int ls=0,rs=0; 
	for(int i=s;i<=t;i++){
		if(q[i].op==0){
			if(q[i].y<=mid){
				update(q[i].x,q[i].z);
				lq[++ls]=q[i];
			}
			else rq[++rs]=q[i];
		}
		else{
			int cnt=query(q[i].y)-query(q[i].x-1);
			if(cnt>=q[i].z)lq[++ls]=q[i];
			else {
				q[i].z-=cnt;
				rq[++rs]=q[i];
			}
		}
	}
	for(int i=s;i<=t;i++)
		if(q[i].op==0&&q[i].y<=mid)
			update(q[i].x,-q[i].z);
	for(int i=1;i<=ls;i++)
		q[s+i-1]=lq[i];
	for(int i=1;i<=rs;i++)
		q[s+ls+i-1]=rq[i];
	divide(l,mid,s,s+ls-1);
	divide(mid+1,r,s+ls,t);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&q[++t].y),q[t].op=0,q[t].x=i,q[t].z=1,a[i]=q[t].y;
	scanf("\n");
	for(int i=1;i<=m;i++){
		scanf("%c ",&c);
		if(c=='Q')scanf("%d%d%d\n",&q[++t].x,&q[t].y,&q[t].z),q[t].op=i,pd[i]=1;
		if(c=='C'){
			int x,y;
			scanf("%d%d\n",&x,&y);
			q[++t].op=0;
			q[t].x=x;
			q[t].y=a[x];
			q[t].z=-1;
			q[++t].op=0;
			q[t].x=x;
			q[t].y=y;
			q[t].z=1;
			a[x]=y;
		}
	}
	for(int i=1;i<=t;i++)
		printf("%d %d %d %d\n",q[i].op,q[i].x,q[i].y,q[i].z);
	divide(-INF,INF,1,t);
	for(int i=1;i<=m;i++)
		if(pd[i])printf("%d\n",ans[i]);
	return 0;
}