并查集 | kruskal重构树

Crescent_ · 2022-03-10 16:07:14 · 个人记录

1.Problem: D. The Door Problem

每扇门由两个开关控制,如果初始为1,那么两个开关最后一定都是1或者0,如果初始为 0,那么两个开关最后一定是10或01,将一个开关分为两个状态开和不开,枚举每扇门的两个开关,将合法的两个状态合并在一起,最后枚举每个开关的两个状态,如果两个状态在一个并查集里面就非法,否则肯定起码有一个并查集涵盖了每个开关的一个状态

const int N = 2e5 + 10;

int n, m, w[N], r[N], p[N];
vi d[N];

int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}

void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    p[pa] = pb;
}

bool test(int a, int b) {
    int pa = find(a), pb = find(b);
    return pa == pb;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) read(r[i]);
    for (int i = 1; i <= m; i ++ ) {
        int x; read(x);
        while (x -- ) {
            int a; read(a);
            d[a].pb(i);         
        }
    }
    for (int i = 1; i <= m << 1; i ++ ) p[i] = i;
    for (int i = 1; i <= n; i ++ ) {
        if (r[i]) {
            auto &v = d[i];
            merge(v[0], v[1]);
            merge(v[0] + m, v[1] + m);
        } else {
            auto &v = d[i];
            merge(v[0], v[1] + m);
            merge(v[0] + m, v[1]);
        }
    }
    for (int i = 1; i <= m; i ++ ) {
        if (test(i, i + m)) return puts("NO"), 0;
    }
    return puts("YES"), 0;
}

2.P5937 [CEOI1999]Parity Game

设前缀和s[i]表示前i个数中1的个数,那么对于区间[l, r]来说,
 如果为奇数,s[r]和s[l-1]肯定一奇一偶,如果为偶数s[r]和s[l-1]肯定两个奇数或者两个偶数
使用多并查集,将每个s[i]的状态分为奇数和偶数,按询问将对应的状态合并在一个并查集中,
如果某个s[i]的奇偶状态在一个并查集中就非法,否则肯定有一个合法的状态，注意s[0]也是一个状态

const int N = 1e5 + 10;

int n, m, w[N], idx, p[N];
char s[6];

struct Q {
    int l, r, op;
}q[N];

int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}

void merge(int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa != pb) {
        p[pa] = pb;
    }
}

bool test(int a, int b) {
    int pa = find(a), pb = find(b);
    return pa == pb;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        read(q[i].l), read(q[i].r); cin >> s;
        if (*s == 'e') q[i].op = 1;
        w[ ++ idx] = q[i].l; w[ ++ idx] = q[i].r;
    }
    sort(w + 1, w + 1 + idx);
    int tot = unique(w + 1, w + 1 + idx) - w - 1;
    for (int i = 1; i <= tot + tot + 1; i ++ ) p[i] = i;
    n = tot + 1;
    for (int i = 1; i <= m; i ++ ) {
        int l = q[i].l, r = q[i].r, op = q[i].op;
        l = lower_bound(w + 1, w + 1 + tot, l) - w;
        r = lower_bound(w + 1, w + 1 + tot, r) - w;
        if (op) {
            merge(l - 1, r);
            merge(l + n - 1, r + n);
        } else {
            merge(l - 1, r + n);
            merge(l - 1 + n, r);
        }
        if (test(l - 1, l + n - 1) || test(r, r + n)) return cout << i - 1 << "\n", 0;
    }
    cout << m << "\n";
    return 0;
}

3.#176. 新年的繁荣

给定一个完全图,有点权w, 定义边权[u->v] = w[u] & w[v],求全图的最大生成树

const int N = 1e5 + 10;

int n, m, w[(1 << 19)], p[N], cnt;
LL ans;

int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}

