洛谷：P5937：Parity Game

题目

P5937：Parity Game

分析

先分析样例：

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

这个01序列长度是10，有5个查询。

• 1-2偶数，表明[1,2]区间有偶数个1，或者说partity=0。
• 3-4奇数，表明parity=1
• 5-6偶数，表明parity=0

（观察：这时都是独立的区间，没有重合，肯定不会有矛盾。）

• 1-6偶数，parity=0。但是，根据前面三个区间（在例题中正好凑成1-6）的奇偶性，“偶数+奇数+偶数”肯定是奇数，和这个断言矛盾！

（问题：我们怎么判断区间有了重合，并且判定“总区间”和各个“子区间”关于奇偶性的说明没有矛盾呢？）

我们先看知道两个相邻区间各自的奇偶性后，如何快速判定联合区间的奇偶性：

• [l, r]区间的奇偶性，显然由[l, k-1]和[k, r]（其中\(k\in [l+1, r-1]\)）的区间奇偶性决定。
• 偶+偶/奇+奇=偶，偶+奇/奇+偶=奇。这让我们联想到了异或运算。

这里我们得到了一个洞见，对我们后续的计算非常重要。对上面的异或操作进行一些变量替换：

\(parity[r]\oplus parity[l-1]=w \Rightarrow parity[r]=parity[l-1]\oplus w\)，其中w是给出的[l, r]区间的奇偶性。这个关系非常重要。

有了这个递推公式，我们可以开始建立各个区间设定的约束（可以认为是一个“等式”关系）。这让我们想到之前我们做过的“P1955：程序自动分析”，一个等式一个等式地合并，如果出现不等式约束出现在一个应该是等式约束的地方，就出现了矛盾。在本题中，就是：区间可以不断合并，并更新该新区间的奇偶性，如果有一个区间的奇偶性判定和我们的计算不想同，这就是那个出问题的判定——程序停止，输出能满足的最大数量的判定。

并查集

并查集的基本操作有两个：查找和合并。

查找

// 查找根节点并返回 {根节点, 当前节点与根节点的奇偶性关系}
pair<int, int> find(int x)
{
    // 如果是新节点，初始化为自己的根
    if (parent.find(x) == parent.end())
    {
        parent[x] = x;
        parity[x] = 0;  // 自己到自己的奇偶性差异为0
        return {x, 0};
    }

    // 如果已经是父节点
    if (parent[x] == x)
    {
        return {x, parity[x]};
    }

    // 路径压缩：递归查找根节点
    auto [root, parent_to_root_parity] = find(parent[x]);

    // 更新当前节点到根的奇偶性差异
    // 原来parity[x]是x到parent[x]的差异
    // parent_to_root_parity是parent[x]到root的差异
    // 异或后得到x到root的差异
    parity[x] ^= parent_to_root_parity;

    // 路径压缩：直接指向根节点
    parent[x] = root;

    return {root, parity[x]};
}

这里有一些扩充：

1. 如果是新的节点parent.find(x) == parent.end()，那么要创建一个节点：它的父节点是自己，到父节点的奇偶性是0。更新相应的父节点表、奇偶性表，并返回{x, 0}。¹
2. 如果是父节点（parent[x]==x）：返回父节点（自己）和对应的奇偶性。
3. 否则，递归寻找、路径压缩找到根节点{root, parent_to_root_parity}。
   1. 更新当前节点的奇偶性：parity[x] ^= parent_to_root_parity;
   2. 路径压缩：parent[x] = root;

可见，总体流程和并查集的查找流程类似，但多了奇偶性更新的操作。

合并

两个节点（区间）合并不光要合并到同一个父节点，还要校验是否奇偶性能得到满足——这个操作是一般并查集合并不需要进行的操作。

// 合并两个集合，约束条件：区间[x+1,y]应该有expected_parity个1
bool union_sets(int x, int y, int expected_parity)
{
    auto [root_x, parity_x] = find(x);  // x到其根的奇偶性差异
    auto [root_y, parity_y] = find(y);  // y到其根的奇偶性差异

    if (root_x == root_y)
    {
        // 如果x和y已经在同一个连通分量中
        // 检查现有的奇偶性关系是否与新约束矛盾
        // parity_x ^ parity_y 就是x和y之间的奇偶性差异
        return (parity_x ^ parity_y) == expected_parity;
    }

    // 合并两个不同的连通分量
    // 让root_y指向root_x
    parent[root_y] = root_x;

    // 计算root_y到root_x的奇偶性差异
    // 使得x和y的奇偶性关系等于expected_parity
    parity[root_y] = parity_x ^ parity_y ^ expected_parity;

    return true;
}

1. 首先找到这两个点的根节点和奇偶性。

auto [root_x, parity_x] = find(x);  // x到其根的奇偶性差异
auto [root_y, parity_y] = find(y);  // y到其根的奇偶性差异

2. 如果已经相等（连通），那么判定parity_x\oplus parity_y是否和期望的奇偶性expected_parity相同，并返回true/false作为合并成功与否的标记，也就是某个判定是否成立的依据。
3. 否则更新根节点：parent[root_y] = root_x;；计算root_y到root_x的奇偶性；返回true，因为不完全连通的两个区间的判定总是能成立的。

答案

思考

说实话，这个题目用并查集（的变体）解决，是很天才的想法！