[CEOI 1999] Parity Game

题意

Alice 写下一个长度为 $n$ 的 $01$ 序列。她依次询问区间 $[l,r]$ 中有奇数个还是偶数个 $1$ ，Bob 给出 $m$ 个回答。我们要找出第一个必然错误的回答：

前 $x$ 个回答应该还能由某个 $01$ 序列同时满足；
前 $x+1$ 个回答已经不存在任何满足它们的序列。

输出这个 $x$ 。如果所有回答都没有矛盾，就输出 $m$ 。

输入中的 odd 表示奇数，even 表示偶数。题目中 $n$ 最大为 $10^9$ ，但回答数 $m\le 5000$ ，所以不能真的创建长度为 $n$ 的数组。

样例中前 3 条回答可以同时成立，第 4 条回答与它们推出的关系相反，因此答案是 $3$ 。

思路

1. 先看最直接的暴力

如果 $n$ 很小，可以枚举所有 $01$ 序列。每生成一个序列，就依次检查回答，记录它最多能满足前多少条回答；所有序列中的最大值就是答案。

这段暴力代码故意保持“每一位做 0/1 选择”的形状。它不适合本题的大数据，却能先把题目的逻辑说清楚：我们要判断的是“是否存在一个序列满足回答前缀”，而不是找出某一个固定序列。

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/**
 * 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-07-16 17:48
 * update_at: 2026-07-21 09:53
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举所有可能的原始序列。
#include <bits/stdc++.h>
using namespace std;

struct Query {
    int left;
    int right;
    int parity;
};

const int MAXN = 12;
const int MAXM = 20;

int n, m;
int choose_value[MAXN];
Query queries[MAXM];
int answer;

void check_sequence() {
    int prefix[MAXN + 1] = {};
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] ^ choose_value[i];
    }

    int satisfied = 0;
    for (int i = 0; i < m; i++) {
        int actual = prefix[queries[i].right] ^ prefix[queries[i].left - 1];
        if (actual != queries[i].parity) {
            break;
        }
        satisfied++;
    }
    answer = max(answer, satisfied);
}

void dfs(int position) {
    if (position == n + 1) {
        check_sequence();
        return;
    }

    choose_value[position] = 0;
    dfs(position + 1);
    choose_value[position] = 1;
    dfs(position + 1);
}

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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        string word;
        cin >> queries[i].left >> queries[i].right >> word;
        queries[i].parity = (word == "odd");
    }

    answer = 0;
    dfs(1);
    cout << answer << '\n';
    return 0;
}

暴力的瓶颈是 $2^n$ 个序列。接下来要做的关键变化是：不再关心每一位具体是 $0$ 还是 $1$ ，只记录前缀中 $1$ 的奇偶性。

2. 把区间奇偶改写成前缀异或

定义

s[i]=a_1\oplus a_2\oplus\cdots\oplus a_i, \qquad s[0]=0。

因为异或两次相同的部分会抵消，所以区间 $[l,r]$ 中 $1$ 的奇偶性为

s[r]\oplus s[l-1].

于是每条回答都可以变成两个前缀点之间的关系。令 $x=l-1$ ， $y=r$ ：

Bob 的回答	对前缀点的约束
`even`	$s[x]\oplus s[y]=0$ ，也就是 $s[x]=s[y]$
`odd`	$s[x]\oplus s[y]=1$ ，也就是 $s[x]\ne s[y]$

例如样例前 3 条回答变成：

text

1
2
31 2 even  -> s[0] XOR s[2] = 0
3 4 odd   -> s[2] XOR s[4] = 1
5 6 even  -> s[4] XOR s[6] = 0

沿着这三条约束可以推出 $s[0]\oplus s[6]=1$ ，而第 4 条回答要求 $s[0]\oplus s[6]=0$ ，所以它矛盾。

注意： $n$ 虽然很大，但每条回答只会用到两个前缀位置 $l-1$ 和 $r$ 。最多只有 $2m$ 个位置真正出现，可以先离散化这些位置。下面记离散化后的位置个数为 $K$ 。

3. 解法一：带权并查集

3.1 用样例走一遍并查集建模

在深入公式之前，先用样例数据感受一下：并查集如何一步步建树、如何检查矛盾。

回忆第 2 节，样例前 4 条回答转化为前缀异或约束（ $w=0$ 表示 even， $w=1$ 表示 odd）：

序号	原始回答	前缀约束	$w$
①	`1 2 even`	$s[0]\oplus s[2]=0$	$0$
②	`3 4 odd`	$s[2]\oplus s[4]=1$	$1$
③	`5 6 even`	$s[4]\oplus s[6]=0$	$0$
④	`1 6 even`	$s[0]\oplus s[6]=0$	$0$

下面边画出并查集树的形态，边说明每一步做了什么。树上每个箭头 x —[v]→ y 表示 $\text{parent}[x]=y$ ，且 $v = s[x]\oplus s[y]$ 。

处理 ①： $s[0]\oplus s[2]=0$

$s[0]$ 和 $s[2]$ 分属两棵树，合并。取 $s[0]$ 为根， $s[2]$ 指向 $s[0]$ ，边权取 $w=0$ ：

graph BT
    s2 --"0"--> s0

沿箭头： $s[2]$ 到根的异或为 $0$ ，即 $s[2]=s[0]\oplus 0=s[0]$ 。

处理 ②： $s[2]\oplus s[4]=1$

$s[2]$ 的根是 $s[0]$ （ $s[2]\to s[0]$ 位移为 $0$ ）， $s[4]$ 是独立的。现在要把 $s[4]$ 的根也接到 $s[0]$ 下，需要算出 $s[4]$ 到 $s[0]$ 的边权。

沿着路径 $s[0]\to s[2]\to s[4]$ ： $s[0]$ 到 $s[4]$ 的位移 $=0\oplus 1=1$ 。

graph BT
    s2 --"0"--> s0
    s4 --"1"--> s0

验证： $s[2]$ 到 $s[4]$ = $(s[2]\to s[0]$ 的 $0) \oplus (s[0]\to s[4]$ 的 $1)=1$ ，满足 ②。

处理 ③： $s[4]\oplus s[6]=0$

$s[4]$ 到 $s[0]$ 的位移是 $1$ ， $s[4]$ 到 $s[6]$ 的位移 $w=0$ 。沿 $s[0]\to s[4]\to s[6]$ ： $s[0]$ 到 $s[6]$ 的位移 $=1\oplus 0=1$ 。

graph BT
    s2 --"0"--> s0
    s4 --"1"--> s0
    s6 --"1"--> s0

此时可以通过树算出任意两点间的关系。例如 $s[0]\oplus s[6]=1$ ， $s[2]\oplus s[6]=0\oplus 1=1$ 。

处理 ④： $s[0]\oplus s[6]=0$ （发生矛盾）

$s[0]$ 和 $s[6]$ 已经在同一棵树中，走到各自根的位移分别是 $0$ 和 $1$ ，所以现有关系 $=0\oplus 1=1$ 。但 ④ 要求的 $w=0$ ， $1\neq 0$ ，矛盾！

graph BT
    s2 --"0"--> s0
    s4 --"1"--> s0
    s6 --"1"--> s0
    style s0 fill:#e6f3ff,stroke:#333
    style s6 fill:#ffe6e6,stroke:#333

上图中 $s[0]$ （蓝底）和 $s[6]$ （红底）是当前回答涉及的两个点。怎么用公式发现矛盾？分三步：

找到各自到根的位移： $s[0]$ 自身就是根，位移 $\textit{xor}[0]=0$ ； $s[6]$ 沿箭头走到 $s[0]$ ，位移 $\textit{xor}[6]=1$ 。
算出两点间的现有关系： $\textit{xor}[0]\oplus\textit{xor}[6]=0\oplus 1=1$ 。这个 $1$ 就是当前 $s[0]\oplus s[6]$ 的值。
跟回答比较：回答要求的 $w=0$ ， $1\neq 0$ ，矛盾！

为什么 $\textit{xor}[x]\oplus\textit{xor}[y]$ 等于 $s[x]\oplus s[y]$ ？因为两人都以同一个根为参照—— $s[x]=s[root]\oplus\textit{xor}[x]$ ， $s[y]=s[root]\oplus\textit{xor}[y]$ ，异或后 $s[root]$ 抵消，剩下的正好是 $\textit{xor}[x]\oplus\textit{xor}[y]$ 。

至此输出 $3$ ，表示前 $3$ 条回答可以成立。

这段手动过程包含了带权并查集的全部操作：合并时沿路径推导新边权（ $\textit{xor}[\textit{ry}] = \textit{xor}[x]\oplus\textit{xor}[y]\oplus w$ ），以及同集合时用异或检查约束。接下来各节把这个过程写成通用公式。

3.2 普通并查集还缺什么

普通并查集只能回答“两个点是否连通”。本题还需要知道连通点之间是相同还是相反，因此给每个节点增加一个异或权值。

下面把前缀值 $s[x]$ 简写成 value[x]，所以 value[x] 和 s[x] 是同一个东西。

并查集维护下面这个不变量：

text

1xor_to_parent[x] = value[x] XOR value[parent[x]]

路径压缩后，xor_to_parent[x] 就表示 value[x] XOR value[root[x]]。

权值的含义只有两种：

权值	含义
`0`	两个前缀值相同
`1`	两个前缀值相反

可以把权值看成 parent[x] 到 x 的位移向量——0 表示"没动"，1 表示"翻了一下"。于是树上任意两点的值差，就是路径上位移向量的逐段异或。

3.3 路径压缩为什么要异或

假设 $x$ 的父亲是 $p$ ，而 $p$ 的根是 $r$ ：

value[x]\oplus value[r] =(value[x]\oplus value[p])\oplus(value[p]\oplus value[r]).

所以递归 find 回来后，只需要执行：

text

1xor_to_parent[x] ^= xor_to_parent[old_parent]

原来的两段关系就被折叠成一段 $x\to r$ 的关系。这本质上就是向量的三角形法则：x→r 的位移 = x→p 的位移 + p→r 的位移。

3.4 合并公式怎么推出来

当前回答要求

value[x]\oplus value[y]=w,

其中 w=0 表示 even，w=1 表示 odd。

设 rx=find(x)，ry=find(y)。路径压缩后：

\begin{aligned} value[x]&=value[rx]\oplus xor[x],\\ value[y]&=value[ry]\oplus xor[y]. \end{aligned}

代入约束并整理：

value[rx]\oplus value[ry] =xor[x]\oplus xor[y]\oplus w.

因此令

text

1relation = xor[x] XOR xor[y] XOR w

如果把 ry 挂到 rx，就设置：

text

1xor[ry] = relation

这正好记录了 value[ry] XOR value[rx]。从向量视角看，这个公式无非是沿着路径 rx→x→y→ry 把三段位移向量加起来。

代码会按集合大小决定到底挂哪一棵树；因为异或满足交换律，交换两个根后这个 relation 数值仍然正确。

3.5 用“关系向量”理解合并

上面的公式也可以用向量首尾相接来记忆。这里的“向量”不是平面几何向量，而是前缀值之间的相对位移；本题中位移只有 0 和 1，向量相加就是 XOR。

把 d[x] 看成从父节点指向 x 的关系向量：

text

1d[x] = value[x] XOR value[parent[x]]

路径压缩就是把两段向量接成一段：

text

1
2
3root ---- d[old_parent] ----> old_parent ---- d[x] ----> x

root ---------------------- d[old_parent] XOR d[x] ----------------------> x

合并时，设 rx=find(x)、ry=find(y)，并且当前回答给出 x -> y 的关系 w：

text

1rx ---- xor[x] ----> x ---- w ----> y ---- xor[y] ----> ry

这里把 y -> ry 也写成 xor[y]，是因为 XOR 中正向和反向的关系数值相同。

因此两个根之间的关系就是：

text

1rx -> ry = xor[x] XOR w XOR xor[y]

这正是代码中的：

text

1relation = xor[x] XOR xor[y] XOR w

如果用普通加法向量表达，公式会写成 dx + w - dy。但在 XOR 关系中，每个值都是自己的逆元，因为 a XOR a = 0，所以“减去 dy”和“再 XOR 一次 dy”是同一件事。这也解释了为什么本题的合并公式看起来特别简洁。

更一般地说，带权并查集可以看成维护每个节点相对于根的“局部坐标”。合并两棵树，就是根据新约束计算两个局部坐标系原点之间的位移；距离并查集使用普通加减法，而本题使用 XOR。

3.6 同集合时如何判矛盾

如果 x 和 y 已经在同一个集合，已有关系已经被唯一确定：

text

1old_relation = xor[x] XOR xor[y]

xor[x] XOR xor[y] 正是 x 沿树走到根再走到 y 的位移和，自然等于 value[x] XOR value[y]。

只要 old_relation != w，当前回答就是第一条矛盾回答；相等则说明它只是重复描述了已有事实。

3.7 样例跟踪

忽略离散化编号，直接写前缀下标：

回答	加入的约束	当前推出的关系
`1 2 even`	$s[0]\oplus s[2]=0$	$s[0]=s[2]$
`3 4 odd`	$s[2]\oplus s[4]=1$	$s[0]\oplus s[4]=1$
`5 6 even`	$s[4]\oplus s[6]=0$	$s[0]\oplus s[6]=1$
`1 6 even`	要求 $s[0]\oplus s[6]=0$	与已有关系 $1$ 冲突

因此处理到第 4 条时输出下标 3，表示前 3 条回答可以成立。

3.8 带权并查集代码

下面先给出 C++17 版本。它先读入并离散化所有前缀坐标，再用数组实现并查集。

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/**
 * 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-07-16 17:48
 * update_at: 2026-07-21 09:53
 */
