Codeforces Round #616 (Div. 2) - E . Prefix Enlightenment (1291E)

题意：灯泡开关问题，n 个灯泡，给定初始状态，0 为关，1 为开，现在有 k 个操作集合，每个集合内可以改变一些灯泡的状态，任意三个集合交集为空，求所有的 i (1<=i<=n) ，使得前 i 个灯泡状态全为开需要的最少操作集合是多少（后面的不用管）；

 

分析：任意三个集合交集为空，即一个灯泡的开关最多只存在于两个集合里，假设控制灯泡 i 的两个集合为 k1,k2；若初始状态：

①灯泡 i 开 ，则 k1,k2 要么同时选择，要么都不选；

②灯泡 i 关 ，则 k1,k2 只能选一个；

如上，则很多集合之间的选择是有关联性的，所以我们可以给这些关联点缩点，即把两个相关联的集合缩成一个集合，那 k 个集合就渐渐成了 m 个连通块 (m<=k)，每个连通块要么全选，要么全不选；

缩点操作可以用并查集做，若两个集合有关联，就把它们合并，选一个集合的代价是 1， 那么可以用带权并查集；如果灯泡只由一个集合控制的点就特判就行了；

 

代码：

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
const int N = 6E5+10;

int n,k,l[N][2];
int fa[N],sc[N];  
string s;

int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
int cal(int x){
	int y= x<=k? x+k:x-k;
	int xx=find(x),yy=find(y);
	if(xx==0||yy==0) return sc[xx+yy];
	return min(sc[xx],sc[yy]);
} 
void merge(int x,int y){
	int xx=find(x),yy=find(y);
	if(xx==0) fa[yy]=xx,sc[xx]+=sc[yy];
	else fa[xx]=yy,sc[yy]+=sc[xx]; 
} 

int main()
{
	scanf("%d%d",&n,&k);
    cin>>s;
    for(int i=1;i<=k;i++) fa[i]=i,fa[i+k]=i+k,sc[i+k]=1;
    //并查集的初始化，fa[i+k]代表用i这个集合，sc[i+k]表示用这个集合的代价
    for(int i=1,c;i<=k;i++){
        scanf("%d",&c);
        for(int j=0,v;j<c;j++){
        	scanf("%d",&v);
        	if(l[v][0]) l[v][1]=i;   //l[v][0],l[v][1]表示控制灯泡v的两个集合
        	else l[v][0]=i;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(l[i][1]==0){
			int x=l[i][0];
			if(x){                   //如果只有一个集合控制开关 i 
			    ans-=cal(x);         //先减去集合 x 的连通块的代价
			    if(s[i-1]=='1') fa[find(x+k)]=0;
			    else fa[find(x)]=0;
			    ans+=cal(x);         //确定好集合 x 选不选，缩点之后再加回来
			}
		}
		else{
			int x=l[i][0],y=l[i][1];
			if(s[i-1]=='1'){
				if(find(x)!=find(y)){  //因为灯泡 i 初始状态是开，所以若两个集合已经有联系了(属于一个连通块)，就不用管了，若没有，则需要进一步操作

					ans-=cal(x);       //分别减去x和y的连通块
				    ans-=cal(y);
				    merge(x,y);        //缩点，同时选或同时不选
				    merge(x+k,y+k);
				    ans+=cal(x);       //加回去
			    }
			}
			else{
				if(find(x)!=find(y+k)){   //同上
				    ans-=cal(x);
				    ans-=cal(y);
				    merge(x,y+k);
				    merge(x+k,y);
				    ans+=cal(x); 	
				}
			}
		}
		cout<<ans<<'\n';
	}
	
}