捞

就就就一个普通treap。。。但一直过不了QAQ

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

const int N=1e5+5,INF=1e9;

struct treap{
	int l,r;//左右孩子
	int key;//关键字
	int cnt;//关键字出现次数
	int size;//子树大小
	int rd;//堆随机值
}t[N];

int n,cur,root;

void update(int u){
	t[u].size=t[t[u].l].size+t[t[u].r].size+1;
}

void rturn(int &u){//右旋
	int v=t[u].l;
	t[u].l=t[v].r;
	t[v].r=u;
	update(v);
	update(u);
	u=v;
}

void lturn(int &u){//左旋
	int v=t[u].r;
	t[u].r=t[v].l;
	t[v].l=u;
	update(v);
	update(u);
	u=v;
}

int new_point(int x){//新建一个空结点
	++cur;
	t[cur].key=x;
	t[cur].rd=rand();
	t[cur].size=t[cur].cnt=1;
	return cur;
}

void insert(int &u,int x){
	if(!u){//啥都没有
		u=new_point(x);//新建一个节点
		return;
	}
	if(t[u].key==x)++t[u].cnt;//已经存在则出现次数+1
	else{
		if(x<t[u].key){//递归左子树
			insert(t[u].l,x);
			if(t[u].rd>t[t[u].l].rd)rturn(u);//旋转保持平衡
		}
		else{//同理，递归右子树
			insert(t[u].r,x);
			if(t[u].rd>t[t[u].r].rd)lturn(u);//旋转
		}
	}
	update(u);
}

void remove(int &u,int x){
	if(!u)return;//找不到了，则没有这个点，那么直接return
	if(t[u].key==x){//定位到了
		if(t[u].cnt>1){//关键字出现了多次
			--t[u].cnt;//减去一个就行
			update(u);
			return;
		}
		if(t[u].l||t[u].r){//有儿子
			if(!t[u].r||t[t[u].l].rd>t[t[u].r].rd){//优先级大的补上来
				rturn(u);
				remove(t[u].r,x);
			}
			else{
				lturn(u);
				remove(t[u].l,x);
			}
		}
		else u=0;//发现是叶子节点，直接删
		return;
	}
	if(x<t[u].key)remove(t[u].l,x);
	else remove(t[u].r,x);
	update(u);
}

int get_rank(int u,int x){
	if(!u)return 1;
	if(t[u].key>=x)return get_rank(t[u].l,x);
	return get_rank(t[u].r,x)+t[t[u].l].size+1;
}

int find_rank(int u,int x){
	if(t[t[u].l].size==x-1)return t[u].key;
	else if(t[t[u].l].size>=x)return find_rank(t[u].l,x);
	return find_rank(t[u].r,x-t[t[u].l].size-1);
}

int get_pre(int u,int x){
	if(!u)return -INF;
	if(t[u].key<x)return max(t[u].key,get_pre(t[u].r,x));
	else return get_pre(t[u].l,x);
}

int get_next(int u,int x){
	if(!u)return INF;
	if(t[u].key>x)return min(t[u].key,get_next(t[u].l,x));
	else return get_next(t[u].r,x);
}

int main(){
	scanf("%d",&n);
	while(n--){
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1)insert(root,x);
		if(opt==2)remove(root,x);
		if(opt==3)printf("%d\n",get_rank(root,x));
		if(opt==4)printf("%d\n",find_rank(root,x));
		if(opt==5)printf("%d\n",get_pre(root,x));
		if(opt==6)printf("%d\n",get_next(root,x));
	}
	return 0;
}