2018-team4-modules-Treap

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
struct Node{
    Node *ch[2];
    int siz,w,fix;
    void update(){
        siz = ch[0]->siz + ch[1]->siz + 1;
    }
};
struct Treap{
    Node mem[maxn];
    Node *tail,*root,*null;
    Node *bc[maxn];int top;
    Treap(){
        tail = mem;null = tail++;
        null->ch[0] = null->ch[1] = null;
        null->siz = null->w = 0;null->fix = 0x7f7f7f7f;
        root = null;
    }
    Node* newNode(int key){
        Node *p = top ? bc[top--] : tail++;
        p->ch[0] = p->ch[1] = null;
        p->siz = 1;p->w = key;p->fix = rand();
        return p;
    }
    void del(Node* &p){
        bc[++top] = p;
        p = null;
    }
    void turn(Node* &p,int k){
        Node *y = p->ch[k^1];
        p->ch[k^1] = y->ch[k];
        y->ch[k] = p;
        y->siz = p->siz;
        p->update();p = y;
    }
    int val;
    void Insert(Node* &p){
        if(p == null){
            p = newNode(val);
            return;
        }
        p->siz++;
        Insert(p->ch[val >= p->w]);
        if(p->ch[val >= p->w]->fix < p->fix)
            turn(p,val < p->w);
    }
    void Insert(int x){
        val = x;
        Insert(root);
    }
    void Erase(Node* &p){
        if(val == p->w){
            if(p->ch[0] != null && p->ch[1] != null){
                int k = p->ch[0]->fix >= p->ch[1]->fix;
                turn(p,k);
                Erase(p->ch[k]);
            }else{
                Node *y = p->ch[0] == null ? p->ch[1] : p->ch[0];
                del(p);p = y;
            }
        }else Erase(p->ch[val >= p->w]);
        if(p != null) p->update();
    }
    void Erase(int x){
        val = x;
        Erase(root);
    }
    int Kth(int k){
        Node *nw = root;
        while(nw != null){
            if(nw->ch[0]->siz + 1 == k) return nw->w;
            if(nw->ch[0]->siz + 1 >  k) nw = nw->ch[0];
            else k -= nw->ch[0]->siz + 1,nw = nw->ch[1];
        }
    }
    int rank(int x){
        int ret = 1;
        Node *nw = root;
        while(nw != null){
            if(x <= nw->w) nw = nw->ch[0];
            else{
                ret += nw->ch[0]->siz + 1;
                nw = nw->ch[1];
            }
        }return ret;
    }
};// srand()
}}}

struct Node{
    Node *ch[2];
    int siz,w,fix;
    void update(){
        siz = ch[0]->siz + ch[1]->siz + 1;
    }
};
struct Treap{
    Node mem[maxn];
    Node *tail,*root,*null;
    Node *bc[maxn];int top;
    Treap(){
        tail = mem;null = tail++;
        null->ch[0] = null->ch[1] = null;
        null->siz = null->w = 0;null->fix = 0x7f7f7f7f;
        root = null;
    }
    Node* newNode(int key){
        Node *p = top ? bc[top--] : tail++;
        p->ch[0] = p->ch[1] = null;
        p->siz = 1;p->w = key;p->fix = rand();
        return p;
    }
    void del(Node* &p){
        bc[++top] = p;
        p = null;
    }
    void turn(Node* &p,int k){
        Node *y = p->ch[k^1];
        p->ch[k^1] = y->ch[k];
        y->ch[k] = p;
        y->siz = p->siz;
        p->update();p = y;
    }
    int val;
    void Insert(Node* &p){
        if(p == null){
            p = newNode(val);
            return;
        }
        p->siz++;
        Insert(p->ch[val >= p->w]);
        if(p->ch[val >= p->w]->fix < p->fix)
            turn(p,val < p->w);
    }
    void Insert(int x){
        val = x;
        Insert(root);
    }
    void Erase(Node* &p){
        if(val == p->w){
            if(p->ch[0] != null && p->ch[1] != null){
                int k = p->ch[0]->fix >= p->ch[1]->fix;
                turn(p,k);
                Erase(p->ch[k]);
            }else{
                Node *y = p->ch[0] == null ? p->ch[1] : p->ch[0];
                del(p);p = y;
            }
        }else Erase(p->ch[val >= p->w]);
        if(p != null) p->update();
    }
    void Erase(int x){
        val = x;
        Erase(root);
    }
    int Kth(int k){
        Node *nw = root;
        while(nw != null){
            if(nw->ch[0]->siz + 1 == k) return nw->w;
            if(nw->ch[0]->siz + 1 >  k) nw = nw->ch[0];
            else k -= nw->ch[0]->siz + 1,nw = nw->ch[1];
        }
    }
    int rank(int x){
        int ret = 1;
        Node *nw = root;
        while(nw != null){
            if(x <= nw->w) nw = nw->ch[0];
            else{
                ret += nw->ch[0]->siz + 1;
                nw = nw->ch[1];
            }
        }return ret;
    }
};// srand()