「LOJ 121」「离线可过」动态图连通性「按时间分治 」「并查集」

题意

你要维护一张\(n\)个点的无向简单图。你被要求执行\(m\)条操作，加入删除一条边及查询两个点是否连通。

• 0：加入一条边。保证它不存在。
• 1：删除一条边。保证它存在。
• 2：查询两个点是否联通。

\(n \leq 5\times 10^3, m \leq 5\times 10^5\)

题解

第一次写按时间分治的题，感觉还是比较 清新 有趣的

对时间建线段树，一个结点\([l, r]\)上存储在时间\([l, r]\)上存在的边集，那么询问在叶子结点上

对这颗线段树\(dfs\)，我们到一个结点就把边连起来（用并查集），可是需要回溯（即我们要把边撤销）。值得庆幸的是可以发现每次撤销的是当前最后一次加入的，所以使用按秩合并并查集就好。

复杂度：\(O(m \log n)\)

#include <algorithm>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
#define fs first
#define sc second
#define pb push_back
typedef pair<int, int> P;
const int N = 5e5 + 10;
const int M = 5010;
int n, m, Map[M][M], qs[N], qsum[N];
vector<P> edge, q, T;
bool ans[N];
struct Edge {
    int v, nxt;
} e[N * 35];
int hd[N << 2], c;
void push_edge(int id, int rt) {
    e[++ c] = (Edge) {id, hd[rt]}; hd[rt] = c;
}
void add(int u, int l, int r, int ql, int qr, int id) {
    if(l == ql && r == qr) { push_edge(id, u); return ; }
    int mid = (l + r) >> 1;
    if(qr <= mid) add(u << 1, l, mid, ql, qr, id);
    else if(ql > mid) add(u << 1 | 1, mid + 1, r, ql, qr, id);
    else {
        add(u << 1, l, mid, ql, mid, id);
        add(u << 1 | 1, mid + 1, r, mid + 1, qr, id);
    }
}
int nq, f[M], sz[M], st[N], top;
int find(int u) {
    return u == f[u] ? u : find(f[u]);
}
void dfs(int u, int l, int r) {
    if(qsum[r] == qsum[l - 1]) return ;
    int ntop = top;
    for(int i = hd[u]; i; i = e[i].nxt) {
        int u = find(edge[e[i].v].fs), v = find(edge[e[i].v].sc);
        if(u != v) {
            if(sz[u] < sz[v]) st[++ top] = u, f[u] = v, sz[v] += sz[u];
            else st[++ top] = v, f[v] = u, sz[u] += sz[v];
        }
    }
    if(l == r) {
        if(qs[l]) qs[l] --, ans[qs[l]] = find(q[qs[l]].sc) == find(q[qs[l]].fs);
    } else {
        int mid = (l + r) >> 1;
        dfs(u << 1, l, mid);
        dfs(u << 1 | 1, mid + 1, r);
    }
    while(top > ntop) {
        int u = st[top --];
        sz[f[u]] -= sz[u];
        f[u] = u;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++) {
        int op, x, y, tmp;
        scanf("%d%d%d", &op, &x, &y);
        if(x > y) swap(x, y);
        if(op == 0) {
            if(!Map[x][y]) {
                int id = (int) edge.size();
                Map[x][y] = id + 1;
                edge.pb(P(x, y));
                T.pb(P(i, m));
            }
        }
        if(op == 1) {
            if(tmp = Map[x][y]) {
                T[tmp - 1].sc = i;
                Map[x][y] = 0;
            }
        }
        if(op == 2) { qs[i] = (int) q.size() + 1; q.pb(P(x, y)); }
        qsum[i] = qsum[i - 1] + qs[i];
    }
    for(int i = 0; i < edge.size(); i ++) {
        add(1, 1, m, T[i].fs, T[i].sc, i);
    }
    for(int i = 1; i <= n; i ++) f[i] = i, sz[i] = 1;
    dfs(1, 1, m);
    for(int i = 0; i < q.size(); i ++) puts(ans[i] ? "Y" : "N");
    return 0;
}

「LOJ 121」「离线可过」动态图连通性「按时间分治 」「并查集」

原文：https://www.cnblogs.com/hongzy/p/11633403.html