TIOJ 1903：【Gate】這個笑容由我來守護 - EXTREME

TIOJ 1903：【Gate】這個笑容由我來守護 - EXTREME

題目大意：有 $n$ 個點，給你一些操作：在 $a, b$ 加一條邊或在 $a, b$ 減一條邊，每次操作完問有幾個連通塊。

解法：如果不刪邊，用並查集就可以了，但是現在要刪邊，所以勢必要取消操作，那要如何取消操作呢？合併時可按照大小合併，並記錄被合併點原本的大小，之後恢復就好了，所以可以用一個線段樹存操作，每個節點的區間代表這個操作存在的區間，每次進來節點時執行操作，出去節點時取消操作，並同時記錄連通塊的數量。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int SIZE = 5e5 + 5;

int n, m, q, cc, to[SIZE], h[SIZE];
vector<pair<int, int>> seg[4 * SIZE];   /// time segment tree
vector<tuple<int, int, int>> op;        /// a, b, size[b]
vector<tuple<int, int, int, bool>> all; /// a, b, time, Del?

int dsu (int x) {
    while (x != to[x])
        x = to[x];
    return x;
}

bool Merge (int a, int b) {
    a = dsu (a), b = dsu (b);
    if (a == b)
        return 0;
    if (h[a] < h[b])
        swap (a, b);
    op.pb (a, b, h[b]);
    to[b] = a, h[a] += h[b];
    cc--;
    return 1;
}

void Undo() {
    auto [a, b, sz] = op.back();
    op.pop_back();
    to[b] = b, h[a] -= sz;
    cc++;
}

void Insert (int pos, int l, int r, int L, int R, pair<int, int> p) {
    if (l == L && r == R)
        seg[pos].pb (p);
    else {
        int mid = (L + R) / 2;
        if (r <= mid)
            Insert (lpos, l, r, L, mid, p);
        else if (l > mid)
            Insert (rpos, l, r, mid + 1, R, p);
        else {
            Insert (lpos, l, mid, L, mid, p);
            Insert (rpos, mid + 1, r, mid + 1, R, p);
        }
    }
}

void dfs (int pos, int l, int r) {
    int cnt = 0;
    for (auto [a, b] : seg[pos]) {
        if (Merge (a, b))
            cnt++;
    }
    if (l == r) {
        if (l)
            cout << cc << '\n';
    } else {
        int mid = (l + r) / 2;
        dfs (lpos, l, mid);
        dfs (rpos, mid + 1, r);
    }
    while (cnt--)
        Undo();
    seg[pos].clear();
}

void solve() {
    all.clear();
    cin >> n >> m >> q;
    cc = n;
    FOR (i, 1, n) to[i] = i, h[i] = 1;
    FOR (i, 1, m) {
        int a, b;
        cin >> a >> b;
        a++, b++;
        if (a > b)
            swap (a, b);
        all.pb (a, b, 0, 0);
    }
    FOR (i, 1, q) {
        char c;
        int a, b;
        cin >> c >> a >> b;
        a++, b++;
        if (a > b)
            swap (a, b);
        all.pb (a, b, i, c == 'D');
    }
    sort (all.begin(), all.end());
    int cnt = 0, last;
    for (int i = 0; i < all.size(); i++) {
        auto [a, b, t, d] = all[i];
        if (!d) {
            if (!cnt)
                last = t;
            cnt++;
        } else {
            cnt--;
            if (!cnt)
                Insert (1, last, t - 1, 0, q, {a, b});
        }
        if (cnt && (i == all.size() - 1 || (a != get<0> (all[i + 1]) || b != get<1> (all[i + 1])))) {
            cnt = 0;
            Insert (1, last, q, 0, q, {a, b});
        }
    }
    dfs (1, 0, q);
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    int tt;
    cin >> tt;
    while (tt--)
        solve();
}

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