浅论 T2 带权并查集做法

· · 个人记录

前言

不知道对不对，但是我觉得很对。

约定：T=1, U=0, F=-1=Z

正文

首先我们手玩一下样例。对于每次赋值u:=v，我们画一条从 u 指向 v 的箭头，并在箭头上标 + 或者 -，表示 u 依赖于 v 。然而我们发现，有些似乎图画出来是这样的：

2 1 Z
1 3 1
3 2 1

(我们约定 Z=-1 表示取反，1 表示取同，并且将操作后置)

欸怎么还有环呢？显然依赖不能成环，或者全得置U。如果按照这张图，则仅有全 U 的方案满足题意。

但是不对劲，我们发现时间上有问题。当 3 被 1 赋值时，2 已经被 3 赋值过了，不会再赋一遍，因而这种依赖是不正确的。

很自然地我们想到，像分层图那样给节点标上时间。方便起见，我们令 i 表示 x_i 的初始值，i' 则表示修改过的 x_i。 每次赋值时，将被赋值的变量复制一份，在新的变量上做修改。注意，等号右边的要是 i 位置上最新的数。则原图应该是：

2' 1 Z
1' 3 1
3' 2' 1

这样就对了。

我们再观察图片，会发现有些结构是不必要的。我们压缩长度超过 1 的路径。

题目要求最终变量与初值相等，很自然地我们要合并这两棵树，使得它们的相对关系确定下来。

我们发现这种操作很像并查集：路径压缩和合并都有了。因为边带权，所以我们叫他带权并查集。

带权并查集边的意义并非只能是“类型相同”，还可以是 Z 的“类型取异相等”等。两点间，有连边（无论方向）仅仅表示它们的相对关系确定。

我们于是连一条边3 1 1 使得 3 和 3’ 的值相等。

刚好 1 1' 也同类型。但是若不等呢？如

2' 1 Z
1' 3 Z
3' 1 1

时，又该怎么办？

我们先对齐 3 和 3'，然后发现……

ooops! 1 和它的末值不相等。

该如何避免它呢？

能不能换顺序，即先对齐 1 呢？

不行。因为 “3==3‘” 已经蕴含了 "1=!1'"，我们才得以导出这个结构。本质上，是 "3==3’"和“1==1‘”的矛盾，怎样交换顺序都不行。

我们发现，只能有一种解决方法：令 1==1'==0 。因为 0*Z=0。题目保证了一定有解，所以不会出现 1 已经被强制赋成 TF 的情况。

我们的思路已经清晰：既然冲突数量与顺序无关，我们可以按任意顺序合并集合。若产生冲突，赋值为 0 即可。

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+100;

const int T=3e5+11, F=3e5+12, U=3e5+13;

int fa[maxn],w[maxn],lst[maxn],psz;

int Find(int u) {
    if(fa[u]) {
        int f=fa[u];
        fa[u]=Find(fa[u]);
        w[u]=w[u]*w[f];
        return fa[u];
    }else return u;
}

void Merge(int u,int v,int c) { // u:=v , u->v
    int fu=Find(u),fv=Find(v);
    if(fu==fv) {
        if(w[u]*w[v]!=c&&!(w[u]==0&&w[v]==0)) {
            if(fu>1e5+10) assert(0);
            w[fu]=0;
//          cout<<'!';
        }
        return;
    }
    fa[fu]=fv;
    w[fu]=w[u]*w[v]*c;
    return;
//  Find(fv);
}

inline int acc(int u) {
    return lst[u]=++psz;
}

void init(int n) {
    memset(fa,0,sizeof fa); //???
    fill(w,w+10+n*3,1);
    for(int i=1;i<=n;i++) lst[i]=i;
}

void work() {
    int n,m;
    cin>>n>>m;
    init(n);
    psz=n;
    while(m--) {
        char op;
        int u,v;
        cin>>op;
        if(op=='T') {
            cin>>u;
            Merge(acc(u),T,1);
        }
        else if(op=='U') {
            cin>>u;
            Merge(acc(u),U,1);
        }
        else if(op=='F') {
            cin>>u;
            Merge(acc(u),F,1);
        }
        else if(op=='+') {
            cin>>u>>v;
            Merge(acc(u),lst[v],1);
        }
        else if(op=='-') {
            cin>>u>>v;
            Merge(acc(u),lst[v],-1);
        }
        else assert(false);
    }
    for(int i=1;i<=n;i++) { //n????ê?￡ow[lst[i]]==w[i] 
//      if(w[lst[i]]==w[i]) continue;
//      if(Find(i)==Find(lst[i])) {
//          w[Find(i)]=0;
//      }
        Merge(i,lst[i],1);
    }
    int cnt=0;
    for(int i=1;i<=n;i++) {
        Find(i);
    }
    for(int i=1;i<=n;i++) {
//      cout<<i<<':'<<char(w[i]==-1?'F':w[i]?'T':'U')<<'\n';
        if(w[i]==0) cnt++;
    }
//  cout<<cnt<<'\n';
}

int main() {
//  freopen("tribool.in","r",stdin);
//  freopen("tribool.out","w",stdout);
    int c,Tc;
    cin>>c>>Tc;
    w[U]=0,w[F]=-1,w[T]=1;
    while(Tc--) {
        work();
    }
}

但是你谷 40 pts.