动态区间第K大

整体二分。

主要需要注意的一点是，对于每个删除操作，若删除操作被算入贡献，则最开始的插入操作也一定会被算入，所以不必担心删除删错。

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

#define LL  long long

#define FILE "dealing"

#define up(i,j,n) for(int i=j;i<=n;i++)

int read(){

	int x=0,f=1,ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return x*f;

}

const int maxn=800000,mod=1000000007,inf=10000000000000LL;

bool cmin(int& a,int b){return a>b?a=b,true:false;}

bool cmax(int& a,int b){return a<b?a=b,true:false;}

int ans[maxn];int n,m;

struct node{int x,y,k,id,op;}a[maxn],q1[maxn],q2[maxn];

char s[10];

int d[maxn],sum[maxn],v[maxn];

int lowbit(int x){return x&-x;}

void add(int x,int di){while(x<=n)d[x]+=di,x+=lowbit(x);}

int getsum(int x){int ans=0;while(x)ans+=d[x],x-=lowbit(x);return ans;}

void divide(int L,int R,int l,int r){

	if(l>r)return;

	if(L==R){

		up(i,l,r)if(a[i].op==2)ans[a[i].id]=L;

		return;

	}

	int mid=(L+R)>>1;

	up(i,l,r){

		if(a[i].op==1&&mid>=a[i].x)add(a[i].y,1);

		if(a[i].op==2)sum[i]=getsum(a[i].y)-getsum(a[i].x-1);

		if(a[i].op==3&&mid>=a[i].x)add(a[i].y,-1);

	}

	up(i,l,r){

		if(a[i].op==1&&mid>=a[i].x)add(a[i].y,-1);

		if(a[i].op==3&&mid>=a[i].x)add(a[i].y,1);

	}

	int top1=0,top2=0;

	up(i,l,r){

		if(a[i].op==2){

			if(sum[i]<=a[i].k){

				a[i].k-=sum[i];

				q2[++top2]=a[i];

			}else q1[++top1]=a[i];

		}

		else {

			if(a[i].x<=mid)q1[++top1]=a[i];

			else q2[++top2]=a[i];

		}

	}

	up(i,l,l+top1-1)a[i]=q1[i-l+1];

	up(i,l+top1,r)a[i]=q2[i-l-top1+1];

	divide(L,mid,l,l+top1-1);

	divide(mid+1,R,l+top1,r);

}

int main(){

	freopen(FILE".in","r",stdin);

	freopen(FILE".out","w",stdout);

	int T=read();

	while(T--){

		memset(ans,0,sizeof(ans));

		n=read(),m=read();int top=n;

		up(i,1,n){a[i].op=1;v[i]=a[i].x=read(),a[i].y=i,a[i].id=i;}

		up(i,1,m){

			scanf("%s",s);

			if(s[0]=='Q')a[++top].op=2,a[top].x=read(),a[top].id=i,a[top].y=read(),a[top].k=read()-1;

			else a[++top].op=3,a[top].y=read(),a[top].x=v[a[top].y],a[++top].op=1,a[top].x=read(),a[top].y=a[top-1].y,v[a[top].y]=a[top].x;

		}

		divide(0,mod,1,top);

		up(i,1,m)if(ans[i])printf("%d\n",ans[i]);

	}

	return 0;

}