splay 是通过 splay 操作均摊复杂度，而旋转 treap 也旋转，但是是通过随机赋权使得复杂度在期望下正确。
具体来说就是再随机赋一个权值 \(rank\) ，通过旋转使得这棵树的 \(val\) 满足二叉搜索树且 \(rank\) 满足小根堆。
具体来说，在查询的时候是不旋转的，只有在插入和删除时有旋转。
插入时正常往里插，回溯维护的时候，判断 \(rank\) 是否满足小根堆的性质，不满足就转一下。
删除时正常删，到要删除一个节点时，如果左右儿子不全有，那么就直接删，然后回溯维护 \(siz\) ；如果左右儿子都出现 ，那么把 \(rank\) 小的专上来，然后递归删除转下去的目前节点。
代码如下（指针实现）：
```cpp
#include<bits/stdc++.h>
using namespace std;
#if linux
random_device RD;
mt19937_64 rnd(RD());
#else
mt19937_64 rnd(time(0));
#endif
struct node{
node* son[2];
int val,cnt,siz;
uint_fast64_t rank;
node(int num=0){val=num,cnt=siz=1,rank=rnd(),son[0]=son[1]=nullptr;}
void upt(){
siz=cnt+(son[0]!=nullptr?son[0]->siz:0)+(son[1]!=nullptr?son[1]->siz:0);
}
};
class Treap{
private:
node* root=nullptr;
void rotate(node* &cur,int dir){// 0 right,1 left
node* x=cur->son[dir];
cur->son[dir]=x->son[dir^1];
x->son[dir^1]=cur;
cur->upt();
x->upt();
cur=x;
}
void _ins(node* &cur,int num){
if (cur==nullptr){
cur=new node(num);
return;
}
if (num==cur->val){
++cur->cnt;
++cur->siz;
return;
}
if (num<cur->val){
_ins(cur->son[0],num);
if (cur->son[0]->rank<cur->rank) rotate(cur,0);
cur->upt();
}
else{
_ins(cur->son[1],num);
if (cur->son[1]->rank<cur->rank) rotate(cur,1);
cur->upt();
}
}
void _del(node* &cur,int num){
if (cur==nullptr) return;
if (num<cur->val){
_del(cur->son[0],num);
cur->upt();
return;
}
if (num>cur->val){
_del(cur->son[1],num);
cur->upt();
return;
}
if (cur->cnt>1){
--cur->cnt;
--cur->siz;
return;
}
node* tmp=cur;
if (cur->son[0]==nullptr && cur->son[1]==nullptr){
cur=nullptr;
delete tmp;
}
else if (cur->son[0]==nullptr && cur->son[1]!=nullptr){
cur=cur->son[1];
delete tmp;
}
else if (cur->son[0]!=nullptr && cur->son[1]==nullptr){
cur=cur->son[0];
delete tmp;
}
else{
int dir=cur->son[0]->rank<cur->son[1]->rank?1:0;
rotate(cur,dir);
_del(cur->son[dir^1],num);
cur->upt();
}
}
int _askrk(node* cur,int num){
if (cur==nullptr) return 1;
int less_siz=cur->son[0]==nullptr?0:cur->son[0]->siz;
if (cur->val==num) return less_siz+1;
if (num<cur->val) return _askrk(cur->son[0],num);
return less_siz+cur->cnt+_askrk(cur->son[1],num);
}
int _asknum(node* cur,int rk){
int less_siz=cur->son[0]==nullptr?0:cur->son[0]->siz;
if (rk<=less_siz) return _asknum(cur->son[0],rk);
if (rk<=less_siz+cur->cnt) return cur->val;
return _asknum(cur->son[1],rk-less_siz-cur->cnt);
}
int pre_tmp,suf_tmp;
int _askpre(node* cur,int num){
if (num<=cur->val){
if (cur->son[0]!=nullptr) return _askpre(cur->son[0],num);
}
else{
pre_tmp=cur->val;
if (cur->son[1]!=nullptr) _askpre(cur->son[1],num);
return pre_tmp;
}
return -1e9;
}
int _asksuf(node* cur,int num){
if (num>=cur->val){
if (cur->son[1]!=nullptr) return _asksuf(cur->son[1],num);
}
else{
suf_tmp=cur->val;
if (cur->son[0]!=nullptr) _asksuf(cur->son[0],num);
return suf_tmp;
}
return 1e9;
}
public:
void ins(int num){_ins(root,num);}
void del(int num){_del(root,num);}
int askrk(int num){return _askrk(root,num);}
int asknum(int rk){return _asknum(root,rk);}
int askpre(int num){return _askpre(root,num);}
int asksuf(int num){return _asksuf(root,num);}
}treap;
int n;
int main(){
scanf("%d",&n);
for (int op,x,i=1;i<=n;++i){
scanf("%d%d",&op,&x);
cerr<<i<<endl;
if (op==1) treap.ins(x);
else if (op==2) treap.del(x);
else if (op==3) printf("%d\n",treap.askrk(x));
else if (op==4) printf("%d\n",treap.asknum(x));
else if (op==5) printf("%d\n",treap.askpre(x));
else printf("%d\n",treap.asksuf(x));
}
return 0;
}