Codeforces1290 C. Prefix Enlightenment（拆点，并查集）

题意：

给定长度为n的01串,表示n盏灯的初始状态.
给定k个下标集合,保证任意三个集合的交集为空.
一次操作你可以选择一个子集,将子集中所有位置的灯取反.
令m(i)为灯[1,i]全部为1的最小操作次数,要求计算出所有m(i),
保证所有m(i)有解.

数据范围：n,k<=3e5

解法：

因为任意三个子集的交集为空,
意味着每个位置最多只在两个集合中.

因为对同一个集合操作两次等同于没有操作,
因此每个集合最多操作一次.

对于位置x:
1.如果x不出现在任何一个集合中,那么不用管
2.如果x只出现在一个集合中,如果s[i]=0,那么这个集合一定被选,否则一定不选
3.如果x出现在两个集合中,如果s[i]=0,那么两个集合其中一个选一个不被选,
如果s[i]=1,那么两个集合要么全选要么全不选.

如果只需要判断能否让[1,n]全亮,那么可以用2-sat或者普通并查集直接做.
但是这题要计算所有[1,x]的代价,2-sat做不动.

拆点,令i为不选i集合,令i+k为选择i集合,
此外,设置0的代价设为inf,将操作与0连接表示这个操作一定不能做.

从1到i遍历每个位置x:
1.如果x只出现在一个集合中,设这个集合为p,
如果s[i]==0,那么必选,即一定不能不选,将p和0连接
如果s[i]==1,那么必不选,即一定不能选,将p+k和0连接
2.如果x出现在两个集合中,设这两个集合为p和q,
如果s[i]==0,那么一个选一个不选,将p和q+k连接,p+k和q连接.
如果s[i]==1,那么要么全选要么全不选,将p和q连接,p+k和q+k连接.

连接用并查集,同时维护一下并查集集合的操作次数,

连接完之后在p选和p+k中选择一个代价最少的即可.

code：

#include<bits/stdc++.h>
using namespace std;
const int maxm=6e5+5;
vector<int>pos[maxm];
char s[maxm];
int pre[maxm];
int cnt[maxm];
int res[maxm];
int n,k;
int ffind(int x){
    return pre[x]==x?x:pre[x]=ffind(pre[x]);
}
int cal(int x){//选代价最小的
    return min(cnt[ffind(x)],cnt[ffind(x+k)]);
}
void add(int a,int b){
    int x=ffind(a),y=ffind(b);
    if(x!=y){
        pre[x]=y;
        cnt[y]+=cnt[x];
    }
}
signed main(){
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    for(int i=1;i<=k;i++){
        int x;scanf("%d",&x);
        for(int j=1;j<=x;j++){
            int t;scanf("%d",&t);
            pos[t].push_back(i);
        }
    }
    //i表示不选,i+k表示选,额外开一个代价为0的inf,连接表示一定不能做
    for(int i=1;i<=k;i++){
        pre[i]=i,cnt[i]=0;
        pre[i+k]=i+k,cnt[i+k]=1;
    }
    pre[0]=0,cnt[0]=1e9;
    //
    int ans=0;
    for(int i=1;i<=n;i++){
        if(pos[i].size()==1){
            int x=pos[i][0];
            if(s[i]=='0'){//必选
                ans-=cal(x);
                add(x,0);//一定不能不选,连接代价inf
                ans+=cal(x);
            }else{//必不选
                ans-=cal(x);
                add(x+k,0);//一定不能选,连接代价inf
                ans+=cal(x);
            }
        }else if(pos[i].size()==2){//这里要用if-else,不能else,因为存在size=0的情况
            int x=pos[i][0],y=pos[i][1];
            if(s[i]=='0'){
                if(ffind(x)!=ffind(y+k)){
                    ans-=cal(x);
                    ans-=cal(y);
                    //一个选一个不选
                    add(x,y+k);
                    add(x+k,y);
                    //
                    ans+=cal(x);
                }
            }else{
                if(ffind(x)!=ffind(y)){
                    ans-=cal(x);
                    ans-=cal(y);
                    //要么全选要么全不选
                    add(x,y);
                    add(x+k,y+k);
                    //
                    ans+=cal(x);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

---