RenaMoe's Blog

念念不忘，必有回响

0%

板子 平衡树

发表于 更新于 分类于 ， Valine：

包括 Splay、WBLT、替罪羊树.。

Splay

update 2020.11.23

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
struct Splay {
    int tot, root;
    int fa[N], ch[N][2], size[N], cnt[N], val[N];
    inline void push_up(int x) {
        size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
    }
    inline int which(int x) {
        return x == ch[fa[x]][1];
    }
    inline void clear(int x) {
        fa[x] = ch[x][0] = ch[x][1] = size[x] = val[x] = cnt[x] = 0;
    }
    inline int new_node(int v = 0, int f = 0) {
        tot++;
        val[tot] = v, fa[tot] = f;
        size[tot] = cnt[tot] = 1;
        return tot;
    }
    inline void rotate(int x) {
        int f = fa[x], gf = fa[f], w = which(x), y = ch[x][w^1];
        ch[gf][which(f)] = x, ch[x][w^1] = f, ch[f][w] = y;
        fa[x] = gf, fa[f] = x, fa[y] = f;
        clear(0), push_up(f), push_up(x);
    }
    inline void splay(int x, int goal = 0) {
        while (fa[x] != goal) {
            int f = fa[x];
            if (fa[f] != goal)
                which(f) == which(x) ? rotate(f) : rotate(x);
            rotate(x);
        }
        if (!goal) root = x;
    }
    inline void insert(int k) {
        if (!root) return root = new_node(k), void();
        int x = find(k);
        if (val[x] == k) cnt[x]++, push_up(x);
        else {
            ch[x][k > val[x]] = new_node(k, x);
            x = ch[x][k > val[x]];
        }
        splay(x);
    }
    inline void erase(int k) {
        int x = find(k);
        splay(x);
        if (cnt[x] > 1) {
            cnt[x]--, push_up(x);
            return;
        }
        if (!ch[x][0] || !ch[x][1]) {
            int y = ch[x][0] | ch[x][1];
            clear(x), fa[y] = 0, root = y;
            return;
        }
        int l = pre(val[x]), r = ch[x][1];
        splay(l, x);
        clear(x), ch[l][1] = r, fa[r] = l;
        fa[l] = 0, root = l, push_up(l);
    }
    inline int find(int k) {
        int x = root, f = 0;
        while (x && val[x] != k)
            f = x, x = ch[x][k > val[x]];
        return x ? x : f;
    }
    inline int rank(int k) {
        int x = find(k), rk = rank_id(x);
        return rk + (k > val[x]) * cnt[x];
    }
    inline int rank_id(int x) {
        splay(x);
        return size[ch[x][0]] + 1;
    }
    inline int kth(int k) {
        int x = root;
        while (true) {
            if (k <= size[ch[x][0]]) x = ch[x][0];
            else if (k > size[ch[x][0]] + cnt[x]) {
                k -= size[ch[x][0]] + cnt[x];
                x = ch[x][1];
            }
            else return x;
        }
    }
    inline int pre(int k) {
        return kth(rank(k) - 1);
    }
    inline int nxt(int k) {
        return kth(rank(k + 1));
    }
} tr;

替罪羊树

update on 2020.1.29

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
const double Alpha = 0.75;

struct SGT {
    int tot, root, cnt_tmp;
    int val[N], cnt[N], sz[N], rsz[N], ls[N], rs[N], tmp[N];
    // sz：节点数量
    // rsz：真实数量
    queue<int> trash;
    
