2013-team4/code/treap

从 Trac 迁移的文章

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

原文章内容如下：

{{{
Treap 不释放内存，可以有重复数据
DATA 为数据类型
}}}
{{{
创建
Treap tree;
清空
tree.clear();
插入
tree.insert(x);
删除
tree.erase(x);
第 k 小元素，k 从 0 开始到 size - 1
tree[k];
计数
tree.count(x);
上下界，返回 int 下标
tree.lower_bound();
tree.upper_bound();
}}}
{{{
typedef int DATA;
struct Node{
    Node *ch[2];
    int rank, size, cnt;
    DATA v;
    Node(DATA val){
        ch[0] = ch[1] = NULL;
        rank = rand();
        size = 1;
        cnt = 1;
        v = val;    
    }
    int cmp(DATA x) const{
        if(x == v) return -1;
        return x < v ? 0 : 1;
    }
    void update(){
        size = cnt;
        if(ch[0] != NULL) size += ch[0]->size;
        if(ch[1] != NULL) size += ch[1]->size;
    }
};
struct Treap{
    Node *rt;    
    Treap(){
        clear();
    }
    void clear(){
        rt = NULL;
    }
    void rotate(Node *&o, int d){
        Node *k = o->ch[d ^ 1];
        o->ch[d ^ 1] = k->ch[d];
        k->ch[d] = o;
        o->update(); 
        k->update();
        o = k;
    }
    void insert(Node *&o, DATA x){
        if(o == NULL) o = new Node(x);
        else{
            int d = o->cmp(x);
            if(d == -1) o->cnt++;
            else{
                insert(o->ch[d], x);
                if(o->rank < o->ch[d]->rank) rotate(o, d ^ 1);
            }
        }
        o->update();
    }
    void insert(DATA x){
        insert(rt, x);
    }
    void erase(Node *&o, DATA x){
        if(o == NULL) return;
        int d = o->cmp(x);
        if(d == -1){
            if(o->cnt > 1) o->cnt--;
            else{
                if(o->ch[0] == NULL) o = o->ch[1];
                else if(o->ch[1] == NULL) o = o->ch[0];
                else{
                    int d2 = (o->ch[0]->rank > o->ch[1]->rank ? 1 : 0);
                    rotate(o, d2);
                    erase(o->ch[d2], x);
                }
            }
        }
        else erase(o->ch[d], x);
        if(o != NULL) o->update();
    }
    void erase(DATA x){
        erase(rt, x);
    }
    int count(DATA x){
        for(Node *o = rt; true; ){
            if(o == NULL) return 0;
            int d = o->cmp(x);
            if(d == -1) return o->cnt;
            o = o->ch[d];
        }
    }
    int lower_bound(DATA x){
        int ret = 0, d;
        for(Node *o = rt; true; o = o->ch[d]){
            if(o == NULL) return ret;
            d = o->cmp(x);
            if(d != 0 && o->ch[0] != NULL) ret += o->ch[0]->size;
            if(d == -1) return ret;
            if(d == 1) ret += o->cnt;
        }
    }
    int upper_bound(DATA x){
        int ret = 0, d;
        for(Node *o = rt; true; o = o->ch[d]){
            if(o == NULL) return ret;
            d = o->cmp(x);
            if(d != 0 && o->ch[0] != NULL) ret += o->ch[0]->size;
            if(d == -1) return ret + o->cnt;
            if(d == 1) ret += o->cnt;
        }
    }
    DATA operator[](int k) const{
        if(k >= rt->size || k < 0) abort();
        for(Node *o = rt; true; ){
            int sl = (o->ch[0] == NULL ? 0 : o->ch[0]->size);
            if(k < sl) o = o->ch[0];
            else{
                k -= sl;
                if(k < o->cnt) return o->v;
                k -= o->cnt;
                o = o->ch[1];
            }
        }
    }
    int size() const{
        return rt->size;
    }
};
}}}

Treap 不释放内存，可以有重复数据
DATA 为数据类型

创建
Treap tree;
清空
tree.clear();
插入
tree.insert(x);
删除
tree.erase(x);
第 k 小元素，k 从 0 开始到 size - 1
tree[k];
计数
tree.count(x);
上下界，返回 int 下标
tree.lower_bound();
tree.upper_bound();

typedef int DATA;
struct Node{
    Node *ch[2];
    int rank, size, cnt;
    DATA v;
    Node(DATA val){
        ch[0] = ch[1] = NULL;
        rank = rand();
        size = 1;
        cnt = 1;
        v = val;    
    }
    int cmp(DATA x) const{
        if(x == v) return -1;
        return x < v ? 0 : 1;
    }
    void update(){
        size = cnt;
        if(ch[0] != NULL) size += ch[0]->size;
        if(ch[1] != NULL) size += ch[1]->size;
    }
};
struct Treap{
    Node *rt;    
    Treap(){
        clear();
    }
    void clear(){
        rt = NULL;
    }
    void rotate(Node *&o, int d){
        Node *k = o->ch[d ^ 1];
        o->ch[d ^ 1] = k->ch[d];
        k->ch[d] = o;
        o->update(); 
        k->update();
        o = k;
    }
    void insert(Node *&o, DATA x){
        if(o == NULL) o = new Node(x);
        else{
            int d = o->cmp(x);
            if(d == -1) o->cnt++;
            else{
                insert(o->ch[d], x);
                if(o->rank < o->ch[d]->rank) rotate(o, d ^ 1);
            }
        }
        o->update();
    }
    void insert(DATA x){
        insert(rt, x);
    }
    void erase(Node *&o, DATA x){
        if(o == NULL) return;
        int d = o->cmp(x);
        if(d == -1){
            if(o->cnt > 1) o->cnt--;
            else{
                if(o->ch[0] == NULL) o = o->ch[1];
                else if(o->ch[1] == NULL) o = o->ch[0];
                else{
                    int d2 = (o->ch[0]->rank > o->ch[1]->rank ? 1 : 0);
                    rotate(o, d2);
                    erase(o->ch[d2], x);
                }
            }
        }
        else erase(o->ch[d], x);
        if(o != NULL) o->update();
    }
    void erase(DATA x){
        erase(rt, x);
    }
    int count(DATA x){
        for(Node *o = rt; true; ){
            if(o == NULL) return 0;
            int d = o->cmp(x);
            if(d == -1) return o->cnt;
            o = o->ch[d];
        }
    }
    int lower_bound(DATA x){
        int ret = 0, d;
        for(Node *o = rt; true; o = o->ch[d]){
            if(o == NULL) return ret;
            d = o->cmp(x);
            if(d != 0 && o->ch[0] != NULL) ret += o->ch[0]->size;
            if(d == -1) return ret;
            if(d == 1) ret += o->cnt;
        }
    }
    int upper_bound(DATA x){
        int ret = 0, d;
        for(Node *o = rt; true; o = o->ch[d]){
            if(o == NULL) return ret;
            d = o->cmp(x);
            if(d != 0 && o->ch[0] != NULL) ret += o->ch[0]->size;
            if(d == -1) return ret + o->cnt;
            if(d == 1) ret += o->cnt;
        }
    }
    DATA operator[](int k) const{
        if(k >= rt->size || k < 0) abort();
        for(Node *o = rt; true; ){
            int sl = (o->ch[0] == NULL ? 0 : o->ch[0]->size);
            if(k < sl) o = o->ch[0];
            else{
                k -= sl;
                if(k < o->cnt) return o->v;
                k -= o->cnt;
                o = o->ch[1];
            }
        }
    }
    int size() const{
        return rt->size;
    }
};