此处仅提供优质模板——
若想学习可看此优秀博文：
Treap学习

#include <bits/stdc++.h>
#define INF 0x7f7f7f7f
using namespace std;
int n,siz,flag;
struct TREE
{
	int node,sum,num,r,son[2];
}FAST[100005];
void push1(int u) 
{
	FAST[u].node=FAST[FAST[u].son[0]].node+FAST[FAST[u].son[1]].node+FAST[u].sum;
}
void turn(int &NODE,int flag) 
{
	int wson=FAST[NODE].son[!flag];
	FAST[NODE].son[!flag]=FAST[wson].son[flag];
	FAST[wson].son[flag]=NODE;
	push1(NODE);
	push1(wson);
	NODE=wson;
}
void init(int &root,int k) 
{
	if (!root) 
	{
		root=++siz;
		FAST[root].node=FAST[root].sum=1;
		FAST[root].num=k;
		FAST[root].r=rand();
		return;
	}
	if (FAST[root].num==k) 
	{
		FAST[root].sum++;
		FAST[root].node++;
		return;
	}
	int AC=k>FAST[root].num;
	init(FAST[root].son[AC],k);
	if (FAST[root].r<FAST[FAST[root].son[AC]].r) turn(root,!AC);
	push1(root);
}
void det(int &root,int k)
{
	if (!root) return;
	if (k!=FAST[root].num) det(FAST[root].son[k>FAST[root].num],k);
	else 
	{
		if (!FAST[root].son[0] && !FAST[root].son[1]) 
		{
			FAST[root].sum--;
			FAST[root].node--;
			if (!FAST[root].sum) root=0;
		}
		else if (FAST[root].son[0] && !FAST[root].son[1]) 
		{
			turn(root,1);
			det(FAST[root].son[1],k);
		}
		else if (!FAST[root].son[0] && FAST[root].son[1]) 
		{
			turn(root,0);
			det(FAST[root].son[0],k);
		}
		else 
		{
		    int AK=FAST[FAST[root].son[0]].r>FAST[FAST[root].son[1]].r;
			turn(root,AK);
			det(FAST[root].son[AK],k);
		}
	}
	push1(root);
}
int DFS(int root,int k) 
{
	if (!root) return 0;
	if (FAST[root].num==k) return FAST[FAST[root].son[0]].node+1;
	if (FAST[root].num<k) 
	return FAST[FAST[root].son[0]].node+FAST[root].sum+DFS(FAST[root].son[1],k);
	return DFS(FAST[root].son[0],k);
}
int BFS(int root,int k) 
{
	if (!root) return 0;
	if (FAST[FAST[root].son[0]].node>=k) return BFS(FAST[root].son[0],k);
	else if (FAST[FAST[root].son[0]].node+FAST[root].sum<k) return BFS(FAST[root].son[1],k-FAST[root].sum-FAST[FAST[root].son[0]].node);
	return FAST[root].num;
}
int find1(int root,int k)
{
	if (!root) return -INF;
	if (FAST[root].num>=k) return find1(FAST[root].son[0],k);
	else return max(FAST[root].num,find1(FAST[root].son[1],k));
}
int find2(int root,int k) 
{
	if (!root) return INF;
	if (FAST[root].num<=k) return find2(FAST[root].son[1],k);
	else return min(FAST[root].num,find2(FAST[root].son[0],k));
}
int main() 
{
	cin>>n;
	while (n--) 
	{
		int typ,k;
		cin>>typ>>k;
		switch (typ)
		{
			case 1:init(flag,k);break;
			case 2:det(flag,k);break;
			case 3:cout<<DFS(flag,k)<<endl;break;
			case 4:cout<<BFS(flag,k)<<endl;break;
			case 5:cout<<find1(flag,k)<<endl;break;
			case 6:cout<<find2(flag,k)<<endl;break;
		}
	}
	return 0;
}