这是一个还没有来得及填的坑……等我丢个带旋的treap代码在这里

可能会过几（hen）天（jiu）才写

• 带旋treap代码：（洛谷P3369【模板】普通平衡树）

#include
    
     #define grbv GetRankByVal#define gvbr GetValByRankusing namespace std;const int size=100010;struct treap{    int l,r;    int val,dat;    int cnt,size;}a[size];int tot,root,n,inf=0x7fffffff;inline int read(){    int cn=0,f=1;char c;    c=getchar();    while(!isdigit(c)){        if(c=='-')f=-1;        c=getchar();    }    while(isdigit(c)){        cn=cn*10+c-'0';        c=getchar();    }    return cn*f;}int New(int val){    a[++tot].val=val;    a[tot].dat=rand();    a[tot].cnt=a[tot].size=1;    return tot;}inline void update(int p){    a[p].size=a[a[p].l].size+a[a[p].r].size+a[p].cnt;}void build_tree(){    New(-inf),New(inf);    root=1,a[1].r=2;    update(root);}int grbv(int p,int val){//  if(p==0) return 0;    if(val==a[p].val) return a[a[p].l].size+1;    if(val
     
      =rank) return gvbr(a[p].l,rank);    if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;    return gvbr(a[p].r,rank-a[a[p].l].size-a[p].cnt);}void zig(int &p){    int q=a[p].l;    a[p].l=a[q].r,a[q].r=p,p=q;    update(a[p].r),update(p);}void zag(int &p){    int q=a[p].r;    a[p].r=a[q].l,a[q].l=p,p=q;    update(a[p].l),update(p);}void insert(int &p,int val){    if(p==0){        p=New(val);        return;    }    if(val==a[p].val){        a[p].cnt++,update(p);        return;    }    if(val
      
       0){                p=a[p].l;                while(a[p].r>0) p=a[p].r;                ans=p;            }            break;        }        if(a[p].val
       
        a[ans].val) ans=p;        p=val
        
         0){                p=a[p].r;                while(a[p].l>0) p=a[p].l;                ans=p;            }            break;        }        if(a[p].val>val&&a[p].val
         
          1){ a[p].cnt--,update(p); return; } if(a[p].l||a[p].r){ if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat) zig(p),remove(a[p].r,val); else zag(p),remove(a[p].l,val); update(p); } else p=0; return; } val