可以过BST模板,交上去随机WA+TLE+MLE

#include<bits/stdc++.h>
using namespace std;

struct Treap{
	int val,cnt,ls,rs,siz;
	bool flag;
	int dat;
}T[100050];

int q,op,x,n=5,root=1;

void build_tree(){
	T[1].flag=1;
	T[1].val=2147483647;
	T[1].cnt=1;
	T[1].ls=2;
	T[1].rs=3;
	T[1].siz=2;
	T[1].dat=rand();
	T[2].flag=1;
	T[2].val=-2147483647;
	T[2].cnt=1;
	T[2].ls=4;
	T[2].rs=5;
	T[2].siz=1;
	T[2].dat=rand()%T[1].dat;
}

void update(int no){
	T[no].siz=T[T[no].ls].siz+T[T[no].rs].siz+T[no].cnt;
}

int zig(int no){
	int save=T[no].ls;
	T[no].ls=T[T[no].ls].rs;
	T[save].rs=no;
	update(no);
	update(save);
	return save;
}

int zag(int no){
	int save=T[no].rs;
	T[no].rs=T[T[no].rs].ls;
	T[save].ls=no;
	update(no);
	update(save);
	return save;
}

void add(int no){
	if(T[no].flag==0){
		T[no].flag=1;
		T[no].val=x;
		T[no].ls=++n;
		T[no].rs=++n;
		T[no].cnt=1;
		T[no].siz=1;
		T[no].dat=rand();
		return;
	}T[no].siz++;
	if(x<T[no].val){
		add(T[no].ls);
		if(T[T[T[no].ls].rs].flag==1&&T[T[no].ls].dat>T[T[T[no].ls].rs].dat){
			T[no].ls=zag(T[no].ls);
		} 
	}if(x>T[no].val){
		add(T[no].rs);
		if(T[T[T[no].rs].ls].flag==1&&T[T[no].rs].dat>T[T[T[no].rs].ls].dat){
			T[no].rs=zig(T[no].rs);
		}
	}if(x==T[no].val)T[no].cnt++;
}

int getmin(int no){
	if(T[T[no].rs].flag==0)return no;
	T[no].siz--;
	return getmin(T[no].ls);
}

void delete_num(int no){
	if(T[no].flag==0)return;
	T[no].siz--;
	if(T[no].val==x){
		if(T[no].cnt>1){
			T[no].cnt--;
			return;
		}if(T[T[no].ls].flag==0&&T[T[no].rs].flag==0){
			T[no].flag=0;
			return;
		}if(T[T[no].ls].flag==1&&T[T[no].rs].flag==1){
			int change=getmin(T[no].rs);
			T[no].val=T[change].val;
			T[no].cnt=T[change].siz;
			T[change].flag=0;
			return;
		}if(T[T[no].ls].flag==1){
			T[no]=T[T[no].ls];
			return;
		}if(T[T[no].rs].flag==1){
			T[no]=T[T[no].rs];
			return;
		}
	}
	delete_num(T[no].ls);
	delete_num(T[no].rs);
	update(no);
}

int find_no(int no){
	if(T[no].flag==0)return 0;
	if(T[no].val==x)return T[T[no].ls].siz;
	if(T[no].val>x)return find_no(T[no].ls);
	if(T[no].val<x)return find_no(T[no].rs)+T[T[no].ls].siz+T[no].cnt;
}

int find_num(int no){
	if(T[T[no].ls].siz>=x)return find_num(T[no].ls);
	if(T[T[no].ls].siz+T[no].cnt>=x)return T[no].val;
	x-=T[T[no].ls].siz+T[no].cnt;
	return find_num(T[no].rs);
}

int find_last(int no){
	if(T[no].flag==0)return -2147483647;
	if(T[no].val>=x)return find_last(T[no].ls);
	if(T[no].val<x)return max(T[no].val,find_last(T[no].rs));
}

int find_next(int no){
	if(T[no].flag==0)return 2147483647;
	if(T[no].val<=x)return find_next(T[no].rs);
	if(T[no].val>x)return min(T[no].val,find_next(T[no].ls));
}

int main()
{
	srand(time(0));
	build_tree();
	cin>>q;
	while(q--){
		cin>>op>>x;
		if(op==1){
			add(root);
			if(T[root].dat>T[T[root].ls].dat&&T[T[T[root].ls].rs].flag==1)root=zig(root);
			if(T[root].dat>T[T[root].rs].dat&&T[T[T[root].rs].ls].flag==1)root=zag(root);
		}if(op==2)delete_num(root);
		if(op==3)cout<<find_no(root)<<endl;
		if(op==4){x++;cout<<find_num(root)<<endl;}
		if(op==5)cout<<find_last(root)<<endl;
		if(op==6)cout<<find_next(root)<<endl;
	}
	return 0;
}