inline bool test(int x, int y, bool un = false) {
    if ((x = find(x)) == (y = find(y))) return true;
    if (un) cnt ++ , p[x] = y; return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        int x; read(x); p[i] = i;
        w[x] ? ans += x : w[x] = i;
    }
    for (int i = (1 << m) - 1; i; i -- ) {
        if (cnt == n - 1) break;
        int &u = w[i]; int j;
        for (j = 0; j < m && !u; j ++ ) u = w[i | 1 << j];
        for (; j < m; j ++ ) {
            int v = w[i | 1 << j];
            if (v && !test(u, v, true)) ans += i;
        }
    }
    cout << ans << "\n";
    return 0;
}

4.CF915F Imbalance Value of a Tree

给定一棵树，每个顶点都被写上了一个数，第i个顶点写上的数是a_i。定义一个函数I(x,y)表示从顶点x到y的简单路径上a_i 的最大值和最小值的差。你要求出\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)

const int N = 1e6 + 10;

int n, m, A[N], p[N], cnt[N];
LL ans;

struct E {
    int a, b, w;
}e[N];

int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}

inline bool test(int x, int y, int w, bool un = false) {
    if ((x = find(x)) == (y = find(y))) return true;
    if (un) p[x] = y, ans += 1ll * cnt[x] * cnt[y] * w, cnt[y] += cnt[x]; return false;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) read(A[i]), p[i] = i, cnt[i] = 1;
    for (int i = 1; i < n; i ++ ) {
        int a, b; read(a), read(b);
        e[i] = {a, b, max(A[a], A[b])};
    }   
    sort(e + 1, e + n, [&](const E &A, const E &B){return A.w < B.w;});
    for (int i = 1; i < n; i ++ ) {
        int a = e[i].a, b = e[i].b, w = e[i].w;
        test(a, b, w, true);
        e[i].w = max(-A[a], -A[b]);
    }
    sort(e + 1, e + n, [&](const E &A, const E &B){return A.w < B.w;});
    for (int i = 1; i <= n; i ++ ) p[i] = i, cnt[i] = 1;
    for (int i = 1; i < n; i ++ ) {
        int a = e[i].a, b = e[i].b, w = e[i].w;
        test(a, b, w, true);
    }
    cout << ans << "\n";
    return 0;
}

5.#4242. 水壶

平面图的 |E| < 3n - 6

网格图用bfs转化为平面图,由题意求的是s到t的路径在最小生成树中的最长边, 可以用树上倍增log简单维护(常数较大?不知道为什么过不去)或者kruskal重构树(按边权合并连通块pa,pb，连接的不是pa和pb而是新建一个点fa,让fa的权值等于这条边的权值,然后fa成为pa和 pb的父亲,这样查询{x,y}中路径中边权的最大值必定是他们的LCA的权值

const int N = 2e3 + 10, M = 4e5 + 10, maxE = 1e7;

int n, m, w[M * 6], p[M], R, C, idx, cnt, Q;
int g[N][N], d[N][N], st[N][N], dep[M], D[M][20], P[M][20];
int h[M], e[M * 6], ne[M * 6], V, val[M];
char s[N];
pi q[N * N], S[M];

struct Edge {
    int a, b, w;
    inline bool operator< (const Edge &B) const {return w < B.w;}
} E[maxE];

inline void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
} 

void bfs() {
    int dx[] = {0, 0, 1, -1}, dy[] = {-1, 1, 0, 0};
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ ) q[ ++ tt] = S[i], st[S[i].fi][S[i].se] = i;
    while (hh <= tt) {
        auto t = q[hh ++ ];
        for (int i = 0; i < 4; i ++ ) {
            int nx = t.fi + dx[i], ny = t.se + dy[i];
            if (!g[nx][ny]) continue;
            int X = st[t.fi][t.se], &Y = st[nx][ny];
            if (Y) {
                if (X >= Y) continue;
                int W = d[t.fi][t.se] + d[nx][ny];
                E[ ++ cnt] = {X, Y, W};
                continue;
            }
            Y = X;
            d[nx][ny] = d[t.fi][t.se] + 1;
            q[ ++ tt] = {nx, ny};
        }
    }
}

int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}

