「Parity Game」奇偶游戏

形式化题目

01 序列 $S$ ， $M$ 个回答：「 $S[l..r]$ 中 1 的个数为奇/偶」。回答按顺序给出，求第一个与前面所有回答自相矛盾的回答编号（全部一致输出 OK 类答案，按题目约定输出）。

正解

思路

1. 前缀异或化

令 $P_i = S[1..i]$ 的异或和（ $P_0 = 0$ ）。则

S[l..r] \text{ 中 1 的个数为奇} \iff P_{l-1} \oplus P_r = 1

每个回答变成一条异或约束： $P_{l-1} \oplus P_r = \text{parity}$ 。

2. 带权并查集

维护 $P$ 之间的异或关系：kind[x] = $x$ 到所在集合根的异或值。

查询： $x, y$ 同根时， $P_x \oplus P_y = \text{kind}[x] \oplus \text{kind}[y]$ ；与新约束矛盾则该回答撒谎。
合并：异根时按 $kind[y] \oplus kind[x] = parity$ 挂接，按秩合并控制树高，路径压缩时用「从根往回」顺序修正 kind。

3. 找第一个矛盾 + 离散化

端点离散化（ $M$ 个回答至多 $2M$ 个不同端点）；
回答矛盾具有单调性：前 $k$ 个回答若已矛盾，之后必然持续矛盾。按回答顺序在线增量维护也可直接得到第一个矛盾（本题即按序加入、遇矛盾即报）；若需要「前 k 个是否矛盾」则二分 + 可撤销并查集。

本实现按回答顺序在线加入，第一个使约束冲突的回答即为答案。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 17:28
# update_at: 2026-10-01 17:28

import sys

ODD = 1  # 回答编码：1 = 奇数个 1（前缀异或不同），0 = 偶数个 1（前缀异或相同）


def find(kind: dict[int, int], parent: dict[int, int], x: int) -> int:
    """路径压缩地返回 x 的根，并把 kind[x] 修正为 x 到根的异或。"""
    path: list[int] = []
    while parent[x] != x:
        path.append(x)
        x = parent[x]
    root, acc = x, 0
    for node in reversed(path):  # 从靠近根的一端往回走，先修正父亲再修正儿子
        acc ^= kind[node]
        kind[node] = acc  # node 到根的异或
        parent[node] = root  # 顺带把这条路径压平
    return root


def add_constraint(
    kind: dict[int, int],
    parent: dict[int, int],
    size: dict[int, int],
    x: int,
    y: int,
    parity: int,
) -> bool:
    """加入约束 `kind[y] ^ kind[x] = parity`；与已有约束矛盾时返回 False。"""
    rx, ry = find(kind, parent, x), find(kind, parent, y)
    if rx == ry:
        return kind[x] ^ kind[y] == parity  # 同集合：已有约束的推论必须与本次回答一致
    if size[rx] < size[ry]:  # 小树挂到大树，控制树高
        rx, ry, x, y = ry, rx, y, x
    parent[ry] = rx
    kind[ry] = kind[x] ^ kind[y] ^ parity  # 使 y 到 x 的新路径异或恰好是 parity
    size[rx] += size[ry]
    return True


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    length = int(next(it))  # 序列长度（只界定前缀下标范围，判定过程不用它）
    m = int(next(it))       # 回答数量

    kind: dict[int, int] = {}  # kind[v] = 点 v 到其父亲的异或（根恒为 0）
    parent: dict[int, int] = {}
    size: dict[int, int] = {}

    answer = m  # 所有回答都不矛盾时，能撑过的回答数就是 M
    for i in range(m):
        left = next(it)
        right = next(it)
        word = next(it)
        x, y = int(left) - 1, int(right)  # 前缀坐标：S[l..r] 对应点 l-1 与点 r
        for v in (x, y):  # 坐标只有 2M 个且 N 可达 1e9，按需开点
            parent.setdefault(v, v)
            kind.setdefault(v, 0)
            size.setdefault(v, 1)
        parity = ODD if word == b"odd" else 0
        if not add_constraint(kind, parent, size, x, y, parity):
            answer = i  # 第 i 条回答与前面矛盾，说明序列能同时满足的是前 i 条
            break

    print(answer)  # length 只界定前缀下标范围，判定过程与它无关


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 18:57
 * update_at: 2026-10-06 18:57
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;

// 带权并查集：kind[x] = x 到其所在集合根的异或值
const int MAXM = 20005; // M <= 10000，每个回答两个端点，至多 2M 个坐标

