这么好的一道平衡树题,怎么没人写替罪羊啊,明明是最好写的平衡树

本题第一篇替罪羊树题解

思路挺好想,用$n$个平衡树和并查集,维护每个联通块内各个岛屿的优先级。注意二叉排序树中节点的优先级。

合并时,直接把节点少的平衡树里面每个节点暴力塞到节点多的平衡树中,均摊复杂度是对的。

代码

替罪羊树+启发式合并

// luogu-judger-enable-o2
#include <iostream>
#include <utility>
#include <vector>

using namespace std;
typedef long long LL;
typedef pair<int, int> poi;

const float Alpha = 0.7;
const int MAXN = 1e5 + 5;

int n, m;

class SGTree{
private :
    struct Node{
        poi val;
        int cnt;
        int siz, cov;
        Node *ch[2];

        Node(poi val) : val(val) {
            cnt = true;
            siz = 1;
            cov = 1;
            ch[0] = NULL;
            ch[1] = NULL;
        }

        void Update() {
            siz = cnt + (ch[0] ? ch[0]->siz : 0) + (ch[1] ? ch[1]->siz : 0);
            cov = 1 + (ch[0] ? ch[0]->cov : 0) + (ch[1] ? ch[1]->cov : 0);
        }

        bool Bad() {
            int ls = (ch[0] ? ch[0]->cov : 0), rs = (ch[1] ? ch[1]->cov : 0);
            return (float)ls > (float)cov * Alpha || (float)rs > (float)cov * Alpha;
        }
    };

    Node *rt;
    vector<Node*> vec;

    void Dfs(Node *now) {
        if (!now) return;
        Dfs(now->ch[0]);
        if (now->cnt) vec.push_back(now);
        Dfs(now->ch[1]);
        now->ch[0] = now->ch[1] = NULL;
        now->Update();
    }

    void Rebuild(Node *&now, int l, int r) {
        if (l > r) return;
        int mid = l + r >> 1;
        now = vec[mid];
        Rebuild(now->ch[0], l, mid - 1);
        Rebuild(now->ch[1], mid + 1, r);
        now->Update();
    }

    void Insert(Node *&now, poi k) {
        if (!now) {
            now = new Node(k);
            return;
        }
        if (k < now->val) Insert(now->ch[0], k);
        else if (k == now->val) now->cnt++;
        else Insert(now->ch[1], k);
        now->Update();
        if (now->Bad()) {
            vec.clear();
            Dfs(now);
            int sz = vec.size();
            Rebuild(now, 0, sz - 1);
        }
    }

    void Remove(Node *now, poi k) {
        if (!now) return;
        if (k < now->val) {
            Remove(now->ch[0], k);
        } else if (k == now->val) {
            if (now->cnt) now->cnt--;
        } else {
            Remove(now->ch[1], k);
        }
        now->Update();
    }

    poi Kth(Node *now, int k) {
        if (!now) return make_pair(0, 0);
        int ls = (now->ch[0] ? now->ch[0]->siz : 0);
        if (k <= ls) return Kth(now->ch[0], k);
        else if (k == ls + 1) return now->val;
        else return Kth(now->ch[1], k - now->cnt - ls);
    }

    void PopInto(SGTree &tree, Node *now) {
        if (!now) return;
        for (int i = 1; i <= now->cnt; i++) tree.Insert(now->val);
        PopInto(tree, now->ch[0]);
        PopInto(tree, now->ch[1]);
        delete now;
    }

public :
    SGTree() {
        rt = NULL;
        vec.clear();
    }

    void Insert(poi k) {
        Insert(rt, k);
    }

    void Join(SGTree &tree) {
        tree.PopInto(*this, tree.rt);
    }

    poi Kth(int k) {
        return Kth(rt, k);
    }

    int Size() {
        return rt ? rt->siz : 0;
    }
};

SGTree tr[MAXN];

int bel[MAXN];

int Find(int x) {
    if (bel[x] == x) return x;
    return bel[x] = Find(bel[x]);
}

void Build(int a, int b) {
    int u = Find(a), v = Find(b);
    if (tr[u].Size() > tr[v].Size()) swap(u, v);
    bel[u] = v;
    tr[v].Join(tr[u]);
}

int main() {
    cin >> n >> m;
    int x, y, k, u, v;
    char op[5];
    for (int i = 1; i <= n; i++) bel[i] = i;
    for (int i = 1; i <= n; i++) {
        cin >> k;
        tr[i].Insert(make_pair(k, i));
    }
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        Build(x, y);
    }
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> op;
        if (op[0] == 'Q') {
            cin >> x >> k;
            u = Find(x);
            if (tr[u].Size() < k) {
                cout << -1 << endl;
                continue;
            }
            cout << tr[u].Kth(k).second << endl;
        } else {
            cin >> x >> y;
            Build(x, y);
        }
    }
    return 0;
}