void kruskal() {
    sort(E + 1, E + 1 + cnt);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    int Ek = 0; V = n;
    for (int i = 1; i <= cnt; i ++ ) {
        int a = E[i].a, b = E[i].b, w = E[i].w;
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            ++ V;
            p[pa] = p[pb] = p[V] = V;
            val[V] = w;
            add(V, pa), add(V, pb);
            if ( ++ Ek == n - 1) return ;
        }
    }
}

void dfs(int u, int fa) {
    for (int i = 1; i < 19 && P[u][i - 1]; i ++ ) {
        P[u][i] = P[P[u][i - 1]][i - 1];
    }
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        P[j][0] = u, dep[j] = dep[u] + 1;
        dfs(j, u);
    }
}

int query(int x, int y) {
    if (find(x) != find(y)) return -1;
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 18; i >= 0; i -- )
        if (dep[x] - (1 << i) >= dep[y]) x = P[x][i];
    if (x == y) return val[x];
    for (int i = 18; i >= 0; i -- )
        if (P[x][i] != P[y][i])
            x = P[x][i], y = P[y][i];
    return val[x == y ? x : P[x][0]];
}

int main() {
    cin >> R >> C >> n >> Q;
    for (int i = 1; i <= R; i ++ ) {
        scanf("%s", s + 1);
        for (int j = 1; j <= C; j ++ ) g[i][j] = s[j] == '.';
    }
    for (int i = 1; i <= n; i ++ ) {
        int a, b; read(a), read(b);
        S[i] = {a, b};
    }
    bfs();
    kruskal();
    for (int i = 1; i <= V; i ++ ) if (!dep[i]) {
        int pa = find(i); dep[pa] = 1;
        dfs(pa, 0);
    }
    while (Q -- ) {
        int a, b; read(a), read(b);
        printf("%d\n", query(a, b));
    }
    return 0;
}

6.#14. 【UER #1】DZY Loves Graph [撤销按秩合并离线]

如果没有撤销操作,对于操作2,就是删除最后加的k条边,mst用并查集维护还需要支持删除操作,故并查集不能使用路径压缩且需要使用按秩合并,对于断开u,p[u]的操作,只需让 sz[p[u]] -= sz[u], p[u] = u 即可,加上撤销操作,由于只撤销一次,可以分别考虑对操作1,2产生的影响,add a,b直接变成delete 1,delete k变成连接最近的k条边,可以记录mst[i]表示i条边时最小生成树的大小,那么这一步可以不删边,直接输出mst[now-k]即可,我们可以通过预先读入离线操作判断下一步是否撤销

const int N = 5e5 + 10;

int n, m, A[N], p[N], sz[N], t;
int edge[N], hist[N];
LL mst[N];

struct Q {
    int op, a, b;
}q[N];

inline int find(int x) {return x == p[x] ? x : find(p[x]);}

void add(int a, int b, int c) {
    ++ t;
    if ((a = find(a)) == (b = find(b))) {
        hist[t] = 0; edge[t] = edge[t - 1]; mst[t] = mst[t - 1];
    } else {
        if (sz[a] > sz[b]) swap(a, b);
        hist[t] = a; p[a] = b; sz[b] += sz[a]; edge[t] = edge[t - 1] + 1;
        mst[t] = mst[t - 1] + c;
    }
}

void del(int l, int r) {
    for (int i = r; i >= l; i -- ) {
        int x = hist[i];
        sz[p[x]] -= sz[x]; p[x] = x;
    }
    t = l - 1;
}

void print(int time) {
    printf("%lld\n", edge[time] == n - 1 ? mst[time] : 0);
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i, sz[i] = 1;
    char op[10]; int a, b;
    for (int i = 1; i <= m; i ++ ) {
        if (scanf("%s", op), *op == 'A') {
            read(a), read(b); 
            q[i] = {1, a, b};
        } else if (*op == 'D') {
            read(a);
            q[i] = {2, a};
        } else {
            q[i].op = 3;
        }
    }   
    for (int i = 1; i <= m; i ++ ) {
        if (q[i].op == 1) {
            add(q[i].a, q[i].b, i); print(t);
            if (q[i + 1].op == 3) {
                del(t, t); 
            } 
        } else if (q[i].op == 2) {
            if (q[i + 1].op == 3) {
                print(t - q[i].a);
            } else {
                del(t - q[i].a + 1, t);
                print(t);
            }
        } else {
            print(t);
        }
    }
    return 0;
}