#include <bits/stdc++.h>
using namespace std;

struct Query {
    int left;
    int right;
    int parity; // even = 0, odd = 1
};

const int MAXM = 5005;

int parent_array[MAXM * 2];
int size_array[MAXM * 2];
int xor_to_parent[MAXM * 2];

// xor_to_parent[x] 表示 value[x] XOR value[parent[x]]。
int find_root(int x) {
    if (parent_array[x] == x) {
        return x;
    }

    int old_parent = parent_array[x];
    parent_array[x] = find_root(old_parent);
    xor_to_parent[x] ^= xor_to_parent[old_parent];
    return parent_array[x];
}

// 约束为 value[x] XOR value[y] = expected。
// 返回 false 表示这条约束和之前的约束矛盾。
bool unite(int x, int y, int expected) {
    int root_x = find_root(x);
    int root_y = find_root(y);

    if (root_x == root_y) {
        return (xor_to_parent[x] ^ xor_to_parent[y]) == expected;
    }

    // value[root_x] XOR value[root_y]
    int relation = xor_to_parent[x] ^ xor_to_parent[y] ^ expected;

    if (size_array[root_x] < size_array[root_y]) {
        swap(root_x, root_y);
    }

    parent_array[root_y] = root_x;
    xor_to_parent[root_y] = relation;
    size_array[root_x] += size_array[root_y];
    return true;
}

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

    int n, m;
    cin >> n >> m;

    vector<Query> queries;
    vector<int> coordinates;
    queries.reserve(m);
    coordinates.reserve(2 * m);

    for (int i = 0; i < m; i++) {
        int left, right;
        string word;
        cin >> left >> right >> word;

        // 区间 [left, right] 对应前缀点 left-1 和 right。
        left--;
        int parity = (word == "odd");
        queries.push_back({left, right, parity});
        coordinates.push_back(left);
        coordinates.push_back(right);
    }

    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()), coordinates.end());

    int node_count = static_cast<int>(coordinates.size());
    for (int i = 0; i < node_count; i++) {
        parent_array[i] = i;
        size_array[i] = 1;
        xor_to_parent[i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int x = lower_bound(coordinates.begin(), coordinates.end(), queries[i].left)
                - coordinates.begin();
        int y = lower_bound(coordinates.begin(), coordinates.end(), queries[i].right)
                - coordinates.begin();

        if (!unite(x, y, queries[i].parity)) {
            cout << i << '\n';
            return 0;
        }
    }

    cout << m << '\n';
    return 0;
}

