TIOJ 1843：傳說中的編譯器，上集。

TIOJ 1843：傳說中的編譯器，上集。

題目大意：給你一張圖，每個點有點權，有三種操作，第一種是詢問某個點所屬連通塊第 $k$ 大的點權，第二種是將某點點權改變，第三種是將某條邊刪掉。

解法：因為刪邊很難，所以可以反過來加邊，然後問第 $k$ 大可以用一個 $\text{treap}$ 維護，每次合併可以啟發式合併。

$\text{Code：}$

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 2e4 + 5;
const int M = 6e4 + 5;

mt19937 seed (87);
struct T {
    int prior = uniform_int_distribution<int> (0, 2e9) (seed);
    int val, siz = 1;
    T *ls = NULL, *rs = NULL, *fa = NULL;
    void Reset() {
        siz = 1;
        ls = rs = fa = NULL;
    }
    void Pull() {
        siz = (ls ? ls->siz : 0) + (rs ? rs->siz : 0) + 1;
        if (ls) ls->fa = this;
        if (rs) rs->fa = this;
    }
};

int siz (T *t) {
    return t ? t->siz : 0;
}

T *Merge (T *a, T *b) {
    if (!a || !b) return a ? a : b;
    if (a->prior <= b->prior) {
        a->rs = Merge (a->rs, b);
        a->Pull();
        return a;
    } else {
        b->ls = Merge (a, b->ls);
        b->Pull();
        return b;
    }
}

void Split (T *t, T *&a, T *&b, int k) {
    if (t == NULL) {
        a = b = NULL;
        return;
    }
    if (k <= siz (t->ls)) {
        b = t;
        Split (t->ls, a, b->ls, k);
        b->Pull();
    } else {
        a = t;
        Split (t->rs, a->rs, b, k - siz (t->ls) - 1);
        a->Pull();
    }
}

void SplitT (T *t, T *&a, T *&b, int k) {
    if (t == NULL) {
        a = b = NULL;
        return;
    }
    if (t->val < k) {
        a = t;
        SplitT (t->rs, a->rs, b, k);
        a->Pull();
    } else {
        b = t;
        SplitT (t->ls, a, b->ls, k);
        b->Pull();
    }
}

T *Find (T *t) {
    while (t->fa != NULL) t = t->fa;
    return t;
}

int n, m;
int a[N];
T *root, *t[N];
bitset<M> is;
pair<int, int> e[M];
vector<tuple<char, int, int>> op;

void Insert (T *&root, T *t) {
    T *t1, *t2;
    SplitT (root, t1, t2, t->val);
    root = Merge (Merge (t1, t), t2);
}

void dfs (T *t) {
    if (t->ls) {
        dfs (t->ls);
        t->ls = NULL;
    }
    if (t->rs) {
        dfs (t->rs);
        t->rs = NULL;
    }
    t->fa = NULL;
    t->Pull();
    Insert (root, t);
}

void MergeT (int a, int b) {
    T *ta = Find (t[a]), *tb = Find (t[b]);
    if (ta == tb) return;
    if (siz (ta) < siz (tb)) swap (ta, tb);
    root = ta;
    dfs (tb);
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt = 0;
    while (cin >> n >> m && n) {
        cout << "Sekai " << ++tt << ": ";
        op.clear();
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= m; i++) {
            int a, b;
            cin >> a >> b;
            e[i] = {++a, ++b};
            is[i] = 0;
        }
        char c;
        while (cin >> c && c != 'E') {
            int x, k;
            cin >> x;
            x++;
            if (c == 'Q') {
                cin >> k;
                op.emplace_back (c, x, k);
            }
            if (c == 'C') {
                cin >> k;
                op.emplace_back (c, x, a[x]);
                a[x] = k;
            }
            if (c == 'D') {
                op.emplace_back (c, x, 0);
                is[x] = 1;
            }
        }
        reverse (op.begin(), op.end());
        for (int i = 1; i <= n; i++) {
            if (t[i] == NULL) t[i] = new T();
            t[i]->Reset();
            t[i]->val = a[i];
        }
        for (int i = 1; i <= m; i++) if (!is[i]) {
            MergeT (e[i].first, e[i].second);
        }
        ll sum = 0;
        int cnt = 0;
        for (auto [c, x, k] : op) {
            if (c == 'Q') {
                cnt++;
                root = Find (t[x]);
                k = root->siz - k + 1;
                if (k <= 0) continue;
                T *t1, *t2;
                Split (root, t1, root, k - 1);
                Split (root, root, t2, 1);
                sum += root->val;
                Merge (Merge (t1, root), t2);
            }
            if (c == 'C') {
                root = Find (t[x]);
                T *tmp, *t1, *t2;
                SplitT (root, t1, tmp, a[x]);
                Split (tmp, tmp, t2, 1);
                root = Merge (t1, t2);
                a[x] = tmp->val = k;
                Insert (root, tmp);
            }
            if (c == 'D') {
                MergeT (e[x].first, e[x].second);
            }
        }
        cout << fixed << setprecision (6) << (double) sum / cnt << '\n';
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！