第一个平衡树板子，有旋Treap。用随机函数规定一个堆，维护点权的同时维护堆的性质，可以有效地避免退化成链。按我的理解，建立一棵二叉排序树，树的形态会和给出节点的顺序有关。按照出题人很机智定理，数据肯定不会太容易操作，这时候就需要我们自行调整“数据顺序”，平衡树应运而生。

       这个板子涵盖的操作有左旋、右旋(维护堆性质)、添加节点、删除节点(建树相关)、查找第x个元素、查找元素排名、查找前驱、查找后继这8种操作。改变树本身的操作都是取地址传参的，询问操作则都是简单传参。原理不是太难理解，应用则看以后刷题了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int sj=100010;int n,opt,g,jg,cs,size;struct tree{    int l,r,v,w,rnd,size;}t[sj];void update(int x){    t[x].size=t[t[x].l].size+t[t[x].r].size+t[x].w;}void lturn(int &x){     int tt=t[x].r;     t[x].r=t[tt].l;     t[tt].l=x;     t[tt].size=t[x].size;     update(x);     x=tt;}void rturn(int &x){     int tt=t[x].l;     t[x].l=t[tt].r;     t[tt].r=x;     t[tt].size=t[x].size;     update(x);     x=tt;}void cr(int &x,int y){     if(x==0)     {        size++;        x=size;        t[x].size=t[x].w=1;        t[x].v=y;        t[x].rnd=rand();        return;     }     t[x].size++;     if(t[x].v==y) t[x].w++;     else if(y>t[x].v)     {         cr(t[x].r,y);         if(t[t[x].r].rnd
          
           1) { t[k].w--; t[k].size--; return; } if(t[k].l*t[k].r==0) k=t[k].l+t[k].r; else if(t[t[k].l].rnd
           
            t[k].v) t[k].size--,sc(t[k].r,x); else t[k].size--,sc(t[k].l,x);}int query_rank(int k,int x){ if(k==0) return 0; if(t[k].v==x) return t[t[k].l].size+1; else if(x>t[k].v) return t[t[k].l].size+t[k].w+query_rank(t[k].r,x); else return query_rank(t[k].l,x);}int query_num(int k,int x){ if(k==0) return 0; if(x<=t[t[k].l].size) return query_num(t[k].l,x); else if(x>t[t[k].l].size+t[k].w) return query_num(t[k].r,x-t[t[k].l].size-t[k].w); else return t[k].v;}void query_pre(int k,int x){ if(k==0) return; if(t[k].v
            
             x) jg=k,query_sub(t[k].l,x); else query_sub(t[k].r,x);}int main(){ //freopen("t.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&opt,&cs); if(opt==1) cr(g,cs); if(opt==2) sc(g,cs); if(opt==3) printf("%d\n",query_rank(g,cs)); if(opt==4) printf("%d\n",query_num(g,cs)); if(opt==5) { jg=0; query_pre(g,cs); printf("%d\n",t[jg].v); } if(opt==6) { jg=0; query_sub(g,cs); printf("%d\n",t[jg].v); } } //while(1); return 0;}