Codeforces Round #616 (Div. 2) E Prefix Enlightenment(并查集)

题目链接：https://codeforces.com/contest/1291/problem/E

 

题目大意：

  有k个集合，每三个集合交集为空，有一堆灯泡，初始的开关由0和1表示，0表示关，1表示开。每次可以选择一个集合中的灯泡切换状态，输出i位1~n,1~i全亮的最少操作次数

 

题目思路：

  在大佬眼里好像很简单，但是我感觉很难啊。。
  首先由于每三个集合交集为空，所以每个灯泡最多由两个集合控制。假设现在一个灯泡由两个集合控制，那么如果这个灯泡当前是亮的，那么一定是控制他的两个集合都用了或者都没用。如果当前是灭的，想让他亮起来，那么一定是两个集合中一个用了一个没用。而对于只有一个集合控制的情况，如果当前是灭的，那么这个集合必须用，如果是暗的，那么这个集合必须不用。
  使用并查集，1~m表示的是用，m+1~2m表示的是不用，$num[x]$表示x所在集合需要多少次操作。
  先说只有一个集合控制的情况。如果一个情况不能用，就让他的父亲为0，就是并查集中的$pre[x]=0$，所以当面对0的时候，就说明必须用，也就是不用的情况需要废掉，那么就是$pre[Find(x+m)]=0$要注意的是，如果这个情况不能用的话，是这一整个家族都不能用了，所以要找出他的祖宗，让祖宗废掉，那整个家族就废掉了。
  然后说有两个集合控制的情况。首先先要去掉这两个集合的贡献，防止后面重复加这一部分贡献，然后对这两个集合进行合并，最后再加上合并后的贡献。计算贡献的话，就是看这个集合用和不用的家族需要多少钱，所以先算出他和他的另一半(如果当前$<m$就$+m$，否则$-m$)然后用Find找出自己和另一半的各自家族的老大，然后判断有没有是被废掉的，即老大为0，有的话返回没被废掉的家族的值，没有的话返回两个家族中小的那个。因为这俩家族都能满足要求。合并的话，如果是0的情况下需要反转，所以x和y+m合并，x+m和y合并，而对于1的情况不需要，所以是x和y合并，x+m和y+m合并。合并完大家就是一家人了，所以随便挑个人当代言人，这里选x，直接算x的贡献就行。之前想错了，感觉x和y合并了，所以算贡献应该算x家族的贡献，我就先找到了x的祖先，然后加贡献的时候，加的是它祖先的贡献没过样例。这里的原因是我们需要从x和x的另一半中选一个厉害的，在算贡献的过程中，我们会去找x的祖先，所以提前找是画蛇添足，没必要，而这样的坏处则是，x的另一半明明是通过x得到的，如果先找了x的祖先，再去找x的祖先的另一半，那就导致另一个家族找错了，明明要找的是x的另一半，却找了x的祖先的另一半，导致了错误。确实找x的本身的数量要找他祖先，但是这一部分在$cal$写了我给忘了。。
  感觉再遇到一次这类题，我还是会给到底找不找祖先，到底要不要去除贡献，去谁的，加谁的整的云里雾里，这题感觉现在虽然每个地方都能说明白，但总觉得隔着一个啥东西，希望通过以后的学习能更加深刻地理解并查集吧！

 

以下是代码：

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MAXN=1e6+5;
const int MOD=1e9+7;
int pre[MAXN],l[MAXN][2],num[MAXN];
int n,m,c,x;
int Find(int x){
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}
void Merge(int x,int y){
    int xx=Find(x);
    int yy=Find(y);
    if(xx<yy)swap(xx,yy);
    pre[xx]=yy;
    if(!yy)return;
    num[yy]+=num[xx];
}
int cal(int x){
    int y;
    if(x>m)y=x-m;
    else y=x+m;
    int xx=Find(x);
    int yy=Find(y);
    if(!xx||!yy)return num[xx+yy];
    return min(num[xx],num[yy]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    while(cin>>n>>m>>s){
        memset(l,0,sizeof(l));
        memset(num,0,sizeof(num));
        rep(i,1,m){
            cin>>c;
            rep(j,1,c){
                cin>>x;
                if(!l[x][0])l[x][0]=i;
                else l[x][1]=i;
            }
            pre[i]=i,pre[i+m]=i+m;
            num[i]=1;
        }
        int ans=0;
        rep(i,0,n-1){
            int x=l[i+1][0],y=l[i+1][1];
            if(!y){
                ans-=cal(x);
                if(s[i]=='0'){
                    pre[Find(x+m)]=0;
                }
                else{
                    pre[Find(x)]=0;
                }
                ans+=cal(x);
            }
            else{
                if(s[i]=='0'){
                    if(Find(x)!=Find(y+m)){
                        ans-=cal(x);
                        ans-=cal(y);
                        Merge(x,y+m);
                        Merge(y,x+m);
                        //int p=Find(x);
                        ans+=cal(x);
                    }
                }
                else{
                    if(Find(x)!=Find(y)){
                        ans-=cal(x);
                        ans-=cal(y);
                        Merge(x,y);
                        Merge(y+m,x+m);
                        //int p=Find(x);
                        ans+=cal(x);
                    }
                }
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}