int fa[MAXM];          // 并查集父亲
int kind[MAXM];        // kind[x] = 前缀异或值 P[x] ^ P[fa[x]]（到父亲的异或），find 后修正为到根
int rnk[MAXM];         // 按秩合并用的树高

// 离散化后的坐标点
int xs[MAXM];          // 所有出现过的端点（l-1 与 r）
ll tot;                // 离散化后点的个数

struct Query {
    ll l, r;           // 存的是前缀坐标 l-1 与 r（原始值，未离散化）
    int parity;        // 0 = 偶数个 1，1 = 奇数个 1
};
Query qs[MAXM];        // qs[i] = 第 i 个回答（下标从 1 开始）

int m;                 // 回答数量

// 朴素 find：从 x 一路向上，同时累加异或值，再统一路径压缩
// 注意必须「先靠根的先修正」：递归返回时自根向叶累加 kind
int find_root(int x) {
    if (fa[x] == x) return x;
    int root = find_root(fa[x]);
    kind[x] ^= kind[fa[x]]; // 父亲的 kind 此时已是「父亲到根」的异或
    fa[x] = root;
    return root;
}

// 加入约束 kind[y] ^ kind[x] = parity；与已有约束矛盾返回 false
bool add_constraint(int x, int y, int parity) {
    int rx = find_root(x), ry = find_root(y);
    if (rx == ry) {
        // 同一集合：P[x] ^ P[y] 应等于 kind[x] ^ kind[y]
        return (kind[x] ^ kind[y]) == parity;
    }
    // 异根：按秩合并，把矮的挂到高的下面
    if (rnk[rx] < rnk[ry]) {
        int t = rx; rx = ry; ry = t;
        t = x; x = y; y = t;
    }
    fa[ry] = rx;
    kind[ry] = kind[x] ^ kind[y] ^ parity; // 保证 y 到 x 的路径异或恰为 parity
    if (rnk[rx] == rnk[ry]) rnk[rx]++;
    return true;
}

// 离散化：返回原始值 v 在 xs 中的下标（下标从 1 开始）
int id(ll v) {
    int low = 1, high = tot;
    while (low < high) {
        int mid = (low + high) / 2;
        if (xs[mid] < v) low = mid + 1;
        else high = mid;
    }
    return low;
}

int main() {
    ll n;
    scanf("%lld %d", &n, &m); // n 只界定前缀下标范围，判定过程与它无关
    for (int i = 1; i <= m; i++) {
        char word[10];
        scanf("%lld %lld %s", &qs[i].l, &qs[i].r, word);
        // S[l..r] 的 1 的个数奇偶 = P[l-1] ^ P[r]，前缀坐标取 l-1 与 r
        qs[i].l = qs[i].l - 1;
        qs[i].parity = (word[0] == 'o') ? 1 : 0;
    }

    // 收集所有端点做离散化（N <= 1e9，坐标不能直接开数组）
    tot = 0;
    for (int i = 1; i <= m; i++) {
        xs[++tot] = qs[i].l;
        xs[++tot] = qs[i].r;
    }
    std::sort(xs + 1, xs + tot + 1);
    tot = std::unique(xs + 1, xs + tot + 1) - (xs + 1);

    // 并查集初始化：每个离散化坐标是一个独立点
    for (int i = 1; i <= tot; i++) {
        fa[i] = i;
        kind[i] = 0;
        rnk[i] = 0;
    }

    // 按回答顺序逐条加入，第一条与前面矛盾的回答就是答案
    for (int i = 1; i <= m; i++) {
        int x = id(qs[i].l), y = id(qs[i].r);
        if (!add_constraint(x, y, qs[i].parity)) {
            printf("%d\n", i - 1); // 前 i-1 条回答可以满足，第 i 条矛盾
            return 0;
        }
    }
    printf("%d\n", m); // 所有回答都自洽
    return 0;
}

复杂度

时间复杂度： $O(M \alpha(M) + M \log M)$ （离散化排序）。
空间复杂度： $O(M)$ 。

总结

「奇偶个数」类问题的标准变形：前缀异或 → 异或约束 → 带权并查集。
带权并查集的关键：kind 存「到根的异或」，路径压缩时按靠近根的顺序累加修正。
回答矛盾具有单调性，配合离散化与可撤销并查集可以二分出精确的「第一个谎言」。

「Parity Game」 奇偶游戏

目录

形式化题目

正解

思路

1. 前缀异或化

2. 带权并查集

3. 找第一个矛盾 + 离散化

代码

复杂度

总结

「Parity Game」奇偶游戏