题目链接: Prefix Enlightenment

任何3个集合的交集为空，这就说明了每个灯最多属于两个集合。题目保证能够使灯变亮。显然如果某个灯不被任何集合所控制，我们不用去考虑。我们先假设每个灯被两个集合所控制

如果某个灯原本就是亮的，那么控制该灯的两个集合要么同时翻转，要么都不翻转。如果某个灯原本就是暗的，那么控制改灯的两个集合必定是一个翻转，一个不翻转。
我们把每个集合抽象成一个点，然后每个点有两个属性:翻转和不翻转。然后根据上面讨论的情况，我们在控制该灯的集合的属性上连边。答案显然就是翻转的次数。可以用并查集来完成，这样我们就得到了每个连通块的大小，既是翻转的次数，我们取最小即可。

那么如果某个灯仅属于一个集合呢，这种情况下该集合是否翻转就可以根据灯的初始情况确定了，然后我们把该集合的对立情况连到代价为无穷的点去，保证不取这种情况。

#include<bits/stdc++.h>
#define SZ( v ) ((int)(v).size())
using namespace std;
typedef long long ll;
const int N = 6e5 + 10
const int inf = 0x3f3f3f3f;
vector < int > G[N];
int n , k , fa[N] , cnt[N];
char s[N];

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

int getmin ( int x ) {
    return min ( cnt[get ( x )] , cnt[get ( x + k )] );
}

void merge ( int u , int v ) {
    u = get ( u ) , v = get ( v );
    if ( u != v ) {
        fa[u] = v;
        cnt[v] += cnt[u];
    }
}

int main () {
    scanf ( "%d%d%s" , &n , &k , s + 1 );
    for ( int i = 1 ; i <= k ; ++ i ) {
        int c , x;
        scanf ( "%d" , &c );
        while ( c -- ) {
            scanf ( "%d" , &x );
            G[x].push_back ( i );
        }
        fa[i] = i; // 翻转
        fa[i + k] = i + k;//不翻转
        cnt[i] = 1;
    }
    int ed = 2 * k + 1; // 只有一个点连接到这个点
    fa[ed] = ed;
    cnt[ed] = inf; // 代价设为无穷，保证不取这个点
    int ans = 0;
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( SZ( G[i] ) == 1 ) {
            int u = G[i][0] + k * ( s[i] == '0' ); //不取的情况的编号
            ans -= getmin ( G[i][0] );
            merge ( u , ed );
            ans += getmin ( G[i][0] );
        } else if ( SZ( G[i] ) == 2 ) {
            int u = G[i][0] , v = G[i][1];
            if ( s[i] == '1' ) {
                if ( get ( u ) != get ( v ) ) {
                    ans -= getmin ( u );//每次都要减去之前的
                    ans -= getmin ( v );
                    merge ( u , v );
                    merge ( u + k , v + k );
                    ans += getmin ( u );//再加上新的
                }
            } else {
                if ( get ( u ) != get ( v + k ) ) {
                    ans -= getmin ( u );
                    ans -= getmin ( v );
                    merge ( u + k , v );
                    merge ( u , v + k );
                    ans += getmin ( u );
                }
            }
        }
        printf ( "%d\n" , ans );
    }
    return 0;
}