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

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

---

题意

给出一个长度为$n$的$01$串$S$表示初始状态。
给出$k$个集合，集合内的元素是$1$~$n$，表示$S$的下标。保证任意三个不同集合的交为空集。
每次操作可以选择一个集合，使得集合内所有下标的状态$S$翻转。
询问要使得状态$S$前$i$位都为$1$所需要的最少操作次数。
题目保证必有解。
$(1\le n,k\le 3\times 10^5).$

---

题解

首先看到这个很奇怪的条件：任意三个不同集合的交为空。换句话说任何一个位置最多被两个操作所覆盖。然后稍微分类讨论一下：

• 如果一个位置没有操作覆盖：因为题目保证有解，所以可以直接不考虑它。
• 如果一个位置只有一个操作覆盖：
  • 当前位是$1$，这个操作一定不会选。
  • 当前位是$0$，如果需要把这一位变成$1$，这个操作必选。
• 如果一个位置有两个操作覆盖：
  • 当前位是$1$，这两个操作要么都选，要么都不选。
  • 当前位是$0$，这两个操作必选一个，且只选一个。

这样就发现操作与操作之间是存在限制关系，然后就考虑拆点建并查集。对所有操作拆两个点：一个点$x$代表选，代价为$1$；另一个点$x+k$代表不选，代价为$0$。

因为有些操作是必选和不选的，我开始是想分类讨论在并查集里维护的，写不下去了。直接另外开一对点，选了的代价为无穷大，不选的代价为$0$。必选就把$x$连向$0$，$x+k$连向无穷大；不选就把$x$连向无穷大，$x+k$连向$0$。因为$x$与$x+k$所在的并查集，代价较小的那个一定会对答案产生贡献。

题目要求对每个前缀都要求答案，只要把当前位两个操作的贡献都删去，等并查集啥的都维护好了，再加上贡献就行了。

---

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int n,k;
char s[N];
int fa[N],val[N];
int fd(int x){return x==fa[x]?x:fa[x]=fd(fa[x]);}
int op[N][2];
void uni(int u,int v){
    int fu=fd(u),fv=fd(v);
    if(fu==fv) return;
    val[fv]+=val[fu];
    fa[fu]=fv;
}
int main(){
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    for(int i=1,m;i<=k;i++){
        scanf("%d",&m);
        for(int j=1,x;j<=m;j++){
            scanf("%d",&x);
            if(op[x][0]) op[x][1]=i;
            else op[x][0]=i;
        }
    }
    k++;
    for(int i=0;i<=2*k;i++) fa[i]=i,val[i]=(i<=k);
    val[0]=N;val[k]=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        int u=op[i][0],v=op[i][1];
        if(!u){printf("%d\n",ans);continue;}
        if(s[i]=='0'&&fd(u)!=fd(v+k)){
            ans-=min(val[fd(u)],val[fd(u+k)]);
            ans-=min(val[fd(v)],val[fd(v+k)]);
            uni(u,v+k);
            uni(v,u+k);
            ans+=min(val[fd(u)],val[fd(u+k)]);
        }
        if(s[i]=='1'&&fd(u)!=fd(v)){
            ans-=min(val[fd(u)],val[fd(u+k)]);
            ans-=min(val[fd(v)],val[fd(v+k)]);
            uni(u,v);
            uni(u+k,v+k);
            ans+=min(val[fd(u)],val[fd(u+k)]);
        }
        printf("%d\n",ans);
    }
}