Python 版本使用字典按需创建节点，不需要把 $10^9$ 范围的坐标压成数组下标；权值维护完全相同。

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
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# P5937 [CEOI 1999] Parity Game — 带权并查集解法
#
# 核心转换：
#   区间 [l,r] 中 1 的奇偶性 = prefix[r] XOR prefix[l-1]
#   每条回答变成两个前缀位置之间的关系约束。
#
# 带权并查集维护：
#   parity[x] = 节点 x 与它的根节点之间的 XOR 关系
#              0 → x 和根取值相同
#              1 → x 和根取值相反

import sys


input = sys.stdin.buffer.readline
_ = int(input())               # n 只用于读入，后面不需要
m = int(input())

# ---- 三个字典实现带权并查集（n 可达 1e9，只存出现过的位置）----
parent = {}   # parent[x] = x 的父节点，根指向自己
size = {}     # size[x]   = 以 x 为根的集合大小（按大小合并用）
parity = {}   # parity[x] = x 相对于父节点 parent[x] 的 XOR 关系


def add(x):
    """向并查集中加入一个新节点，初始为孤立点"""
    if x not in parent:
        parent[x] = x       # 自己是自己的根
        size[x] = 1         # 集合大小 = 1
        parity[x] = 0       # 自己和自己当然相同


