To boldly go where no one has gone before.

【封装】替罪羊树

2019-04-09 13:35:06


替罪羊树学会好久了,但是从来没有认真用$class$成功封装过。这里记录一种封装了正常$BST$操作的$class$,供以后复习使用。

实际上这是一种比较奇葩的写法,在查询前驱后继的时候比较暴力,导致常数大了一些,不过拿去跑二逼平衡树不吸氧也是能过的。暴力大法好啊

这里所谓的暴力写法 就是这个地方:

inline int Prefix(int x, int v) {
    if(!x)
        return -INF;
    if(v(x) < v) {
        if(c(x))
            return max(v(x), Prefix(r(x), v));
        else
            return max(Prefix(l(x), v), Prefix(r(x), v));
    }
    else 
        return Prefix(l(x), v);
}
inline int Suffix(int x, int v) {
    if(!x)
        return INF;
    if(v(x) > v) {
        if(c(x))
            return min(v(x), Suffix(l(x), v));
        else
            return min(Suffix(r(x), v), Suffix(l(x), v));
    }
    else 
        return Suffix(r(x), v);
}

注意第二层$if()$的$else$,是不是非常暴力!当前节点不存在就合并左右儿子的信息,因为你也不知道左右儿子到底存不存在。要想完美地解决这个判断问题非常麻烦,因此我干脆就不解决了,直接拉常数解决,反正不太可能会TLE

注意使用前需要$Init()$,以为低版本C++是不支持在$private$里头初始化的。


完整代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const double alpha = 0.67;
const int INF = 2147483647;

class ScapeGoatTree {
    #define l(x) tree[x].lson
    #define r(x) tree[x].rson
    #define v(x) tree[x].val 
    #define s(x) tree[x].size 
    #define c(x) tree[x].cnt 
    #define d(x) tree[x].del
 private: 
    int cnt;
    int cache[MAXN];
    int len;
    struct BST {
        int lson, rson;
        int val, size, cnt, del;
    } tree[MAXN];
    inline void update(int &x) {
        s(x) = s(l(x)) + s(r(x)) + c(x);
        d(x) = d(l(x)) + d(r(x)) + c(x);
        return;
    }
    inline bool isbad(int x) {
        return ((double)s(x) * alpha > d(x)) || ((double)s(x) * alpha < max(s(l(x)), s(r(x))));
    }
    inline void flatten(int x) {
        if(!x)
            return;
        flatten(l(x));
        if(c(x))
            cache[++len] = x;
        flatten(r(x));
        return;
    }
    inline void build(int &x, int l, int r) {
        if(l > r) {
            x = 0;
            return;
        }
        int mid = (l + r) >> 1;
        x = cache[mid];
        build(l(x), l, mid - 1);
        build(r(x), mid + 1, r);
        update(x);
        return;
    }
    inline void rebuild(int &x) {
        len = 0;
        flatten(x);
        build(x, 1, len);
        return;
    }
 public:
    inline void Init() {
        cnt = len = 0;
        return;
    }
    inline void Insert(int &x, int v) {
        if(!x) {
            x = ++cnt;
            v(x) = v;
            l(x) = r(x) = 0;
            c(x) = s(x) = d(x) = 1;
            return;
        }
        if(v == v(x)) {
            c(x)++;
        }
        else {
            if(v < v(x))
                Insert(l(x), v);
            else 
                Insert(r(x), v);
        }
        update(x);
        if(isbad(x))
            rebuild(x);
        return;
    }
    inline void Delete(int &x, int v) {
        if(!x)
            return;
        d(x)--;
        if(v == v(x)) {
            if(c(x))
                c(x)--;
        }
        else {
            if(v < v(x))
                Delete(l(x), v);
            else 
                Delete(r(x), v);
        }
        update(x);
        if(isbad(x))
            rebuild(x);
        return;
    }
    inline int QueryKth(int x, int k) {
        if(!k)
            return 0;
        if(d(l(x)) < k && k <= d(l(x)) + c(x))
            return v(x);
        else {
            if(k <= d(l(x)))
                return QueryKth(l(x), k);
            else 
                return QueryKth(r(x), k - d(l(x)) - c(x));
        }
    }
    inline int PreRank(int x, int v) {
        if(!x)
            return 0;
        if(v == v(x))
            return d(l(x));
        else {
            if(v < v(x))
                return PreRank(l(x), v);
            else 
                return PreRank(r(x), v) + c(x) + d(l(x));
        }
    }
    inline int QueryRank(int x, int v) {
        return PreRank(x, v) + 1;
    }
    inline int Prefix(int x, int v) {
        if(!x)
            return -INF;
        if(v(x) < v) {
            if(c(x)) {
                if(d(r(x)))
                    return max(v(x), Prefix(r(x), v));
                else
                    return v(x);
            }
            else {
                if(d(r(x)))
                    return Prefix(r(x), v);
                else
                    return Prefix(l(x), v);
            }
        }
        else 
            return Prefix(l(x), v);
    }
    inline int Suffix(int x, int v) {
        if(!x)
            return INF;
        if(v(x) > v) {
            if(c(x)) {
                if(d(l(x)))
                    return min(v(x), Suffix(l(x), v));
                else
                    return v(x);
            }
            else {
                if(d(l(x)))
                    return Suffix(l(x), v);
                else
                    return Suffix(r(x), v);
            }
        }
        else 
            return Suffix(r(x), v);
    }
    inline void Debug(int x) {
        if(!x)
            return;
        Debug(l(x));
        printf("node#%d: v=%d, l=%d, r=%d, c=%d, d=%d, s=%d\n", x, v(x), l(x), r(x), c(x), d(x), s(x));
        Debug(r(x));
        return;
    }
};

ScapeGoatTree s;

inline int read() {
    int res = 0, uz = 1;
    char ch = getchar();
    while(!isdigit(ch)) {
        if(ch == '-')
            uz = -1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        res = (res << 3) + (res << 1) + (ch ^ '0');
        ch = getchar();
    }
    return res * uz;
}

int main() {
    s.Init();
    int n = read();
    int root = 0;
    while(n--) {
        int opt = read(), x = read();
        switch(opt) {
            case 1: {
                s.Insert(root, x);
                break;
            }
            case 2: {
                s.Delete(root, x);
                break;
            }
            case 3: {
                printf("%d\n", s.QueryRank(root, x));
                break;
            }
            case 4: {
                printf("%d\n", s.QueryKth(root, x));
                break;
            }
            case 5: {
                printf("%d\n", s.Prefix(root, x));
                break;
            }
            default: {
                printf("%d\n", s.Suffix(root, x));
                break;
            }
        }
    }
    return 0;
}