记录编号	595202	评测结果	MMMMMMMMMMMM
题目名称	璐璐的治疗	最终得分	0
用户昵称	Hzoi_Mafia	是否通过	未通过
代码语言	C++	运行时间	0.010 s
提交时间	2024-10-10 12:21:59	内存使用	1.33 MiB

#include<bits/stdc++.h>
using namespace std;
const int inf=1000000000;
int n,m,cnt,tr[10000005],lch[10000005],rch[10000005],rt;
void pushup(int x){
	tr[x]=tr[lch[x]]+tr[rch[x]];
}
void update(int &x,int l,int r,int pos,int k){
	if(!x)x=++cnt;
	if(l==r){
		tr[x]+=k;
		return;
	}
	int mid((l+r)>>1);
	if(pos<=mid)update(lch[x],l,mid,pos,k);
	else update(rch[x],mid+1,r,pos,k);
	pushup(x);
}
int query(int ll,int rr,int l,int r,int x){
	if(!x)return 0;
	if(ll<=l&&r<=rr)return tr[x];
	int mid((l+r)>>1),ret(0);
	if(ll<=mid)ret+=query(ll,rr,l,mid,lch[x]);
	if(mid<rr)ret+=query(ll,rr,mid+1,r,rch[x]);
	return ret;
}
int Q(int l,int r,int k,int x){
	if(l==r)return l;
	int tmp=tr[lch[x]],mid=(l+r)>>1;
	if(k<=tmp)return Q(l,mid,k,lch[x]);
	return Q(mid+1,r,k-tr[lch[x]],rch[x]);
}
int kth(int x){
	return Q(1,inf,x,rt);
}
int opt,x,y;
int main(){
	freopen("ll.in","r",stdin);
	freopen("ll.out","w",stdout);
	cin>>n>>m;
	for(int i=1,x;i<=n;++i){
		cin>>x;
		update(rt,1,inf,x,1);
	}
	while(m--){
		cin>>opt;
		if(opt==1){
			cin>>x;
			update(rt,1,inf,x,-1);
		}
		else if(opt==2){
			cin>>x;
			update(rt,1,inf,x,1);
		}
		else if(opt==3){
			cin>>x>>y;
			update(rt,1,inf,x,-1);
			update(rt,1,inf,y,1);
		}
		else{
			cin>>x>>y;
			int ret=kth(x);
			cout<<ret<<'\n';
			update(rt,1,inf,ret,-1);
			update(rt,1,inf,ret+y,1);
		}
	}
}