def find(x):
    """
    查找 x 的根，并做路径压缩。
    路径压缩时要同步更新 parity：把 x 到根的 XOR 链折叠。
    """
    if parent[x] != x:
        old_parent = parent[x]
        parent[x] = find(old_parent)          # 递归到根
        # 此时 old_parent 已经指向了根，
        # parity[old_parent] 是 old_parent 到根的关系
        # 那么 x 到根 = x 到 old_parent XOR old_parent 到根
        parity[x] ^= parity[old_parent]
    return parent[x]


def unite(x, y, expected):
    """
    尝试合并两个节点 x 和 y。
    expected = 0: 要求 prefix[x] == prefix[y] （even）
    expected = 1: 要求 prefix[x] != prefix[y] （odd）

    返回 True 表示一致，False 表示矛盾。
    """
    root_x, root_y = find(x), find(y)

    # ---- 推导 root_x 和 root_y 之间应有的关系 ----
    # 已知:
    #   prefix[x]  = prefix[root_x] XOR parity[x]
    #   prefix[y]  = prefix[root_y] XOR parity[y]
    #   constraint: prefix[x] XOR prefix[y] = expected
    #
    # 代入:
    #   prefix[root_x] XOR parity[x] XOR
    #   prefix[root_y] XOR parity[y] = expected
    #
    # 移项:
    #   prefix[root_x] XOR prefix[root_y]
    #     = expected XOR parity[x] XOR parity[y]
    #
    # 令 relation = 上式右侧，这表示 root_x 和 root_y 之间的 XOR 关系:
    #   relation = 0 → roots 取值相同
    #   relation = 1 → roots 取值相反
    relation = parity[x] ^ parity[y] ^ expected

    # ---- 已在同一集合：检查是否一致 ----
    if root_x == root_y:
        # 此时 root_x == root_y，所以它们之间关系必须是 0（相同）
        return relation == 0     # relation == 0 → 一致；!= 0 → 矛盾

    # ---- 不在同一集合：按大小合并 ----
    if size[root_x] < size[root_y]:
        root_x, root_y = root_y, root_x       # 保证 root_x 是较大的树

    parent[root_y] = root_x                   # root_y 挂到 root_x 下
    parity[root_y] = relation                 # 记录 root_y 与 root_x 的关系
    size[root_x] += size[root_y]              # 更新大小
    return True


# ---- 主循环：逐条处理回答 ----
answer = m                        # 哨兵，默认所有回答都正确
for i in range(m):
    left, right, word = input().split()
    left, right = int(left) - 1, int(right)   # 转为 prefix[l-1] 和 prefix[r]
    add(left)
    add(right)

    # word == b"odd" → True(=1)，否则 False(=0)
    if answer == m and not unite(left, right, word == b"odd"):
        answer = i                # 记录第一条矛盾的回答编号（0-based）

4. 解法二：2N 并查集

带权并查集把“相同/相反”压缩成一个二进制权值。另一种更直观的办法是：把每个前缀变量拆成两个角色。

对离散化后的每个前缀点 $x$ 建立：

text

1
2x       表示 value[x] = 0
x + K   表示 value[x] = 1

这两个角色不能在同一个集合中。若最终出现 find(x)==find(x+K)，就说明同一个变量被迫同时取 $0$ 和 $1$ ，已经矛盾。

4.1 每条约束如何转成合并

关系	合并操作
$value[x]=value[y]$ （`even`）	`union(x, y)`，`union(x+K, y+K)`
$value[x]\ne value[y]$ （`odd`）	`union(x, y+K)`，`union(x+K, y)`

这就是“敌人的敌人是朋友”：如果 $x$ 和 $y$ 不同，那么 x=0 要和 y=1 归为一类，x=1 要和 y=0 归为一类；两条“不等”关系连起来，自然会推出两点相等。

4.2 为什么这样一定能判冲突

每个节点的两个角色代表它的两种可能取值。合并操作只连接彼此必须同时成立的角色：

相等约束连接同值角色；
不等约束连接异值角色。

如果某个变量的两个角色被并到同一连通分量，说明约束链同时要求它取 0 和取 1；反之，只要所有变量的两个角色仍然分离，就可以从每个连通分量中选择一种取值，满足当前所有关系。因此 find(x)==find(x+K) 恰好等价于矛盾。

4.3 2N 并查集代码

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/**
 * 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-07-21 09:53
 * update_at: 2026-07-21 09:53
 */
#include <bits/stdc++.h>
using namespace std;

struct Query {
    int left;
    int right;
    int parity; // even = 0, odd = 1
};

const int MAXM = 5005;

int parent_array[MAXM * 4];
int size_array[MAXM * 4];

int find_root(int x) {
    if (parent_array[x] == x) {
        return x;
    }

    parent_array[x] = find_root(parent_array[x]);
    return parent_array[x];
}