7.Problem: CF1416D Graph and Queries

题目只要求与 u 连通的最大点，可以用并查集维护，但是还要修改，考虑用树来维护这种连通关系，那么修改和查询就可以用树剖了，根据套路将删边操作看着倒着加边，kruskal 重构树还可以维护时间信息，比如 t 时刻树的根为 V ，那么我们将这颗树的所有点的祖先标记为 V ，在 t 时刻后加入的边可能会改变这棵树的根，但是只会是原来的根的祖先（树只会往上增加），那么如果我们需要查询 t 时刻以前的信息，只需要对原先记录的那个根代表的子树通过树剖查询即可

const int N = 6e5 + 54;

int n, m, A[N], id[N], o[N], p[N], P[N], V, Q, cnt, val[N], eid[N];
int q[N];
int h[N], e[N], ne[N], idx;
pi edge[N];
bool st[N];

inline void add(int a, int b) {
    p[b] = a;
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int find(int x) {return x == P[x] ? x : P[x] = find(P[x]);}
void connect(int x, int y) {
    if ((x = find(x)) == (y = (find(y)))) return;
    V ++ ; P[x] = P[y] = P[V] = V; add(V, x), add(V, y);
}

void dfs(int u, int fa) {
    p[u] = fa; o[ ++ cnt] = u; id[u] = cnt;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i]; if (j == fa) continue;
        dfs(j, u);
    }
    eid[u] = cnt;
}

namespace ST {
    #define segc int mid = (l + r) >> 1, lc = u << 1, rc = lc | 1
    int x[N];
    void build(int u, int l, int r) {
        if (l == r) {x[u] = (o[l] > n ? 0 : o[l]); return ;}
        segc;
        build(lc, l, mid), build(rc, mid + 1, r);
        x[u] = max(x[lc], x[rc]);
    }
    int range(int u, int l, int r, int L, int R) {
        if (L <= l && r <= R) return x[u];
        segc; int res = 0;
        if (L <= mid) res = range(lc, l, mid, L, R);
        if (R > mid) chkmax(res, range(rc, mid + 1, r, L, R));
        return res;
    }
    void adj(int u, int l, int r, int h, int v) {
        if (l == h && r == h) {x[u] = v; return;}
        segc;
        if (h <= mid) adj(lc, l, mid, h, v);
        if (h > mid) adj(rc, mid + 1, r, h, v);
        x[u] = max(x[lc], x[rc]);
    } 
}

int main() {
    cin >> n >> m >> Q; V = n;
    for (int i = 1; i <= n; i ++ ) read(val[i]);
    for (int i = 1; i <= m; i ++ ) {
        int a, b; read(a), read(b);
        edge[i] = {val[a], val[b]};
    }
    for (int i = 1; i <= Q; i ++ ) {
        int op, v; read(op), read(v);
        q[i] = (op == 1 ? val[v] : (st[v] = true, -v));
    }
    iota(P + 1, P + 1 + n, 1);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ ) if (!st[i]) {
        connect(edge[i].fi, edge[i].se);
    }
    for (int i = Q; i >= 1; i -- ) {
        int v = q[i];
        if (v > 0) q[i] = find(q[i]);
        else connect(edge[-v].fi, edge[-v].se);
    }
    for (int i = 1; i <= V; i ++ ) if (!p[i]) dfs(i, 0);
    assert(cnt == V);
    ST::build(1, 1, cnt);
    for (int i = 1; i <= Q; i ++ ) {
        int v = q[i];
        if (v > 0) {
            // cout << i << ' ' << v << "-->" << eid[v] << "\n";    
            int u = ST::range(1, 1, cnt, id[v], eid[v]);
            cout << u << "\n";
            if (u) ST::adj(1, 1, cnt, id[u], 0);
        } 
    }
    return 0;
}