Algoogle

Algorithm for Programming Contest

永続赤黒木

基本情報


計算量  
merge
split
insert
build
add
空間

N := ノード数
M := 生成元の列の長さ

解説


0から連続する整数をkeyとする赤黒木の永続版.
merge/splitベースで書かれている(赤黒木(merge/split)).
JOI 春合宿 2012 Day4 Copy and Pasteで使ったものをを元にしている.
解説スライド

  • build: 列から木を生成する
  • add: 要素を後ろに追加する
  • get: 要素を左から順に並べた列をつくる
  • merge: 木の根同士をもってきてつなげる
  • split: k番目の要素で別れるように木を切る
  • insert: k番目に木を挿入する
  • copy: 区間に対応する部分木の根を取り出す

versionとか持たせたいなら適当にcommit関数とか作ってそのときのrootを保存していけばよさそう(適当)

コード


(prbtree.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
//const int MAX = 15000000, BOUND = 14000000;
template<class T> class prbtree {
public:
    enum COL { BLACK, RED, };
    struct node {
        T val;
        int color;
        int rnk, size;
        node *left, *right;

        node(){}
        node(T v) : val(v), color(BLACK), rnk(0), size(1) {
            left = right = NULL;
        }
        node(node *l, node *r, int c) : color(c) {
            left = l;
            right = r;
            rnk = max((l? l->rnk+(l->color==BLACK): 0),(r? r->rnk+(r->color==BLACK): 0));
            size = !l and !r? 1: !l? r->size: !r? r->size: l->size+r->size;
        }
    };

    node *root;
    //        node nodes[MAX];
    //        int called;

    prbtree() {
        root = NULL;
        // called = 0;
    }

    prbtree(T val) {
        root = new_node(val);
        // called = 0;
    }

    //        node *new_node(T v) { return &(nodes[called++] = node(v));}
    //        node *new_node(node *l, node *r, int c) { return &(nodes[called++] = node(l,r,c));}
    node *new_node(T v) { return new node(v); }
    node *new_node(node *l, node *r, int c) { return new node(l,r,c); }

    node *build(const vector<T> &vs) {
        if(!vs.size()) return NULL;
        if((int)vs.size() == 1) return new_node(vs[0]);
        int m = vs.size()/2;
        return merge(build(vector<T>(begin(vs),begin(vs)+m)), build(vector<T>(begin(vs)+m,end(vs))));
    }

    int size() { return root->size; }
    void clear() {
        // called = 0;
        root = NULL;
    }

    void print() { print(root,0,0); }
    void print(node *v, int dep, int lr) {
        if(!v) return;
        print(v->right,dep+1,1);
        for(int i = 0; i < dep; i++) cerr << "  ";
        if(!lr) cerr << "--";
        else if(lr == 1) cerr << "「";
        else cerr << "L";
        if(v->color == RED) cerr << "\x1b[31m";
        if(!v->left and !v->right) cerr << v->val << endl;
        else cerr << "nd" << endl;
        cerr << "\x1b[0m";
        print(v->left,dep+1,2);
    }

    void get(vector<T> &vs) { get(root,vs); }
    void get(node *v, vector<T> &vs) {
        if(!v->left and !v->right) vs.push_back(v->val);
        else {
            if(v->left) get(v->left,vs);
            if(v->right) get(v->right,vs);
        }
    }

    node *add(T val) {
        node *v = new_node(val);
        return root = merge(root,v);
    }
    node *merge(node *u, node *v) {
        if(!u) return v;
        if(!v) return u;
        u = merge_sub(u,v);
        if(u->color == RED) return new_node(u->left,u->right,BLACK);
        return u;
    }

    node *merge_sub(node *u, node *v) {
        if(u->rnk < v->rnk) {
            node *w = merge_sub(u,v->left);
            if(v->color == BLACK and w->color == RED and w->left->color == RED){
                if(v->right->color == BLACK)  return new_node(w->left,new_node(w->right,v->right,RED),BLACK);
                else return new_node(new_node(w->left,w->right,BLACK),new_node(v->right->left,v->right->right,BLACK),RED);
            }
            else return new_node(w,v->right,v->color);
        }
        else if(u->rnk > v->rnk) {
            node *w = merge_sub(u->right,v);
            if(u->color == BLACK and w->color == RED and w->right->color == RED){
                if(u->left->color == BLACK)  return new_node(new_node(u->left,w->left,RED),w->right,BLACK);
                else return new_node(new_node(u->left->left,u->left->right,BLACK),new_node(w->left,w->right,BLACK),RED);
            }
            else return new_node(u->left,w,u->color);
        }
        else return new_node(u,v,RED);
    }

    pair<node*,node*> split(node *v, int k) {
        if(!k) return pair<node*,node*>(NULL,v);
        if(k == v->size) return pair<node*,node*>(v,NULL);
        if(k < v->left->size) {
            auto p = split(v->left,k);
            return pair<node*,node*>(p.first,merge(p.second,v->right));
        }
        else if(k > v->left->size) {
            auto p = split(v->right,k-v->left->size);
            return pair<node*,node*>(merge(v->left,p.first),p.second);
        }
        else return pair<node*,node*>(v->left,v->right);
    }
    // copy [l,r)
    node *copy(int l, int r) { return split(split(root, l).second, r-l).first; }

    // insert leaf at k
    node *insert(int k, T val) { return insert(new_node(val), k); }

    // insert tree v at k
    node *insert(node *v, int k) {
        auto p = split(root,k);
        return root = merge(merge(p.first,v),p.second);
    }

    // copy and insert [l,r) at k
    node *copy_paste(int l, int r, int k) { return insert(copy(l,r),k); }
};

Comments