BZOJ3224 - Tyvj 1728 普通平衡树

2016/11/26

学习了一种高级数据结构 ———— 替罪羊树。

总结下来就是对满足平衡条件 的子树进行暴力重构。

然后删除是惰性的,直接在节点上打标记,然后重构的时候再一并删掉。

题目

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
1. 插入x数
2. 删除x数(若有多个相同的数,因只删除一个)
3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x,且最大的数)
6. 求x的后继(后继定义为大于x,且最小的数)

代码

  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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

namespace sgoat_tree {
    const int PSIZ = 100000 + 100;
    const float alpha = 0.75;
    struct tnod {
        tnod* ch[2];
        int key, size, cover;
        bool exist;
        void push_up() {
            size = ch[0]->size + ch[1]->size + exist;
            cover = ch[0]->cover + ch[1]->cover + 1;
        }
        bool is_bad() {
            return (ch[0]->cover > cover * alpha + 5) ||
                (ch[1]->cover > cover * alpha + 5);
        }
    } POOL[PSIZ]; int ppos = 1;
    tnod *nul = &POOL[0];
    tnod *bc[PSIZ]; int bpos;

    struct sshot { sshot() { nul->ch[0] = nul->ch[1] = nul; } } ____;

    tnod* mkTnod(int key) {
        tnod *p = bpos ? bc[--bpos] : &POOL[ppos++];
        p->ch[0] = p->ch[1] = nul; p->exist = 1;
        p->size = p->cover = 1;
        p->key = key;
        return p;
    }

    void reTnod(tnod* p) {
        p->exist = 0;
        bc[bpos++] = p;
    }

    struct stree {
        tnod *root;
    public:
        tnod** insert(int val, tnod* &cur) {
            if(cur == nul) {
                cur = mkTnod(val); return &nul;
            } else {
                ++cur->size; ++cur->cover;
                tnod **res = insert(val, cur->ch[val >= cur->key]);
                if(cur->is_bad()) res = &cur;
                return res;
            }
        }

        void travel(tnod* cur, vector<tnod *> &v) {
            if(cur == nul) return;
            travel(cur->ch[0], v);
            if(cur->exist && cur != nul) v.push_back(cur);
            else reTnod(cur);
            travel(cur->ch[1], v);
        }

        tnod* divide(vector<tnod *> v, int L, int R) {
            if(L >= R) return nul;
            int Mid = (L + R) >> 1;
            tnod* p = v[Mid];
            p->ch[0] = divide(v, L, Mid);
            p->ch[1] = divide(v, Mid+1, R);
            p->push_up();
            return p;
        }

        void rebuild(tnod* &cur) {
            static vector<tnod *> v; v.clear();
            travel(cur, v); cur = divide(v, 0, v.size());
        }

        void erase(tnod *cur, int id) {
            --cur->size;
            int offset = cur->ch[0]->size + cur->exist;
            if(cur->exist && id == offset) {
                cur->exist = false;
                return;
            } else {
                if(id <= offset) erase(cur->ch[0], id);
                else erase(cur->ch[1], id - offset);
            }
        }

    public:
        void insert(int val) {
            tnod **p = insert(val, root);
            if(*p != nul) rebuild(*p);
        }

        int rank(int val) {
            tnod* cur = root;
            int ans = 1;
            while(cur != nul) {
                if(cur->key >= val) cur = cur->ch[0];
                else {
                    ans += cur->ch[0]->size + cur->exist;
                    cur = cur->ch[1];
                }
            }
            return ans;
        }

        int kth(int k) {
            tnod* cur = root;
            while(cur != nul) {
                if(cur->ch[0]->size + 1 == k && cur->exist) return cur->key;
                else if(cur->ch[0]->size >= k) cur = cur->ch[0];
                else { k -= cur->ch[0]->size + cur->exist; cur = cur->ch[1]; }
            }
            return INT_MIN;
        }

        void erase(int k) {
            erase_kth(rank(k));
        }

        void erase_kth(int k) {
            erase(root, k);
            if(root->size < alpha * root->cover) rebuild(root);
        }

        stree() {
            root = nul;
        }
    };
};

sgoat_tree::stree T;
int N, K, M;

int main() {
    cin >> N;
    while(N--) {
        cin >> K >> M;
        switch(K) {
        case 1:
            T.insert(M); break;
        case 2:
            T.erase(M); break;
        case 3:
            cout << T.rank(M) << endl; break;
        case 4:
            cout << T.kth(M) << endl; break;
        case 5:
            cout << T.kth(T.rank(M)-1) << endl; break;
        case 6:
            cout <<  T.kth(T.rank(M+1)) << endl; break;
        }
    }
}