void unite(int x, int y) {
    int root_x = find_root(x);
    int root_y = find_root(y);
    if (root_x == root_y) {
        return;
    }

    if (size_array[root_x] < size_array[root_y]) {
        swap(root_x, root_y);
    }

    parent_array[root_y] = root_x;
    size_array[root_x] += size_array[root_y];
}

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

    int n, m;
    cin >> n >> m;

    vector<Query> queries;
    vector<int> coordinates;
    queries.reserve(m);
    coordinates.reserve(2 * m);

    for (int i = 0; i < m; i++) {
        int left, right;
        string word;
        cin >> left >> right >> word;

        left--;
        int parity = (word == "odd");
        queries.push_back({left, right, parity});
        coordinates.push_back(left);
        coordinates.push_back(right);
    }

    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()), coordinates.end());

    int node_count = static_cast<int>(coordinates.size());
    for (int i = 0; i < 2 * node_count; i++) {
        parent_array[i] = i;
        size_array[i] = 1;
    }

    for (int i = 0; i < m; i++) {
        int x = lower_bound(coordinates.begin(), coordinates.end(), queries[i].left)
                - coordinates.begin();
        int y = lower_bound(coordinates.begin(), coordinates.end(), queries[i].right)
                - coordinates.begin();

        if (queries[i].parity == 0) {
            // 相等：x0 与 y0 相连，x1 与 y1 相连。
            unite(x, y);
            unite(x + node_count, y + node_count);
        } else {
            // 相反：x0 与 y1 相连，x1 与 y0 相连。
            unite(x, y + node_count);
            unite(x + node_count, y);
        }

        // 同一个前缀点的 0/1 两种角色不能属于同一集合。
        if (find_root(x) == find_root(x + node_count)
                || find_root(y) == find_root(y + node_count)) {
            cout << i << '\n';
            return 0;
        }
    }

    cout << m << '\n';
    return 0;
}

Python 版本也保留在仓库中。它和 C++ 一样先完成坐标压缩，固定 offset=K，避免新坐标出现时第二层编号发生变化。

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# P5937 [CEOI 1999] Parity Game — 2N 并查集解法
# 对每个前缀位置建两个节点：
#   x     → prefix[x] = 0
#   x+K   → prefix[x] = 1（K 是不同前缀坐标的数量）
# (实际用字典映射到连续编号后偏移)

import sys


input = sys.stdin.buffer.readline
_ = int(input())
m = int(input())

# 先读完所有回答，再把出现过的前缀位置压成 0..k-1。
# 这样第二层节点统一使用 x + k，offset 不会在处理中途改变。
queries = []
coordinates = []
for _ in range(m):
    left, right, word = input().split()
    left, right = int(left) - 1, int(right)
    parity = word == b"odd"
    queries.append((left, right, parity))
    coordinates.append(left)
    coordinates.append(right)

coordinates = sorted(set(coordinates))
node_id = {value: index for index, value in enumerate(coordinates)}
offset = len(coordinates)

# 普通并查集（无额外权值），总节点数为 2 * offset。
parent = list(range(2 * offset))
size = [1] * (2 * offset)


def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


def unite(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]


answer = m
for i, (left, right, parity) in enumerate(queries):
    a = node_id[left]
    b = node_id[right]

    if parity == 0:
        # prefix[A] == prefix[B]
        # → A0 和 B0 在一起，A1 和 B1 在一起
        unite(a, b)
        unite(a + offset, b + offset)
    else:
        # prefix[A] != prefix[B]
        # → A0 和 B1 在一起，A1 和 B0 在一起
        unite(a, b + offset)
        unite(a + offset, b)

    # 判冲突：A0 和 A1 是否被逼到了同一集合？
    if find(a) == find(a + offset) or find(b) == find(b + offset):
        answer = i
        break

print(answer)

5. 两种解法怎么选

对比项	带权并查集	2N 并查集
节点数	$K$	$2K$
额外信息	每条父边存一个异或权	不存权，只复制两种角色
合并	推导 `relation` 后合并一次	每条约束合并两次
判矛盾	检查两点已有异或关系	检查 `x` 与 `x+K` 是否同根
学习重点	带权并查集的路径压缩与公式	种类并查集、敌我关系建模

两种写法的时间复杂度都足够通过本题。第一次学习时，建议先用 2N 并查集建立“角色连通”的直觉，再回到带权并查集理解如何把两种角色压缩成一个异或权值。

6. 常见错误

忘记把左端点改成 l-1：区间前缀关系一定是 s[r] XOR s[l-1]。
把 even 当成 1：本题中 even=0、odd=1，它们正好就是异或约束的右值。
路径压缩时只改父亲不改权值：压缩后权值必须把两段路径异或起来。
2N 写法的偏移量中途改变：若使用 x+K，必须先知道最终的 K；Python 版本因此先读完查询再离散化。
输出第一条错误回答的编号：循环下标从 0 开始，若第 i 条回答矛盾，应输出 i，它正好等于前面已经正确的回答数。

代码

本题保留 Python 解，同时提供等价的 C++17 解：

带权并查集

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/**
 * 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-07-16 17:48
 * update_at: 2026-07-21 09:53
 */
#include <bits/stdc++.h>
using namespace std;

struct Query {
    int left;
    int right;
    int parity; // even = 0, odd = 1
};

const int MAXM = 5005;

int parent_array[MAXM * 2];
int size_array[MAXM * 2];
int xor_to_parent[MAXM * 2];

// xor_to_parent[x] 表示 value[x] XOR value[parent[x]]。
int find_root(int x) {
    if (parent_array[x] == x) {
        return x;
    }

    int old_parent = parent_array[x];
    parent_array[x] = find_root(old_parent);
    xor_to_parent[x] ^= xor_to_parent[old_parent];
    return parent_array[x];
}

