非旋转 treap

其实之前学过一次非旋转 treap，但是全忘光了，今天复习一下. 

洛谷 P3369 【模板】普通平衡树  

code: 

#include <bits/stdc++.h>
#define N  100006
#define lson t[x].ls
#define rson t[x].rs
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int root;
namespace treap
{
    int tot;
    struct node
    {
        int val,size,ls,rs,ran;
    }t[N];
    inline void newnode(int &x,int val)
    {
        ++tot;
        t[tot].size=1;
        t[tot].val=val;
        t[tot].ran=rand();
        t[tot].ls=t[tot].rs=0;
        x=tot;
    }
    inline void pushup(int x)
    {
        t[x].size=t[lson].size+t[rson].size+1;
    }
    void split(int x,int &l,int &r,int val)
    {
        if(!x) { l=r=0; return; }
        if(t[x].val<=val)  l=x, split(t[x].rs,t[l].rs,r,val);
        else   r=x, split(t[x].ls,l,t[r].ls,val);
        pushup(x);
    }
    void merge(int &x,int a,int b)
    {
        if(!a||!b)  { x=a+b;   return; }
        if(t[a].ran<t[b].ran)  x=a, merge(t[x].rs,t[a].rs,b);
        else  x=b, merge(t[x].ls,a,t[b].ls);
        pushup(x);
    }
    void insert(int val)
    {
        int x=0,y=0,z=0;
        newnode(z,val);
        split(root,x,y,val-1);
        merge(x,x,z);
        merge(root,x,y);
    }
    void del(int val)
    {
        int x=0,y=0,z=0;
        split(root,x,y,val);
        split(x,x,z,val-1);
        merge(z,t[z].ls,t[z].rs);
        merge(x,x,z);
        merge(root,x,y);
    }
    void ask_rank(int v)
    {
        int x=0,y=0;
        split(root,x,y,v-1);
        printf("%d\n",t[x].size+1);
        merge(root,x,y);
    }
    void ask_num(int x,int kth)
    {
        while(t[lson].size+1!=kth)
        {
            if(t[lson].size>=kth)  x=lson;
            else kth-=(t[lson].size+1),x=rson;
        }
        printf("%d\n",t[x].val);
    }
    void ask_front(int v)
    {
        int x=0,y=0;
        split(root,x,y,v-1);
        ask_num(x,t[x].size);
        merge(root,x,y);
    }
    void ask_back(int v)
    {
        int x=0,y=0;
        split(root,x,y,v),ask_num(y,1), merge(root,x,y);
    }
};
int main()
{
    // setIO("input");
    int i,j,n;
    srand(16);
    scanf("%d",&n);
    for(i=1;i<=n;++i)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1) treap::insert(x);
        if(opt==2) treap::del(x);
        if(opt==3) treap::ask_rank(x);
        if(opt==4) treap::ask_num(root,x);
        if(opt==5) treap::ask_front(x);
        if(opt==6) treap::ask_back(x);
    }
    return 0;
}