2013-team4/code/treap-Persistent

从 Trac 迁移的文章

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

原文章内容如下：

{{{
const int N = 10010100;
struct Node{
    Node *ch[2];
    int rank, size;
    char c;
    void update(){
        size = ch[0]->size + ch[1]->size + 1;
    }
}pool[N], *null;
int poolCnt;
typedef pair<Node*, Node*> PNN;

Node* newNode(char c){
    Node *p = &pool[poolCnt++];
    p->ch[0] = p->ch[1] = null;
    p->rank = rand();
    p->size = 1;
    p->c = c;
    return p;
}
Node* newNode(Node *a){
    Node *p = &pool[poolCnt++];
    *p = *a;
    return p;
}
// 首先调用 init()
void init(){
    poolCnt = 0;
    null = newNode('$');
    null->size = 0;
}
/* 概率合并可以处理大量 rank 相同的情况, Node 中不需要记录 rank
 * double t = double(a->size) / double(a->size + b->size);
 * if(rand() < RAND_MAX * t) {...}
 * else {...}
 */
// 普通合并, 返回树根
Node* merge(Node *a, Node *b){
    if(a == null) return b;
    if(b == null) return a;
    Node *p;
    if(a->rank < b->rank){
        p = newNode(a);
        p->ch[1] = merge(p->ch[1], b);
    }
    else{
        p = newNode(b);
        p->ch[0] = merge(a, p->ch[0]);
    }
    p->update();
    return p;
}
// 将 [1, n] 划分为 [1, k] 和 [k+1, n]
PNN split(Node *a, int k){
    if(k == 0) return PNN(null, a);
    if(k == a->size) return PNN(a, null);
    Node *p = newNode(a);
    int lsize = p->ch[0]->size;
    if(k <= lsize){
        PNN t = split(p->ch[0], k);
        p->ch[0] = t.second;
        p->update();
        return PNN(t.first, p);
    }
    else{
        PNN t = split(p->ch[1], k - lsize - 1);
        p->ch[1] = t.first;
        p->update();
        return PNN(p, t.second);
    }
}
// 在第 k 个元素之后进行插入
Node* insert(Node *root, int k, Node *x){
    PNN t = split(root, k);
    return merge(merge(t.first, x), t.second);
}
// 删除 [l, r] 区间
Node* erase(Node *root, int l, int r){
    PNN t = split(root, r);
    Node *a = split(t.first, l - 1).first, *b = t.second;
    return merge(a, b);
}
}}}

const int N = 10010100;
struct Node{
    Node *ch[2];
    int rank, size;
    char c;
    void update(){
        size = ch[0]->size + ch[1]->size + 1;
    }
}pool[N], *null;
int poolCnt;
typedef pair<Node*, Node*> PNN;
Node* newNode(char c){
    Node *p = &pool[poolCnt++];
    p->ch[0] = p->ch[1] = null;
    p->rank = rand();
    p->size = 1;
    p->c = c;
    return p;
}
Node* newNode(Node *a){
    Node *p = &pool[poolCnt++];
    *p = *a;
    return p;
}
// 首先调用 init()
void init(){
    poolCnt = 0;
    null = newNode('$');
    null->size = 0;
}
/* 概率合并可以处理大量 rank 相同的情况, Node 中不需要记录 rank
 * double t = double(a->size) / double(a->size + b->size);
 * if(rand() < RAND_MAX * t) {...}
 * else {...}
 */
// 普通合并, 返回树根
Node* merge(Node *a, Node *b){
    if(a == null) return b;
    if(b == null) return a;
    Node *p;
    if(a->rank < b->rank){
        p = newNode(a);
        p->ch[1] = merge(p->ch[1], b);
    }
    else{
        p = newNode(b);
        p->ch[0] = merge(a, p->ch[0]);
    }
    p->update();
    return p;
}
// 将 [1, n] 划分为 [1, k] 和 [k+1, n]
PNN split(Node *a, int k){
    if(k == 0) return PNN(null, a);
    if(k == a->size) return PNN(a, null);
    Node *p = newNode(a);
    int lsize = p->ch[0]->size;
    if(k <= lsize){
        PNN t = split(p->ch[0], k);
        p->ch[0] = t.second;
        p->update();
        return PNN(t.first, p);
    }
    else{
        PNN t = split(p->ch[1], k - lsize - 1);
        p->ch[1] = t.first;
        p->update();
        return PNN(p, t.second);
    }
}
// 在第 k 个元素之后进行插入
Node* insert(Node *root, int k, Node *x){
    PNN t = split(root, k);
    return merge(merge(t.first, x), t.second);
}
// 删除 [l, r] 区间
Node* erase(Node *root, int l, int r){
    PNN t = split(root, r);
    Node *a = split(t.first, l - 1).first, *b = t.second;
    return merge(a, b);
}