// 约束为 value[x] XOR value[y] = expected。
// 返回 false 表示这条约束和之前的约束矛盾。
bool unite(int x, int y, int expected) {
    int root_x = find_root(x);
    int root_y = find_root(y);

    if (root_x == root_y) {
        return (xor_to_parent[x] ^ xor_to_parent[y]) == expected;
    }

    // value[root_x] XOR value[root_y]
    int relation = xor_to_parent[x] ^ xor_to_parent[y] ^ expected;

    if (size_array[root_x] < size_array[root_y]) {
        swap(root_x, root_y);
    }

    parent_array[root_y] = root_x;
    xor_to_parent[root_y] = relation;
    size_array[root_x] += size_array[root_y];
    return true;
}

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

    int n, m;
    cin >> n >> m;

    vector<Query> queries;
    vector<int> coordinates;
    queries.reserve(m);
    coordinates.reserve(2 * m);

    for (int i = 0; i < m; i++) {
        int left, right;
        string word;
        cin >> left >> right >> word;

        // 区间 [left, right] 对应前缀点 left-1 和 right。
        left--;
        int parity = (word == "odd");
        queries.push_back({left, right, parity});
        coordinates.push_back(left);
        coordinates.push_back(right);
    }

    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()), coordinates.end());

    int node_count = static_cast<int>(coordinates.size());
    for (int i = 0; i < node_count; i++) {
        parent_array[i] = i;
        size_array[i] = 1;
        xor_to_parent[i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int x = lower_bound(coordinates.begin(), coordinates.end(), queries[i].left)
                - coordinates.begin();
        int y = lower_bound(coordinates.begin(), coordinates.end(), queries[i].right)
                - coordinates.begin();

        if (!unite(x, y, queries[i].parity)) {
            cout << i << '\n';
            return 0;
        }
    }

    cout << m << '\n';
    return 0;
}

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
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# P5937 [CEOI 1999] Parity Game — 带权并查集解法
#
# 核心转换：
#   区间 [l,r] 中 1 的奇偶性 = prefix[r] XOR prefix[l-1]
#   每条回答变成两个前缀位置之间的关系约束。
#
# 带权并查集维护：
#   parity[x] = 节点 x 与它的根节点之间的 XOR 关系
#              0 → x 和根取值相同
#              1 → x 和根取值相反

import sys


input = sys.stdin.buffer.readline
_ = int(input())               # n 只用于读入，后面不需要
m = int(input())

# ---- 三个字典实现带权并查集（n 可达 1e9，只存出现过的位置）----
parent = {}   # parent[x] = x 的父节点，根指向自己
size = {}     # size[x]   = 以 x 为根的集合大小（按大小合并用）
parity = {}   # parity[x] = x 相对于父节点 parent[x] 的 XOR 关系


def add(x):
    """向并查集中加入一个新节点，初始为孤立点"""
    if x not in parent:
        parent[x] = x       # 自己是自己的根
        size[x] = 1         # 集合大小 = 1
        parity[x] = 0       # 自己和自己当然相同


def find(x):
    """
    查找 x 的根，并做路径压缩。
    路径压缩时要同步更新 parity：把 x 到根的 XOR 链折叠。
    """
    if parent[x] != x:
        old_parent = parent[x]
        parent[x] = find(old_parent)          # 递归到根
        # 此时 old_parent 已经指向了根，
        # parity[old_parent] 是 old_parent 到根的关系
        # 那么 x 到根 = x 到 old_parent XOR old_parent 到根
        parity[x] ^= parity[old_parent]
    return parent[x]


def unite(x, y, expected):
    """
    尝试合并两个节点 x 和 y。
    expected = 0: 要求 prefix[x] == prefix[y] （even）
    expected = 1: 要求 prefix[x] != prefix[y] （odd）

    返回 True 表示一致，False 表示矛盾。
    """
    root_x, root_y = find(x), find(y)

    # ---- 推导 root_x 和 root_y 之间应有的关系 ----
    # 已知:
    #   prefix[x]  = prefix[root_x] XOR parity[x]
    #   prefix[y]  = prefix[root_y] XOR parity[y]
    #   constraint: prefix[x] XOR prefix[y] = expected
    #
    # 代入:
    #   prefix[root_x] XOR parity[x] XOR
    #   prefix[root_y] XOR parity[y] = expected
    #
    # 移项:
    #   prefix[root_x] XOR prefix[root_y]
    #     = expected XOR parity[x] XOR parity[y]
    #
    # 令 relation = 上式右侧，这表示 root_x 和 root_y 之间的 XOR 关系:
    #   relation = 0 → roots 取值相同
    #   relation = 1 → roots 取值相反
    relation = parity[x] ^ parity[y] ^ expected

    # ---- 已在同一集合：检查是否一致 ----
    if root_x == root_y:
        # 此时 root_x == root_y，所以它们之间关系必须是 0（相同）
        return relation == 0     # relation == 0 → 一致；!= 0 → 矛盾

    # ---- 不在同一集合：按大小合并 ----
    if size[root_x] < size[root_y]:
        root_x, root_y = root_y, root_x       # 保证 root_x 是较大的树

    parent[root_y] = root_x                   # root_y 挂到 root_x 下
    parity[root_y] = relation                 # 记录 root_y 与 root_x 的关系
    size[root_x] += size[root_y]              # 更新大小
    return True


# ---- 主循环：逐条处理回答 ----
answer = m                        # 哨兵，默认所有回答都正确
for i in range(m):
    left, right, word = input().split()
    left, right = int(left) - 1, int(right)   # 转为 prefix[l-1] 和 prefix[r]
    add(left)
    add(right)

    # word == b"odd" → True(=1)，否则 False(=0)
    if answer == m and not unite(left, right, word == b"odd"):
        answer = i                # 记录第一条矛盾的回答编号（0-based）

2N 并查集

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/**
 * 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-07-21 09:53
 * update_at: 2026-07-21 09:53
 */
#include <bits/stdc++.h>
using namespace std;

struct Query {
    int left;
    int right;
    int parity; // even = 0, odd = 1
};

const int MAXM = 5005;

int parent_array[MAXM * 4];
int size_array[MAXM * 4];

int find_root(int x) {
    if (parent_array[x] == x) {
        return x;
    }

    parent_array[x] = find_root(parent_array[x]);
    return parent_array[x];
}

