题解：CF1290C Prefix Enlightenment / ARIS0_0 - 55

小屹0_0 · 2026-06-10 21:41:39 · 题解

前言

这是一个不错的问题，做的时候特地去私信风铃草她的做法怎么做，真不会 /dk，看了风铃草的题解不懂在说什么，还看不懂代码，我太菜了 /dk。

思路

首先，我们需要认识到，对于任意三个子集交集为空，其实是保证了，对于任意一个数字，不可能包含在三个集合当中。

考虑到不处于任何集合中的点无法改变，因此对于答案没有影响（题目保证了有解），所以我们完全可以扔掉。

我们讨论一个点：

包含在一个集合。
包含在两个集合。

以及一个点：

初始是开。
初始是关。

于是：

属于一个集合并初始是开：这个集合不能操作。
属于一个集合并初始是关：这个集合必须操作。
属于两个集合并初始是开：这两个集合状态相同。
属于两个集合并初始是关：这两个集合状态不同。

这里做出补充说明：一个集合的状态，是指这个集合有没有被操作。此外，不难发现一个集合只有被操作和不被操作两个状态，我们对一个集合操作多次是没有意义的。

我们将集合看做点，状态之间的关系看做边，那么这就类似但不完全是一个二分图，设这个图为 G。

我们把问题换成二分图染色视角，将操作看成一种颜色，不操作看成另一种。对于两个点，关系就是要么颜色相同，要么颜色不同。

这显然可以通过一个朴素的类二分度染色 dfs 算法完成。

于是我们找到了一种全局的符合条件的染色（及操作）方案。

接下来考虑动态查前缀询怎么做。

我们把这个东西想象成每一次加入一个点 i，我们来观察发生了什么。

如果 i 不在任何集合，没有印象，输出上一次的答案（不变），并跳过。

如果 i 在两个集合，这两个集合的答案应合并，但是用什么合并暂未可知。

如果 i 在一个集合，这等价于强制要求了某一个集合的颜色。

接下来我们考虑刻画这个过程，我们维护一个新图 G'，我们合并两个点，等价于在我们在 G' 中加入某一条 G 中的边。

对于确定一个点的颜色，我们其实是强制要求了一个联通块的颜色。

不难发现，当一个联通块没有被强制某一种颜色的时候，我们总是取颜色对应点较少的颜色，这样可以尽可能少的操作（这个贪心的正确性显然，因为联通块与联通块之间不影响）。

于是我们使用并查集来维护联通块，维护的信息：

黑色点数目。
白色点数目。
有没有强制性要求是选择黑色还是白色进行操作。

然后就做完了，细节看代码。

code

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>
#define fi first
#define se second
const int N = 3e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;

namespace ARIS0_0{
    int n, k, p[N], s[N], col[N], chs[N];
    int qwq[N][2], cnt[N][2], mst[N][2], res;
    int lsta[N];

    vector <pii> g[N];
    void dfs(int u, int c){
        col[u] = c;
        for (auto [v, w] : g[u]) if (col[v] == -1) dfs(v, (w ? !c : c));
    }
    int find(int x){
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    int get(int x){
        x = find(x);
        if (mst[x][0]) return cnt[x][0];
        if (mst[x][1]) return cnt[x][1];
        return min(cnt[x][0], cnt[x][1]);
    }
    void merge(int u, int v){
        int pu = find(u), pv = find(v);
        if (pu == pv) return ;
        res -= lsta[pu], res -= lsta[pv];

        p[pu] = pv;
        cnt[pv][0] += cnt[pu][0], cnt[pv][1] += cnt[pu][1];
        mst[pv][0] |= mst[pu][0], mst[pv][1] |= mst[pu][1];

        lsta[pv] = get(pv), res += lsta[pv];
    }

    void init(){
    }
    void solve(){
        cin >> n >> k;
        for (int i = 1; i <= n; i ++ ){
            char c; cin >> c;
            s[i] = c - '0';
        }
        for (int i = 1; i <= k; i ++ ){
            int c; cin >> c;
            while (c -- ){
                int pwp; cin >> pwp;
                if (qwq[pwp][0]) qwq[pwp][1] = i;
                else qwq[pwp][0] = i;
            }
        }

        for (int i = 1; i <= n; i ++ )
            if (qwq[i][0] && qwq[i][1] && s[i]) g[qwq[i][0]].push_back({qwq[i][1], 0}), g[qwq[i][1]].push_back({qwq[i][0], 0});
            else if (qwq[i][0] && qwq[i][1]) g[qwq[i][0]].push_back({qwq[i][1], 1}), g[qwq[i][1]].push_back({qwq[i][0], 1});
        for (int i = 1; i <= k; i ++ ) col[i] = -1;
        for (int i = 1; i <= k; i ++ ) if (col[i] == -1) dfs(i, 0);
        for (int i = 1; i <= k; i ++ ) cnt[i][col[i]] = 1, p[i] = i;

        for (int i = 1; i <= n; i ++ ){
            if (!qwq[i][0]){
                cout << res << "\n";
                continue;
            }

            if (qwq[i][0] && qwq[i][1]) merge(qwq[i][0], qwq[i][1]) ;
            else{
                int pwp = qwq[i][0];
                if (s[i] == 0){
                    if (col[pwp] == 0){
                        res -= lsta[find(pwp)];
                        mst[find(pwp)][0] = true;
                        lsta[find(pwp)] = get(find(pwp)), res += lsta[find(pwp)];
                    }
                    else{
                        res -= lsta[find(pwp)];
                        mst[find(pwp)][1] = true;
                        lsta[find(pwp)] = get(find(pwp)), res += lsta[find(pwp)];
                    }
                }
                else{
                    if (col[pwp] == 1){
                        res -= lsta[find(pwp)];
                        mst[find(pwp)][0] = true;
                        lsta[find(pwp)] = get(find(pwp)), res += lsta[find(pwp)];
                    }
                    else{
                        res -= lsta[find(pwp)];
                        mst[find(pwp)][1] = true;
                        lsta[find(pwp)] = get(find(pwp)), res += lsta[find(pwp)];
                    }
                }
            }
            cout << res << "\n";
        }
    }
    void single(){ init(), solve(); }
    void multi(){ init(); int T; cin >> T; while (T -- ) solve(); }
    void idmulti(){ init(); int id, T; cin >> id >> T; while (T -- ) solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::single();
}
// ARIS0_0 - 55