#include<bits/stdc++.h>
using namespace std;
const int N=1e5+9;
int q,a[N],w[N],son[N][2],f[N],cnt[N],sz[N],rt;
#define pushup(p) sz[p]=sz[son[p][0]]+sz[son[p][1]]+cnt[p]
void rotate(int x,bool y){
	int a=f[x],b=f[f[x]],c=son[x][!y];
	if(b){
		if(a==son[b][0]) son[b][0]=x;
		else son[b][1]=x;
	}
	else rt=x;
	f[x]=b; 
	son[x][!y]=a,f[a]=x;
	if(c) f[c]=a;
	son[a][y]=c;
	pushup(x);pushup(a); 
}
void up(int x){
	while(x!=rt&&w[x]<w[f[x]]){
		if(x==son[f[x]][0]) rotate(x,0);
		else rotate(x,1);
	}
}
void ins(int p,int x){
	if(a[x]==a[p]) cnt[p]++;
	else{
		bool lr=a[x]>a[p];
		int s=son[p][lr];
		if(!s) son[p][lr]=x,f[x]=p,cnt[x]=sz[x]=1,up(x);
		else ins(s,x);
	}
	pushup(p);
}
void del(int &p,int x){
	if(!p) return;
	if(a[x]==a[p]){
		if(cnt[p]==1){
			if(son[p][0]||son[p][1]){
				if(!son[p][1]) rotate(son[p][0],0),del(son[p][1],x);
				else rotate(son[p][1],1),del(son[p][0],x);
			}
			else{
				cnt[p]=sz[p]=0;p=0;
				return;
			}
		}
		else cnt[p]--;
	}
	else del(son[p][a[x]>a[p]],x);
	pushup(p);
}
int getrank(int p,int x){
	if(!p) return 0;
	if(a[x]<a[p]) return getrank(son[p][0],x);
	if(a[x]==a[p]) return sz[son[p][0]];
	return sz[son[p][0]]+cnt[p]+getrank(son[p][1],x);
}
int getkth(int p,int x){
	if(!p) return 1e9;
	if(x<=sz[son[p][0]]) return getkth(son[p][0],x);
	if(x<=sz[son[p][0]]+cnt[p]) return a[p];
	return getkth(son[p][1],x-sz[son[p][0]]-cnt[p]);
}
int pre(int x){
	int p=rt,res=-1e9;
	while(p){
		if(x<=a[p]) p=son[p][0];
		else res=a[p],p=son[p][1];
	}
	return res;
}
int nxt(int x){
	int p=rt,res=1e9;
	while(p){
		if(x>=a[p]) p=son[p][1];
		else res=a[p],p=son[p][0];
	}
	return res;
}
void print(int x){
	if(son[x][0]) print(son[x][0]);
	cout<<a[x]<<' ';
	if(son[x][1]) print(son[x][1]);
}
int main(){
	srand(time(0));
	cin>>q;
	for(int i=1;i<=q;i++){
		int op;
		cin>>op>>a[i],w[i]=rand();
		if(op==1){
			if(rt) ins(rt,i);
			else rt=i,cnt[rt]=sz[rt]=1;
		}
		if(op==2) del(rt,i);
		if(op==3) cout<<getrank(rt,i)+1<<endl;
		if(op==4) cout<<getkth(rt,a[i])<<endl;
		if(op==5) cout<<pre(a[i])<<endl;
		if(op==6) cout<<nxt(a[i])<<endl;
//		print(rt);
//		puts("");
	}
	return 0;
}

记录

另外本地测大样例时会出现几次运行结果不一样的问题，怀疑是UB