void unite(int x, int y) {
    int root_x = find_root(x);
    int root_y = find_root(y);
    if (root_x == root_y) {
        return;
    }

    if (size_array[root_x] < size_array[root_y]) {
        swap(root_x, root_y);
    }

    parent_array[root_y] = root_x;
    size_array[root_x] += size_array[root_y];
}

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

    int n, m;
    cin >> n >> m;

    vector<Query> queries;
    vector<int> coordinates;
    queries.reserve(m);
    coordinates.reserve(2 * m);

    for (int i = 0; i < m; i++) {
        int left, right;
        string word;
        cin >> left >> right >> word;

        left--;
        int parity = (word == "odd");
        queries.push_back({left, right, parity});
        coordinates.push_back(left);
        coordinates.push_back(right);
    }

    sort(coordinates.begin(), coordinates.end());
    coordinates.erase(unique(coordinates.begin(), coordinates.end()), coordinates.end());

    int node_count = static_cast<int>(coordinates.size());
    for (int i = 0; i < 2 * node_count; i++) {
        parent_array[i] = i;
        size_array[i] = 1;
    }

    for (int i = 0; i < m; i++) {
        int x = lower_bound(coordinates.begin(), coordinates.end(), queries[i].left)
                - coordinates.begin();
        int y = lower_bound(coordinates.begin(), coordinates.end(), queries[i].right)
                - coordinates.begin();

        if (queries[i].parity == 0) {
            // 相等：x0 与 y0 相连，x1 与 y1 相连。
            unite(x, y);
            unite(x + node_count, y + node_count);
        } else {
            // 相反：x0 与 y1 相连，x1 与 y0 相连。
            unite(x, y + node_count);
            unite(x + node_count, y);
        }

        // 同一个前缀点的 0/1 两种角色不能属于同一集合。
        if (find_root(x) == find_root(x + node_count)
                || find_root(y) == find_root(y + node_count)) {
            cout << i << '\n';
            return 0;
        }
    }

    cout << m << '\n';
    return 0;
}

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# P5937 [CEOI 1999] Parity Game — 2N 并查集解法
# 对每个前缀位置建两个节点：
#   x     → prefix[x] = 0
#   x+K   → prefix[x] = 1（K 是不同前缀坐标的数量）
# (实际用字典映射到连续编号后偏移)

import sys


input = sys.stdin.buffer.readline
_ = int(input())
m = int(input())

# 先读完所有回答，再把出现过的前缀位置压成 0..k-1。
# 这样第二层节点统一使用 x + k，offset 不会在处理中途改变。
queries = []
coordinates = []
for _ in range(m):
    left, right, word = input().split()
    left, right = int(left) - 1, int(right)
    parity = word == b"odd"
    queries.append((left, right, parity))
    coordinates.append(left)
    coordinates.append(right)

coordinates = sorted(set(coordinates))
node_id = {value: index for index, value in enumerate(coordinates)}
offset = len(coordinates)

# 普通并查集（无额外权值），总节点数为 2 * offset。
parent = list(range(2 * offset))
size = [1] * (2 * offset)


def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x


def unite(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]


answer = m
for i, (left, right, parity) in enumerate(queries):
    a = node_id[left]
    b = node_id[right]

    if parity == 0:
        # prefix[A] == prefix[B]
        # → A0 和 B0 在一起，A1 和 B1 在一起
        unite(a, b)
        unite(a + offset, b + offset)
    else:
        # prefix[A] != prefix[B]
        # → A0 和 B1 在一起，A1 和 B0 在一起
        unite(a, b + offset)
        unite(a + offset, b)

    # 判冲突：A0 和 A1 是否被逼到了同一集合？
    if find(a) == find(a + offset) or find(b) == find(b + offset):
        answer = i
        break

print(answer)

复杂度

设不同前缀坐标的数量为 $K$ ，则 $K\le 2m$ 。

坐标排序和离散化： $O(m\log m)$ 。
带权并查集： $O(m\alpha(K))$ 时间， $O(K)$ 空间。
2N 并查集： $O(m\alpha(K))$ 时间， $O(2K)$ 空间。
Python 带权版本用字典保存实际出现的坐标，空间复杂度同样为 $O(K)$ 。

其中 $\alpha$ 是反阿克曼函数，可以认为增长极慢。

总结

这题的真正主线只有三步：

区间奇偶转前缀异或： $[l,r]$ 的答案变成 $s[l-1]\oplus s[r]$ 。
维护前缀点之间的相等/相反关系：可以用带异或权的并查集，也可以把每个点拆成 0/1 两个角色，用 2N 并查集维护。
按输入顺序找第一条冲突：新约束若与已有关系不一致，当前下标就是答案。

带权并查集的核心不变量是“节点到根的异或值”；2N 并查集的核心不变量是“同一变量的两个角色不能同根”。理解这两个不变量，今后遇到相等/不等、同类/异类、奇偶关系的题目，就能快速识别出对应的并查集模型。

一图流解析

这张图把本题的建模、两种并查集、实现检查和训练方法压缩到一页，适合读完正文后复盘。

数学本质： $\mathbb{F}_2$ 上的关系系统

前面把边权称为“关系向量”。更严格地说，每个前缀值 $s[i]$ 都是二元域 $\mathbb{F}_2=\{0,1\}$ 中的元素，所有前缀值共同组成 $\mathbb{F}_2^K$ 中的一个向量；每条回答

s[x]\oplus s[y]=w

都是一个关于这些前缀值的线性或仿射约束。带权并查集没有保存所有前缀值，而是选每棵树的根作为局部原点，只保存节点相对于原点的关系。

因此，a-b 和 b-c 能推出 a-c，准确地说不是“向量具有传递性”，而是路径上的关系可以合成：

rel(a,c)=rel(a,b)\oplus rel(b,c).

异或体系还有下面三个特别有用的性质。

1. 反向关系仍是它自己

在普通距离并查集中，如果从 $A$ 到 $B$ 的位移是 $+3$ ，那么从 $B$ 到 $A$ 的位移就是 $-3$ ，合并时必须小心方向。

但在 $\mathbb{F}_2$ 中，每个元素都是自己的加法逆元：

x\oplus x=0, \qquad -x=x.

所以

rel(A,B)=s[A]\oplus s[B]=s[B]\oplus s[A]=rel(B,A).

