首先需要理解题目中一个关键但隐蔽的限制条件。

可以将问题转化为前缀和的角度来思考：给定区间 [l, r] 中有奇数个 1，意味着前缀和 S[r] - S[l-1] 是奇数，即 S[r] 和 S[l-1] 的奇偶性不同。这里的 S 表示前缀和变量，这个性质具有传递性和对称性——如果 x 与 y 奇偶性相同，y 与 z 奇偶性相同，则 x 与 z 奇偶性相同。这种等价关系非常适合用并查集维护。

由于 N 可能很大（可达 10^9）而 M（约束个数）较小（最多 10000），显然需要离散化处理端点。使用带权并查集来维护奇偶关系，用 0 表示相同，1 表示不同（实际上可以扩展到用模 n 表示更一般的关系）。

带权并查集的核心实现：

int parent[N], weight[N];

int find(int x) {
    if (parent[x] == x) return x;
    int oldParent = parent[x];
    parent[x] = find(parent[x]);
    // 权值累加：到父亲节点权值 + 父亲节点到根节点权值
    weight[x] += weight[oldParent];
    return parent[x];
}

处理每条约束时，首先对端点 l-1 和 r 进行离散化映射，然后检查它们是否在同一集合中：

1. 已在同一集合：说明两个端点之前已有关系。权重 weight[a] 表示 a 与根节点的关系，weight[b] 表示 b 与根节点的关系。根据异或运算，a 与 b 的奇偶关系为 weight[a] ^ weight[b]。如果这个值与约束给定的值（0 表示偶数个1，1 表示奇数个1）不相等，则出现矛盾，输出当前约束序号。
2. 不在同一集合：需要合并两个集合。设 pa 是 a 的根，pb 是 b 的根，t 是约束值。可列出等式： weight[pa] ^ weight[a] ^ weight[b] = t 从而推导出： weight[pa] = weight[a] ^ weight[b] ^ t 将 pa 指向 pb，并设置 weight[pa] 为该值。

完整代码实现（C++）：

#include <iostream>
#include <unordered_map>
using namespace std;

const int MAXM = 10010;
unordered_map<int, int> mp;
int parent[MAXM], weight[MAXM], idx;

int find(int x) {
    if (parent[x] != x) {
        int orig = parent[x];
        parent[x] = find(parent[x]);
        weight[x] ^= weight[orig];  // 注意是异或操作，因为奇偶性只有两种状态
    }
    return parent[x];
}

int compress(int x) {
    if (mp.find(x) == mp.end())
        mp[x] = ++idx;
    return mp[x];
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= MAXM; ++i)
        parent[i] = i;

    for (int i = 0; i < m; ++i) {
        int l, r;
        string type;
        cin >> l >> r >> type;
        int t = (type == "odd") ? 1 : 0;
        int a = compress(l - 1), b = compress(r);
        int pa = find(a), pb = find(b);
        if (pa == pb) {
            if ((weight[a] ^ weight[b]) != t) {
                cout << i << endl;
                return 0;
            }
        } else {
            parent[pa] = pb;
            weight[pa] = weight[a] ^ weight[b] ^ t;
        }
    }
    cout << m << endl;
    return 0;
}

关键技巧总结：

• 将区间奇偶性转化为端点奇偶关系的等价性（前缀和思想）。
• 用异或运算表示两种状态（奇偶相同为0，不同为1），符合模2域的特性。
• 离散化减少空间复杂度（从 O(N) 降到 O(M)）。
• 带权并查集中权值的累积与合并通过异或实现，简洁高效。