模版题目

普通平衡树：
luogu3369
luogu6136
splay：
luogu3391

Treap

treap实现的平衡树，需要定义maxn
luogu6136 7.27s（无内存回收） 9.24s（内存回收）

struct node{
    int s,v,r;
    node*ch[2];
    inline void maintain(){
        s=ch[0]->s+ch[1]->s+1;
    }
};
struct treap{
    node pool[maxn],*root,*null;
    queue<node*>Q;
    treap(){
        init();
    }
    node*newnode(int x){
        node*pt=Q.front();
        Q.pop();
        pt->s=1;pt->ch[0]=pt->ch[1]=null;
        pt->r=rand()*rand();
        pt->v=x;
        return pt++;
    }
    void rot(node*&o,int d){
        node*t=o->ch[d^1];
        o->ch[d^1]=t->ch[d];t->ch[d]=o;
        o->maintain();t->maintain();
        o=t;
    }
    void insert(node*&o,int x){
        if(o==null) o=newnode(x);
        else{
            if(x<o->v){
                insert(o->ch[0],x);
                if(o->ch[0]->r>o->r) rot(o,1);
            }else{
                insert(o->ch[1],x);
                   if(o->ch[1]->r>o->r) rot(o,0);
              }
         }
           o->maintain();
    }
    void del(node*&o,int x){
        if(o->v==x){
            if(o->ch[0]!=null&&o->ch[1]!=null){
                if(o->ch[0]->r>o->ch[1]->r){
                    rot(o,1);del(o->ch[1],x);
                }else{
                    rot(o,0);del(o->ch[0],x);
                }
            }else if(o->ch[0]!=null){
                Q.push(o);
                o=o->ch[0];
            }else{
                Q.push(o);
                o=o->ch[1];
            }
        }else{
            if(x<o->v) del(o->ch[0],x);
            else del(o->ch[1],x);
        }
        if(o!=null) o->maintain();
    } 
    int rank(node*o,int x){
        if(o==null) return 1;
        if(x==o->v) return min(rank(o->ch[0],x),o->ch[0]->s+1);
        if(x<o->v) return rank(o->ch[0],x);
        return rank(o->ch[1],x)+o->ch[0]->s+1;
    }
    int num(node*o,int x){
        if(x==o->ch[0]->s+1) return o->v;
        if(x<=o->ch[0]->s) return num(o->ch[0],x);
        return num(o->ch[1],x-o->ch[0]->s-1);
    }
    int pre(node*o,int x){
        if(o==null) return -inf;
        return x<=o->v?pre(o->ch[0],x):max(o->v,pre(o->ch[1],x));
    }
    int suc(node*o,int x){
           if(o==null) return inf;
        return x>=o->v?suc(o->ch[1],x):min(o->v,suc(o->ch[0],x));
    }
    void init(){
        srand(time(NULL));
        for(int i=0;i<maxn;i++)
            Q.push(pool+i);
        null=newnode(0);
        null->s=null->r=0;
        root=null;
    }
};