[Easy] CF2069F Graph Inclusion

简要题意

有两个 $n$ 个点的无向图 $A,B$，有 $m$ 次操作，每次选定一个无向图并给出一条边 $(x,y)$，如果在对应的图中存在，就删除这条边，否则连接这条边。

在每一次操作结束时，你需要求出最少在 $A$ 中添加多少条边，使得对于 $B$ 的每个连通块 $S$，都可以找到 $A$ 的一个连通块 $T$，使得 $S\subseteq T$。

$1\leq n,m\leq 4\times 10^5$。

思路

首先题目中要求的东西非常抽象，不妨加以转化。我们不妨这样考虑：对于在 $B$ 中位于同一个连通块的两个点 $x,y$，如果在 $A$ 中分属两个连通块，那么这两个连通块中就需要连接一条边。那么当 $A$ 连最少的边以符合条件后，只要对于边 $(x,y)\in A\lor (x,y)\in B$，则 $x,y$ 就属于同一个连通块，故其实最后形成的图的所有连通块其实与 $A\cup B$ 相同。

若 $A\cup B$ 的连通块数比 $A$ 的连通块数少 $x$，那么就需要连 $x$ 条边以合并连通块。所以答案就是 $A$ 的连通块数量与 $A\cup B$ 的连通块数量之差。

于是我们需要维护一个动态图加边删边，求连通块数。直接维护极为困难，不过只加边可以用并查集轻易地完成，所以只需要线段树分治即可。时间复杂度 $O(m\log^2 n)$。

代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define ls (i << 1)
#define rs (i << 1 | 1)
using namespace std;

const int N = 4e5 + 5;
int n, m;

template<class T, int N>
struct static_stack {
    T stk[N];
    int tp;
    void push(const T& x){ stk[++tp] = x; }
    void pop(){ tp--; }
    T top(){ return stk[tp]; }
    int size(){ return tp; }
};

template<int N>
struct dynamic_componments {
    static_stack<pair<int,int>, N> fas;
    static_stack<pair<int,int>, N> sizs;
    static_stack<int, N> rets;
    int fa[N], siz[N], ret;

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

    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return;
        if(siz[x] < siz[y]) swap(x, y);
        fas.push({y, fa[y]}), sizs.push({x, siz[x]}), rets.push(ret);
        fa[y] = x, siz[x] += siz[y], ret--;
    }

    vector<pair<int,int>> t[N << 2];

    void update(int ql, int qr, pair<int,int> v, int i, int l, int r){
        if(ql <= l && r <= qr) return t[i].push_back(v), void();
        int mid = (l + r) >> 1;
        if(ql <= mid) update(ql, qr, v, ls, l, mid);
        if(mid < qr) update(ql, qr, v, rs, mid + 1, r);
    }

    int answer[N];

    void solve(int i, int l, int r){
        int lvl = fas.size();
        for(auto [x, y] : t[i]) merge(x, y);
        int mid = (l + r) >> 1;
        if(l == r) answer[l] = ret;
        else solve(ls, l, mid), solve(rs, mid + 1, r);
        while(fas.size() > lvl){
            fa[fas.top().first] = fas.top().second;
            siz[sizs.top().first] = sizs.top().second;
            ret = rets.top();
            fas.pop(), sizs.pop(), rets.pop();
        }
    }

    void init(int n){
        iota(fa + 1, fa + n + 1, 1), fill(siz + 1, siz + n + 1, 1);
        ret = n;
    }
};

dynamic_componments<N> da, dab;
map<pair<int,int>,int> pa, pb;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        char ch; int x, y;
        cin >> ch >> x >> y;
        tie(x, y) = minmax({x, y});
        if(ch == 'A'){
            if(pa.count({x, y})){
                da.update(pa[{x, y}], i - 1, {x, y}, 1, 1, m);
                dab.update(pa[{x, y}], i - 1, {x, y}, 1, 1, m);
                pa.erase({x, y});
            }
            else pa[{x, y}] = i;
        }
        else{
            if(pb.count({x, y})){
                dab.update(pb[{x, y}], i - 1, {x, y}, 1, 1, m);
                pb.erase({x, y});
            }
            else pb[{x, y}] = i;
        }
    }
    for(auto [x, y] : pa) da.update(y, m, x, 1, 1, m), dab.update(y, m, x, 1, 1, m);
    for(auto [x, y] : pb) dab.update(y, m, x, 1, 1, m);
    da.init(n), dab.init(n);
    da.solve(1, 1, m), dab.solve(1, 1, m);
    for(int i=1;i<=m;i++) cout << da.answer[i] - dab.answer[i] << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。