题表：普通平衡树

           宠物收养所

           营业额统计

           文艺平衡树

treap满足二叉树的性质，当前节点的val>左儿子的val，<右儿子的val

为了保持平衡，每个节点有rnd值，满足堆的性质

数组实现

#include
    
     #include
     
      #include
      
       #include
       
        #define N 100005using namespace std;struct treap{    int l,r,v,size,rnd,w;  }t[N];int n,size,root,ans;void update(int k){    t[k].size=t[t[k].l].size+t[t[k].r].size+t[k].w; }void rturn(int &k){     int x=t[k].l;     t[k].l=t[x].r;t[x].r=k;     t[x].size=t[k].size;update(k);k=x;     return ;}void lturn(int &k){     int x=t[k].r;     t[k].r=t[x].l;t[x].l=k;     t[x].size=t[k].size;update(k);k=x;     return ;}void insert(int &k,int x){    if(k==0)    {        size++;k=size;        t[k].size=t[k].w=1;t[k].rnd=rand();t[k].v=x;        return ;        }    t[k].size++;    if(t[k].v==x) t[k].w++;    else      if(t[k].v>x)      {           insert(t[k].l,x);           if(t[t[k].l].rnd
        
         1)        {            t[k].size--;t[k].w--;return ;                }                  if(t[k].l*t[k].r==0) k=t[k].l+t[k].r;        else          if(t[t[k].l].rnd
         
          x) {t[k].size--; del(t[k].l,x); } else {t[k].size--; del(t[k].r,x); }}int rank(int k,int x)//查找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+rank(t[k].r,x); else return rank(t[k].l,x);}int rank2(int k,int x)//查找排名为x的数{ if(k==0) return 0; if(x<=t[t[k].l].size) { return rank2(t[k].l,x); } else if(x>t[t[k].l].size+t[k].w) return rank2(t[k].r,x-t[t[k].l].size-t[k].w); else return t[k].v;}void pre(int k,int x)//查找x的前驱{ if(k==0) return ; if(t[k].v
         
        
       
      
     
    

{

if(k==0) return ;     if(t[k].v>x)     {         ans=k;sub(t[k].l,x);             }     else sub(t[k].r,x);}int main(){     freopen("phs.in","r",stdin);     freopen("phs.out","w",stdout);     scanf("%d",&n);     int opt,x;     for(int i=1;i<=n;i++)     {         scanf("%d%d",&opt,&x);         if(opt==1)  insert(root,x);         if(opt==2)  del(root,x);         if(opt==3)  printf("%d\n",rank(root,x));         if(opt==4)  printf("%d\n",rank2(root,x));         if(opt==5)  { ans=0; pre(root,x); printf("%d\n",t[ans].v);}         if(opt==6)  { ans=0; sub(root,x); printf("%d\n",t[ans].v);}     }     //while(1);     return 0;     }