题解：P9869 [NOIP 2023] 三值逻辑

扩展域并查集题解

如果我考场上看见这个题目，肯定不会觉得和并查集有半点关系

约束系统

我们的目标是找到一个初始值方案，使得对于每个，都有。

我们分析依赖关系，推导出，其表达式总是以下三种形式之一：

$常量$

代入，得到了关于初始值的约束方程：

这个推导是具有充分必要性的，也就是说，任何一个合法的初始值方案，必须满足这个由所有条语句推导出的最终约束系统，且任何一个满足这个约束系统的赋值方案，也必然是一个合法的解。

所以，原问题就被转化成了“找到一个初始值方案使满足这个约束系统”。也就是说，只要在满足约束系统的条件下进行关系推导，得到的解就也是合法的，我们期望得到的，就是最小化的那一个。

求最优解

我们用并查集来分析这个约束系统。这个分析过程会把所有变量划分成若干个不相交的连通块。会有很多的操作，让我们从结果开始分析。

什么时候是？

findAnc(x) == findAnc(x + n)，我和我的非在一个逻辑值中，那肯定是；
anc[x] = U，就是在这个集合当中，显然是；

所以我们要维护的就是 anc 关系，并查集是可以的。

但是注意，不能 merge，因为赋值不会影响到祖先，只会影响到自己。那有的同学就要问了：

欸？这个路径压缩是有滞后性的啊，你这么改会有问题啊？

现在我们就来思考，为什么这么做是满足约束要求的。由于我们的约束关系仅仅关于初始值，中途能够合并的点的初始值都是一致的。所以我们可以在过程中绕一圈，T -> F -> T 这样最终回到初始值，就仍然是合法的。这说明，我们让的子树（更新滞后仍然依赖于）和一起走一遭在结果上看是没有问题的。

代码实现

有几个小细节：

初始化正常流程，如果说最后有一些联通块并没有和中任意一个相连，说明他们可以随便赋成某个值，在最小化的过程中是没有贡献的，不考虑即可；

对于操作，时注意用 swap；

findAnc 可能会有环的情况，处理如下：

如果是，那就直接 return 对应值即可；
我们记录 vis，表示当前 dfs 过程中路径上的值：
- vis[x + n] == true，说明 x, x + n 在同一联通块内，是；
- vis[x] = true，说明走回来了，是一个没有确定的祖先的独立于的部分，返回一个非值即可，都行。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 7;

int c, t;

int n, m;
int a, b;
string opt;

int T, F, U;
int anc[MAXN];

bitset<MAXN> vis;

inline void ancInit(int siz) {
    for (int i = 1; i <= siz; ++i)
        anc[i] = i;
    return;
}
inline int match(int x) {
    if(x == T || x == U || x == F)
        return x;
    return (x <= n) ? x + n : x - n;
}
inline int findAnc(int cur) {
    if (cur == F || cur == T || cur == U)
        return cur;
    if (vis[match(cur)])
        return U;
    if (vis[cur])
        return T;
    if (cur != anc[cur]) {
        vis[cur] = true;
        anc[cur] = findAnc(anc[cur]);
        vis[cur] = false;
    }
    return anc[cur];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> c >> t;
    while (t--) {
        int ans = 0;
        cin >> n >> m;
        T = 2 * n + 1;
        F = 2 * n + 2;
        U = 2 * n + 3;
        ancInit(2 * n + 3);
        while (m--) {
            cin >> opt >> a;

            if (opt == "T")
                anc[a] = T, anc[a + n] = F;
            else if (opt == "F")
                anc[a] = F, anc[a + n] = T;
            else if (opt == "U")
                anc[a] = anc[a + n] = U;

            else {
                cin >> b;
                if (opt == "+") {
                    anc[a] = anc[b];
                    anc[a + n] = anc[b + n];
                } else {
                    if (a == b)
                        swap(anc[a], anc[a + n]);
                    else {
                        anc[a + n] = anc[b];
                        anc[a] = anc[b + n];
                    }
                }
            }
        }

        for (int i = 1; i <= n; ++i)
            if (findAnc(i) == U)
                ans++;
        cout << ans << '\n';
    }
    return 0;
}

Do not go gentle into that good night.