AGC002D Stamp Rally 多种做法 kruskal重构树/可持久化并查集/整体二分-JZTXT

D - Stamp Rally (atcoder.jp)

这题做法很多，我写的是可持久化并查集做法，但是裸的可持久化并查集是 $O(nlog^3n)$，能过但是很慢！看洛谷的题解有一位大佬写了一个很妙的并查集的写法，按秩合并，每一步合并时用vector记录一下这个被合并到的节点的size和当前的时间，这样做可以找到每一个时间每一个节点的集合的size，时间复杂度是 $O(nlog^2n)$，非常巧妙！

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 2e5 + 10;

int sz[N], f[N], tim[N];
int find(int x, int t) {
    while(t >= tim[x]) {
        x = f[x];
    }
    return x;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> upd(n + 1);
    for(int i = 1; i <= n; i++) {
        f[i] = i, sz[i] = 1, tim[i] = m + 1, upd[i].push_back({0, 1});
    }
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int x = find(u, i), y = find(v, i);
        if(x == y) continue;
        if(sz[x] < sz[y]) swap(x, y);
        tim[y] = i;
        f[y] = x;
        sz[x] += sz[y];
        upd[x].push_back({i, sz[x]});
    }
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        int u, v, z;
        cin >> u >> v >> z;
        auto check = [&](int t) {
            int x = find(u, t), y = find(v, t);
            if(x == y) {
                auto it = --upper_bound(upd[x].begin(), upd[x].end(), make_pair(t, n + 1));
                return it -> second >= z;
            }
            else {
                auto it1 = --upper_bound(upd[x].begin(), upd[x].end(), make_pair(t, n + 1));
                auto it2 = --upper_bound(upd[y].begin(), upd[y].end(), make_pair(t, n + 1));
                return it1 -> second + it2 -> second >= z;
            }
        };
        int lo = 1, hi = m;
        while(lo < hi) {
            int mid = lo + hi >> 1;
            if(check(mid)) hi = mid;
            else lo = mid + 1;
        }
        cout << lo << '\n';
    }
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    t = 1;

    while(t--) {
        solve();
    }

    return 0;
}

做法