最近开始学习平衡树，在学长的强烈推荐下学习了AVL、红黑树、splay（以上我都还没学）treap。
首先讲一下个人对treap（树堆）的理解。
treap，顾名思义，就是tree+heap，首先因为treap是一棵平衡树，因此它满足二叉排序树的性质，接下来，为了防止BST退化成一条链，它使用了随机化的方式给每个点分布一个优先级，然后要求优先级满足堆的性质，但不必是一棵完全二叉树，这样的效率期望就是每次基础操作\( \log n \)的。
然后简单讲一下树堆的基础操作，代码参见例题与AC代码。
1.插入 平衡树最基础的操作之一就是插入一个新节点，首先我们按照BST的性质插入这个节点，接下来按照优先级进行旋转维护堆的性质，这样就可以了。
2.删除 平衡树最基础的操作之二就是删除一个原有节点，同样的我们按照BST的性质找到这个节点，然后按照BST的方法删除它，接下来维护堆的性质即可。
3.查找 平衡树最基础的操作之三就是查找，一般主要包含2种查找：1）给定一个权值，查找排名 2)给定一个排名，查找权值 这2种操作是大同小异的，都只需要按照BST的性质来进行即可。
下面是本题题解。
题目就是平衡树最基础的操作裸题，所以就直接参考上面所说的以及代码就好了。(1912KB 232ms on BZOJ)
#include <stdio.h>
#define getchar() (S==TT&&(TT=(S=BB)+fread(BB,1,1<<15,stdin),S==TT)?EOF:*S++)
char BB[<<],*TT=BB,*S=BB;
inline int read(){
int x=,f=;char ch=getchar();
while (ch<''||ch>'') f=ch=='-'?-:,ch=getchar();
while (ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();
return x*f;
}
inline int rad(){
static int x=;
x^=x<<,x^=x>>,x^=x<<;return x;
}
struct treap{
treap *ls,*rs;
int val,pri,cnt,sz;
treap(int val):val(val){ls=rs=NULL,cnt=sz=,pri=rad();}
void combine(){sz=cnt;if (ls!=NULL) sz+=ls->sz;if (rs!=NULL) sz+=rs->sz;}
}*root;
inline void lrotate(treap* &x){treap *y=x->rs;x->rs=y->ls;y->ls=x;y->sz=x->sz;x->combine();x=y;}
inline void rrotate(treap* &x){treap *y=x->ls;x->ls=y->rs;y->rs=x;y->sz=x->sz;x->combine();x=y;}
inline void Insert(treap* &x,int val){
if (x==NULL){x=new treap(val); return;}
if (val==x->val) x->cnt++;
else if (val>x->val){Insert(x->rs,val);if (x->rs->pri<x->pri) lrotate(x);}
else {Insert(x->ls,val);if (x->ls->pri<x->pri) rrotate(x);}x->combine();
}
void Delete(treap *&x,int val){
if (x==NULL) return;
if (val==x->val){
if (x->cnt>) x->cnt--,x->sz--;
else if (x->ls==NULL||x->rs==NULL){
treap *t=x;
if (x->ls==NULL) x=x->rs;
else x=x->ls;
delete t;
}
else if (x->ls->pri<x->rs->pri)
rrotate(x),Delete(x,val);
else lrotate(x),Delete(x,val);
}
else if (val<x->val) x->sz--,Delete(x->ls,val);
else x->sz--,Delete(x->rs,val);
}
inline int find(treap *x,int val){
if (x==NULL) return ;
if (x->ls==NULL){
if (val==x->val) return ;
if (val>x->val) return find(x->rs,val)+x->cnt;
return ;
}
if (val==x->val)return x->ls->sz+;
if (val<x->val) return find(x->ls,val);
return find(x->rs,val)+x->ls->sz+x->cnt;
}
inline int find_rank(treap *x,int k){
if (x==NULL) return ;
if (x->ls==NULL){
if (k<=x->cnt) return x->val;
else return find_rank(x->rs,k-x->cnt);
}
if (k<=x->ls->sz) return find_rank(x->ls,k);
if (k>x->ls->sz+x->cnt) return find_rank(x->rs,k-x->ls->sz-x->cnt);
return x->val;
}
int find_pre(treap *x,int val,int ans){
if (x==NULL) return ans;
if (val>x->val) return find_pre(x->rs,val,x->val);
return find_pre(x->ls,val,ans);
}
int find_nxt(treap *x,int val,int ans){
if (x==NULL) return ans;
if (val<x->val) return find_nxt(x->ls,val,x->val);
return find_nxt(x->rs,val,ans);
}
int main(){
int q=read();
while (q--){
int opt=read(),x=read();
switch (opt){
case :Insert(root,x); break;
case :Delete(root,x); break;
case :printf("%d\n",find(root,x)); break;
case :printf("%d\n",find_rank(root,x)); break;
case :printf("%d\n",find_pre(root,x,-)); break;
case :printf("%d\n",find_nxt(root,x,-)); break;
}
}
}