此处仅提供优质模板——
若想学习可看此优秀博文：
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;
}