    inline int new_node() {
        if (trash.empty()) return ++tot;
        int x = trash.front();
        trash.pop();
        cnt[x] = val[x] = ls[x] = rs[x] = sz[x] = rsz[x] = 0;
        return x;
    }
    inline void push_up(int x) {
        sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
        rsz[x] = rsz[ls[x]] + rsz[rs[x]] + cnt[x];
    }
    void pia(int x) {
        if (!x) return;
        pia(ls[x]);
        if (cnt[x]) tmp[++cnt_tmp] = x;
        else trash.push(x);
        pia(rs[x]);
    }
    int rebuild(int l, int r) {
        if (l > r) return 0;
        int mid = (l + r) >> 1, x = tmp[mid];
        ls[x] = rebuild(l, mid - 1), rs[x] = rebuild(mid + 1, r);
        push_up(x); // bug
        return x;
    }
    inline void maintain(int &x) {
        if (cnt[x] && (double)max(sz[ls[x]], sz[rs[x]]) >= Alpha * sz[x]) {
            cnt_tmp = 0, pia(x);
            x = rebuild(1, cnt_tmp);
        }
    }
    void insert(int &x, int k) {
        if (!x) {
            x = new_node();
            val[x] = k, cnt[x] = sz[x] = rsz[x] = 1;
            return;
        }
        if (val[x] == k) {
            ++cnt[x], push_up(x); // bug
            return;
        }
        insert(k > val[x] ? rs[x] : ls[x], k);
        push_up(x), maintain(x);
    }
    void erase(int &x, int k) {
        if (val[x] == k) {
            --cnt[x], push_up(x); // bug
            return;
        }
        erase(k > val[x] ? rs[x] : ls[x], k);
        push_up(x), maintain(x);
    }
    int rank(int x, int k) {
        if (!x) return 1;
        if (cnt[x] && val[x] == k) return rsz[ls[x]] + 1; // bug
        if (k > val[x]) return rsz[ls[x]] + cnt[x] + rank(rs[x], k);
        return rank(ls[x], k);
    }
    int kth(int x, int k) {
        if (k <= rsz[ls[x]]) return kth(ls[x], k);
        if (k > rsz[ls[x]] + cnt[x]) return kth(rs[x], k - rsz[ls[x]] - cnt[x]);
        return x;
    }
    inline int pre(int k) {
        return kth(root, rank(root, k) - 1);
    }
    inline int nxt(int k) {
        return kth(root, rank(root, k + 1));
    }
} T;

WBLT

update on 2020.2.19

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
struct WBLT {
    int cnt, root;
    int val[M], sz[M], ls[M], rs[M];
    
    WBLT() {
    	new_node(root, 1e9);
    }
    inline bool is_leaf(int x) {
        return !(ls[x] || rs[x]);
    }
    inline void push_up(int x) {
        if (is_leaf(x)) return;
        val[x] = max(val[ls[x]], val[rs[x]]);
        sz[x] = sz[ls[x]] + sz[rs[x]];
    }
    inline void new_node(int &x, int k) {
        x = ++cnt;
        val[x] = k, sz[x] = 1;
    }
    inline void rotate(int x, bool opt) {
        if (!opt) {
            int rson = rs[x];
            rs[x] = ls[x], ls[x] = ls[rs[x]];
            ls[rs[x]] = rs[rs[x]], rs[rs[x]] = rson;
        }
        else {
            int lson = ls[x];
            ls[x] = rs[x], rs[x] = rs[ls[x]];
            rs[ls[x]] = ls[ls[x]], ls[ls[x]] = lson;
        }
        push_up(ls[x]), push_up(rs[x]);
    }
    inline void maintain(int x) {
        if (is_leaf(x)) return;
        if (sz[ls[x]] >= sz[rs[x]] * 4) rotate(x, 0);
        if (sz[rs[x]] >= sz[ls[x]] * 4) rotate(x, 1);
    }
    void insert(int x, int k) {
        if (is_leaf(x)) {
            new_node(ls[x], min(val[x], k));
            new_node(rs[x], max(val[x], k));
            push_up(x);
            return;
        }
        if (k <= val[ls[x]]) insert(ls[x], k);
        else insert(rs[x], k);
        push_up(x), maintain(x);
    }
    void erase(int x, int fa, int k) {
        if (is_leaf(x)) {
            if (!fa) return;
            int son = ls[fa] == x ? rs[fa] : ls[fa];
            val[fa] = val[son], sz[fa] = sz[son];
            ls[fa] = ls[son], rs[fa] = rs[son];
            return;
        }
        if (k <= val[ls[x]]) erase(ls[x], x, k);
        else erase(rs[x], x, k);
        push_up(x), maintain(x);
    }
    int rank(int x, int k) {
        if (is_leaf(x))
            return 1 + (k > val[x]);
        if (k <= val[ls[x]]) return rank(ls[x], k);
        else return sz[ls[x]] + rank(rs[x], k);
    }
    int k_th(int x, int k) {
        if (is_leaf(x)) return x;
        if (k <= sz[ls[x]]) return k_th(ls[x], k);
        else return k_th(rs[x], k - sz[ls[x]]);
    }
    int next(int rt, int k, bool opt) {
        int rk = rank(rt, k), rk2 = rank(rt, k+1);
        if (!opt && rk == 1) return -INF;
        if (opt && rk2 > sz[rt]) return INF;
        return val[k_th(rt, opt ? rk2 : rk - 1)];
    }
};