rt,普通平衡树，用rand就AC，用mt19937就会WA

代码

#include<bits/stdc++.h>
#define EL puts("Elaina")
#define reg register int
using namespace std;
inline char gc(){
    static char buf[1<<20],*p1,*p2;
    if(p1==p2){p1=buf,p2=buf+fread(buf,1,1<<20,stdin);if(p1==p2)return EOF;}
    return *p1++;
}
inline int read(){
    int x=0,f=1;char ch=gc();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=gc();
    return x*f;
}
mt19937 rnd(time(0));
const int maxn=1e5+3,INF=0x7fffffff;
struct Treap{
	int l,r,val,dat,cnt,siz;
}t[maxn];
int adr,root;
inline int New(int val){
	t[++adr].val=val;
	t[adr].dat=rnd();
	t[adr].cnt=t[adr].siz=1;
	return adr;
}
inline void updata(int p){
	t[p].siz=t[t[p].l].siz+t[t[p].r].siz+t[p].cnt;
}
inline int getrank(int p,int val){
	if(p==0)return 0;
	if(val==t[p].val)return t[t[p].l].siz+1;
	if(val<t[p].val)return getrank(t[p].l,val);
	return getrank(t[p].r,val)+t[t[p].l].siz+t[p].cnt;
}
inline int getval(int p,int rank){
	if(p==0)return INF;
	if(t[t[p].l].siz>=rank)return getval(t[p].l,rank);
	if(t[t[p].l].siz+t[p].cnt>=rank)return t[p].val;
	return getval(t[p].r,rank-t[t[p].l].siz-t[p].cnt);
}
inline void zig(int &p){//右旋
	int q=t[p].l;
	t[p].l=t[q].r,t[q].r=p,p=q;
	updata(t[p].r),updata(p); 
}
inline void zag(int &p){//左旋
	int q=t[p].r;
	t[p].r=t[q].l,t[q].l=p,p=q;
	updata(t[p].l),updata(p); 
}
inline void insert(int &p,int val){
	if(p==0)p=New(val);
	else if(val==t[p].val)t[p].cnt++,updata(p);
	else{
		if(val<t[p].val){
			insert(t[p].l,val);
			if(t[p].dat<t[t[p].l].dat)zig(p);
		}
		else{
			insert(t[p].r,val);
			if(t[p].dat<t[t[p].r].dat)zag(p);
		}
		updata(p);
	}
}
inline void remove(int &p,int val){
	if(p==0)return;
	if(val==t[p].val){
		if(t[p].cnt>1){
			t[p].cnt--,updata(p);
			return;
		}
		if(t[p].l||t[p].r){
			if((!t[p].r)||t[t[p].l].dat>t[t[p].r].dat)
				zig(p),remove(t[p].r,val);
			else
				zag(p),remove(t[p].l,val);
			updata(p);
		}
		else p=0;
		return;
	}
	val<t[p].val?remove(t[p].l,val):remove(t[p].r,val);
	updata(p);
}
inline int getpre(int val){
	int ans=-INF,p=root;
	while(p){
		if(t[p].val<val)ans=t[p].val,p=t[p].r;
        else p=t[p].l;
	}
	return ans;
}
inline int getnext(int val){
	int ans=INF,p=root;
	while(p){
		if(t[p].val>val)ans=t[p].val,p=t[p].l;
        else p=t[p].r;
	}
	return ans;
}
void MyDearMomonts(){
    int n=read();
    while(n--){
        int opt=read(),x=read();
        if(opt==1)insert(root,x);
        else if(opt==2)remove(root,x);
        else if(opt==3)printf("%d\n",getrank(root,x));
        else if(opt==4)printf("%d\n",getval(root,x));
        else if(opt==5)printf("%d\n",getpre(x));
        else printf("%d\n",getnext(x));
    }
}
int main(){
	MyDearMomonts();
    return (0^0);
}