顺着边走和逆着边走都使用同一个权值。这就是合并公式

text

1relation = xor[x] XOR xor[y] XOR expected

不需要额外处理正负号的原因。这里的“无向”只表示关系值反向后不变；并查集中的父指针仍然有方向。

2. 一致系统中的环路异或和为 0

设关系图中有一个环：

text

1v0 -> v1 -> v2 -> ... -> vt = v0

把环上所有边权异或起来：

\begin{aligned} &(s[v_0]\oplus s[v_1]) \oplus(s[v_1]\oplus s[v_2]) \oplus\cdots \oplus(s[v_{t-1}]\oplus s[v_0])\\ &=0. \end{aligned}

每个节点势值都恰好出现两次，因此全部抵消。于是一个关系系统能够成立，当且仅当任意环上的边权异或和都是 $0$ 。

当 unite(x,y,w) 发现 $x,y$ 已经同根时，树中已经存在一条 $x$ 到 $y$ 的路径。新回答相当于再加入一条边并闭合成环：

text

1环路异或和 = 树上已有关系 XOR 新回答 w

结果为 0：新回答与已有路径一致；
结果为 1：这个环不可能由任何一组前缀值产生，出现矛盾。

所以代码中的

text

1(xor[x] XOR xor[y]) == w

本质上就是一次零和环检查。也可以把它类比为“沿闭合回路走一圈，回到原点后总位移必须为零”。

3. 区间累积可以变成端点势差

并查集维护的是点与点之间的关系，而题目给出的是区间 $[l,r]$ 中 $1$ 的个数奇偶性。连接二者的是前缀异或：

\bigoplus_{i=l}^{r}a_i=s[r]\oplus s[l-1].

区间外的前缀部分出现两次并被抵消，于是整段区间的信息只由两个端点决定。可以把它类比成离散的“路径累积等于端点势差”；其严格依据就是前缀异或的消去性质，并不需要使用连续微积分。

这一步才是本题真正的建模跳跃：

text

1
2
3
4区间奇偶约束
  -> 两个前缀端点之间的关系边
  -> 动态加入边并检查零和环
  -> 异或带权并查集

4. 以后如何识别这个模型

题面信号	应想到的转换
区间 $[L,R]$ 的和、奇偶性或 XOR	建立前缀状态，把区间改写为 $L-1$ 与 $R$ 的关系
关系只有相同/相反、真/假、奇/偶	用 $0/1$ 表示关系，并在 $\mathbb{F}_2$ 中用 XOR 合成
关系逐条加入，并要求找第一次矛盾	把回答看成加边；同集合时检查新边闭合出的环
坐标范围很大，但回答数量较少	只离散化实际出现的关系端点

可以压缩成下面这条思维链：

text

1
2
3
4
5
6区间累积属性
  -> 前缀端点势差
  -> 相对关系图
  -> 路径关系合成
  -> 零和环一致性
  -> 带权并查集

因此，以后看到“区间奇偶性判断 + 动态一致性检验”，应优先尝试“前缀异或 + 带权并查集”。如果所有关系一次性给出、不要求在线处理，也可以在关系图上用 DFS/BFS 染色检查；并查集的优势在于按顺序动态加入约束。

推荐

本题的权值只有 0/1，所以用 XOR 就能表示“相同/相反”。如果想把“关系向量”的视角继续练熟，建议沿着下面的顺序做题：先练普通加法位势，再练多状态循环关系。

1. 距离型位势：P1196「银河英雄传说」

题目链接：P1196 [NOI2002] 银河英雄传说

这题维护的是战舰到队头的相对距离：

dist_to_head[x] 就是节点相对于根的位移；
路径压缩时把两段距离相加；
合并两列时，根据另一列的长度设置根之间的位移。

它和 P5937 的代码骨架几乎一样，区别只是“关系的加法”换了：

text

1
2P5937：相对位移用 XOR，只有 0/1 两种关系
P1196：相对位移用普通加法，表示实际距离

练习时重点检查：父子方向是什么、路径压缩后距离如何累加、合并时为什么要加上另一棵树的大小。

2. 模 $k$ 关系：P2024「食物链」

题目链接：P2024 [NOI2001] 食物链

这题可以看成 k=3 的循环关系：同类、吃、被吃分别相差 $0$ 、 $1$ 、 $2$ 。它通常用 3N 拆点来写，但底层关系仍然是模 3 的加法：

rel(x,z)=(rel(x,y)+rel(y,z))\bmod 3。

建议分两步练习：

先用题解中的 3N 拆点法，熟悉“一个对象对应多个关系角色”；
再尝试把每条父边改成一个 0/1/2 的模 3 权值，自己推导路径压缩和合并公式。

这样就能从本题的二元 XOR 关系，迁移到一般的模 $k$ 关系并查集。

3. XOR 约束进阶：Codeforces 1615D「X(or)-mas Tree」

题目链接：Codeforces 1615D X(or)-mas Tree

这题把 XOR 关系放到了树上：边权可能未知，但给出的路径约束必须同时成立。它适合用来练习“已知两点相对 XOR，如何沿树传递并检查冲突”，是本题前缀点关系模型的图结构版本。

练习时先不要急着套模板，先明确每条树边的 0/1 关系，再思考如何把“路径 XOR”转成节点到根的相对关系。

4. 2N 拆点进阶：Codeforces 468B「Two Sets」

题目链接：Codeforces 468B Two Sets

这题适合继续训练 2N 并查集：每个元素都有两种互补选择，约束会把“选择 0”的节点和另一个元素的某种角色连起来。它不再是区间奇偶，但“为每个对象建立两个角色、用并查集维护互斥关系”的思想完全相通。

练习重点是自己写出：

两个角色分别代表什么；
一条约束要合并哪两对节点；
如何检查一个元素的两个角色是否被合并到同一集合。