题解：CF1290C Prefix Enlightenment
fish_love_cat · · 题解
被迫营业讲课于是选了 dsu，这是例题。
对于每个位置，考虑包含这个位置的所有集合，进行分讨：
- 如果这个位置是
\texttt0 且有一个集合包含，那么这个集合必选。 - 如果这个位置是
\texttt1 且有一个集合包含，那么这个集合必不选。 - 如果这个位置是
\texttt0 且有两个集合包含，那么这两个集合必有一个被选。 - 如果这个位置是
\texttt1 且有两个集合包含，那么这两个集合是否选择状态一致。
然后这个东西光速发现可以用并查集维护，二倍域维护互斥点就好了。
多维护两个点作为必选和必不选即可，然后对于没有绑定在这两个点上的连通块，显然是互斥的两个连通块对二选一，直接维护一个
前缀问题直接一边扫把边建出来的同时维护答案即可。
哪有紫啊。
#include<bits/stdc++.h>
using namespace std;
vector<int>ve[300005];
int fa[600005];
int siz[600005];
int find(int x){
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int ans;
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
siz[y]+=siz[x];
fa[x]=y;
}
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=k*2+1;i++)
fa[i]=i;
for(int i=1;i<=k;i++)
siz[i]=1;
string s;
cin>>s;
for(int i=1;i<=k;i++){
int m;
cin>>m;
while(m--){
int x;
cin>>x;
ve[x].push_back(i);
}
}
s=" "+s;
for(int i=1;i<=n;i++){
if(ve[i].size()==1){
if(s[i]=='0'){
if(find(0)!=find(ve[i][0]))
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]);
merge(0,ve[i][0]);
merge(k*2+1,k+ve[i][0]);
}else{
if(find(0)!=find(ve[i][0]+k))
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]);
merge(0,ve[i][0]+k);
merge(k*2+1,ve[i][0]);
}
}else if(ve[i].size()==2){
if(s[i]=='0'){
if(find(ve[i][0])==find(0)){
if(find(0)!=find(ve[i][1]+k))
ans-=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
merge(0,ve[i][1]+k);
merge(k*2+1,ve[i][1]);
goto nxt;
}
if(find(ve[i][1])==find(0)){
if(find(0)!=find(ve[i][0]+k))
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]);
merge(0,ve[i][0]+k);
merge(k*2+1,ve[i][0]);
goto nxt;
}
if(find(ve[i][0])==find(2*k+1)){
if(find(0)!=find(ve[i][1]))
ans-=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
merge(0,ve[i][1]);
merge(k*2+1,k+ve[i][1]);
goto nxt;
}
if(find(ve[i][1])==find(2*k+1)){
if(find(0)!=find(ve[i][0]))
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]);
merge(0,ve[i][0]);
merge(k*2+1,k+ve[i][0]);
goto nxt;
}
if(find(ve[i][0])!=find(ve[i][1]+k)){
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]),
ans-=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
merge(ve[i][0],ve[i][1]+k);
merge(ve[i][0]+k,ve[i][1]);
ans+=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
}
}else{
if(find(ve[i][0])==find(2*k+1)){
if(find(0)!=find(ve[i][1]+k))
ans-=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
merge(0,ve[i][1]+k);
merge(k*2+1,ve[i][1]);
goto nxt;
}
if(find(ve[i][1])==find(2*k+1)){
if(find(0)!=find(ve[i][0]+k))
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]);
merge(0,ve[i][0]+k);
merge(k*2+1,ve[i][0]);
goto nxt;
}
if(find(ve[i][0])==find(0)){
if(find(0)!=find(ve[i][1]))
ans-=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
merge(0,ve[i][1]);
merge(k*2+1,k+ve[i][1]);
goto nxt;
}
if(find(ve[i][1])==find(0)){
if(find(0)!=find(ve[i][0]))
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]);
merge(0,ve[i][0]);
merge(k*2+1,k+ve[i][0]);
goto nxt;
}
if(find(ve[i][0])!=find(ve[i][1])){
ans-=min(siz[find(ve[i][0])],siz[find(k+ve[i][0])]),
ans-=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
merge(ve[i][0],ve[i][1]);
merge(ve[i][0]+k,ve[i][1]+k);
ans+=min(siz[find(ve[i][1])],siz[find(k+ve[i][1])]);
}
}
}
nxt:
cout<<ans+siz[find(0)]<<'\n';
}
return 0;
}
// 就算如此，也一定是……
// 有个为这样的她著想的人；有个为这样的她感到生气的人；有个为这样的她而拋下一切，持续奔波的人。
// 根据那个人所说，「我会让你幸福」这句话，是擅自断定对方还没获得幸福。
// 这是猎艳专家、诈欺师和政治家经常使用的话术，让他人依赖自己的一种思想诱导。
// 因此，那个人没有说这种只是用来取悦对方的话语，仅以行动来展现。
// 尽管经常是白忙一场，尽管他的做法也很笨拙。
// 不过，光是这样，她便非常开心。
// 令人实在伤脑筋的是，能够感到开心这一点，没错，就已经是幸福了──