P9869 [NOIP2023] 三值逻辑题解

题目链接
这里使用扩展域并查集实现。
既然来看题解了，相信你已经读懂题了，这里不再赘述题意，直接进入主题。
没读懂可以去看其他题解
思路：

为何用并查集

考虑什么情况下一个变量的最终值为 \(U\)？当且仅当一个变量 \(x=-x\) 或 \(x\) 与 \(-x\) 中有一个等于 \(U\) 那么这个变量就是 \(U\)。
关于维护 \(x\)、\(-x\) 以及与 \(U\) 之间的关系，可以想到用扩展域并查集。正负对应 \([1,n]\) 与 \([n+1,2n]\)，\(T\)、\(F\)、\(U\) 分别对应 \(2n+1\)、\(2n+2\) 与 \(2n+3\)。
维护赋值操作

此题的特殊点在于初始值都不知道，无法直接进行赋值操作。所以考虑如何维护。
我们记每个变量的最终值为 \(ed_i\)。
一个错误的思路就是用 \(ed_x\) 表示当前 \(x\) 赋到的值的下标 \(y\)。这样子做的问题在于 \(ed_y\) 在不停改变，如果 \(ed_y\) 又发生了改变，那么 \(ed_x\) 相应的也会被改变。
但是，如果每个变量的初始值已知，那么就可以直接进行赋值，且不会受到后续变量改变的干扰。
所以，我们假设初始值已知（令初始时 \(ed_i=i\)），然后直接进行赋值操作。最终可以得到 \(ed_i\) 等于某个值 \(x\)。由于变量的初始值等于它的最终值，所以 \(i\) 和 \(x\) 属于同一集合，\(-i\) 与 \(-x\) 属于同一集合，这样就能用并查集维护了。
（记得更新完后还要更新相应负值）
统计答案

将 \(x=-x\) 或 \(x\) 与 \(-x\) 中有一个等于 \(U\) 的与 \(U\) 合并，最后判断哪些 \(i\) 与 \(U\) 在同一集合即可。
实现：

赋值操作

[code]    for(int i=1;i

东西不错很实用谢谢分享