Codeforces 1706E 并查集 + 启发式合并 + ST 表

传送门 Codeforces 1706E Qpwoeirut and Vertices

区间 [ l , r ] [l,r] [l,r] 连通的充要条件是 [ i , i + 1 ] , i ∈ [ l , r ) [i,i+1], iin [l,r) [i,i+1],i∈[l,r) 连通。问题转化为求解使 i , i + 1 , i ∈ [ 0 , n − 1 ) i,i+1,iin [0,n - 1) i,i+1,i∈[0,n−1) 连通的最小的最大边编号；最后 RMQ 查询即可，实现上使用 ST 表。

边编号从小到大依次考虑，使用并查集维护连通性。 i , i + 1 i,i+1 i,i+1 合并时的边编号即为所求。考虑启发式合并，并查集维护所包含的点集，合并前检查规模较小的点集的任一点 i i i，检查 i − 1 i-1 i−1 或 i + 1 i+1 i+1 是否在另一连通分量中；合并时点集规模较小的合并到规模较大的点集中。平衡树维护点集，节点插入以及节点检查次数都是 O ( n log ⁡ n ) O(nlog n) O(nlogn)。

总时间复杂度 O ( n log ⁡ 2 n ) O(nlog^2 n) O(nlog2n)。

构造最小生成树，然后树上 LCA，可以做到 O ( n log ⁡ n ) O(nlog n) O(nlogn)。

#include 
using namespace std;

struct DSU
{
    vector par;
    vector> st;
    DSU(int _n) : par(_n), st(_n)
    {
        for (int i = 0; i < _n; ++i)
            par[i] = i, st[i].insert(i);
    }
    int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); }
    bool same(int x, int y) { return find(x) == find(y); }
    vector unite(int x, int y)
    {
        vector res;
        x = find(x), y = find(y);
        if (x == y)
            return {};
        if (st[x].size() > st[y].size())
            swap(x, y);
        par[x] = y;
        for (int i : st[x])
        {
            if (st[y].count(i + 1))
                res.push_back(i);
            if (st[y].count(i - 1))
                res.push_back(i - 1);
        }
        st[y].insert(st[x].begin(), st[x].end());
        return res;
    }
};

struct ST
{
    int n;
    vector> dat;
    vector lg;
    ST(vector &a) : n((int)a.size())
    {
        lg = vector(n + 1);
        lg[0] = -1;
        for (int i = 1; i <= n; ++i)
            lg[i] = lg[i - 1] + (i == (1 << (lg[i - 1] + 1)));
        dat = vector>(lg[n] + 1, vector(n));
        for (int i = 0; i < n; ++i)
            dat[0][i] = a[i];
        for (int k = 0; k < lg[n]; ++k)
            for (int i = 0; i + (1 << k) <= n; ++i)
                dat[k + 1][i] = max(dat[k][i], dat[k][i + (1 << k)]);
    }
    int ask(int l, int r)
    {
        int k = lg[r - l];
        return max(dat[k][l], dat[k][r - (1 << k)]);
    }
};

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        int N, M, Q;
        cin >> N >> M >> Q;
        DSU dsu(N);
        vector tmp(N - 1);
        for (int i = 0; i < M; ++i)
        {
            int u, v;
            cin >> u >> v;
            --u, --v;
            auto a = dsu.unite(u, v);
            for (int j : a)
                tmp[j] = i + 1;
        }
        ST stb(tmp);

        vector res(Q, -1);
        for (int i = 0; i < Q; ++i)
        {
            int l, r;
            cin >> l >> r;
            if (l == r)
                res[i] = 0;
            else
                res[i] = stb.ask(l - 1, r - 1);
        }

        for (int i = 0; i < Q; ++i)
            cout << res[i] << " n"[i + 1 == Q];
    }
    return 0;
}