题解：CF1814F Communication Towers

· · 题解

对于某些边在一段时间内出现的问题，一般采用线段树分治的方法，线段树分治一般在可撤销并查集的基础上实现。

这题比较巧妙，其实是线段树分治板子加上一个小技巧。

注意到有「i 和 1 连通」的要求，发现在叶子节点时，不借助其它东西无法完成答案统计。

这个时候有一个小技巧：引入标记数组。

我们引入 tag_i 表示点 i 对应集合的根曾经是否与点 1 连通。

发现在并查集合并和撤销时可以非常容易地维护 tag 信息。

具体地，在 Merge 时，假设有操作 fa_x=y，则要保证 x 的 tag 信息不发生变化，就要考虑如何维护此时的 tag_x。

发现如果将 x 和 y 合并时，由于二者之前位于不同集合，而现在 y 为 x 所在集合的根。故将 tag_x 减去 tag_y 后，二者信息可正确维护。

在线段树上 ask 时，到叶子节点时，将节点 1 此时所在集合根的 tag 加上 1。

同样的，在 Undo 时，将 tag_x 做相反操作，即将 tag_x 加上 tag_y。

最后若某个点的 tag 大于 0 则此点在某时刻与 1 相连通。

时间复杂度为正常的线段树分治复杂度 O(M \log^2N)。

线段树分治时尤其注意并查集数组的大小。可以像我一样开 2e6，怎么都不会 RE。

顺带一提，本题给的是点的出现时间，故连边时注意左右区间，可以参考代码实现。

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define pb push_back
#define PII pair<int, int>

using namespace std;
const int N = 2e6 + 5;
int n, m, k, u[N], v[N], l[N], r[N], ans[N], tag[N];
vector<PII> e[N * 2];//没必要再乘2了

struct Union {
    int fa[N], siz[N];
    stack<PII> st;

    void init() {
        rep(i, 1, n) fa[i] = i, siz[i] = 1;
    }

    int get(int x) {
        return x == fa[x] ? x : get(fa[x]);
    }

    void merge(int x, int y) {
        x = get(x), y = get(y);
        if(x == y) return;
        if(siz[x] > siz[y]) swap(x, y);
        st.push({x, y});
        fa[x] = y, siz[y] += siz[x];
        tag[x] -= tag[y];
    }

    void undo(int last) {
        while(st.size() > last) {
            int x = st.top().first, y = st.top().second;
            st.pop();
            fa[x] = x, siz[y] -= siz[x];
            tag[x] += tag[y];
        }
    }

} DSU;

stack<PII> T;

struct SegmentTree {
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid (l + r >> 1)

    void upd(int p, int l, int r, int L, int R, int u, int v) {
        if(L > r || l > R) return;
        if(L <= l && r <= R)
            return e[p].pb({u, v}), void();
        upd(ls, l, mid, L, R, u, v), upd(rs, mid + 1, r, L, R, u, v);
    }

    void ask(int p, int l, int r) {
        int S = DSU.st.size();
        for(auto ed : e[p]) {
            int x = ed.first, y = ed.second;
            DSU.merge(x, y);
        }
        if(l == r) ++tag[DSU.get(1)];
        else ask(ls, l, mid), ask(rs, mid + 1, r);
        DSU.undo(S);
    }
} SGT;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);

    int mx = 0;

    cin >> n >> m;
    DSU.init();
    rep(i, 1, n) cin >> l[i] >> r[i], mx = max(mx, r[i]);
    rep(i, 1, m) cin >> u[i] >> v[i];
    rep(i, 1, m) SGT.upd(1, 0, mx, max(l[u[i]], l[v[i]]), min(r[u[i]], r[v[i]]), u[i], v[i]);

    SGT.ask(1, 0, mx);
    rep(i, 1, n) if(tag[i]) cout << i << ' ';

}