解题思路

若$x$, $y$之间$1$的个数为偶数个, 那么$1$~$x$ 与$1$~$y$中$1$的个数同奇偶性, 反之则异奇偶性, 我们可以将其理解为若输入$x$, $y$, $even$, 即$x$, $y$属于同种, 反之则属于不同种,

用种类并查集就可以啦…不过要注意三点, 一是数据范围$1e9$, 不能直接用做数组下标, 要先离散化一下，当然本题只需要用$map$映射下就行了; 二是输入的数据中$x$, $y$是闭区间, 不好处理, 我们可以将其化为半开区间来处理, $(x-1, y]$； 还有就是如果全部正确的话就输出$m$。

标程

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>
#include <string>
using namespace std;

#define SIS std::ios::sync_with_stdio(false)
#define endl '\n'

const int MAXN = 10005;  // 1e4+5在C++98中可能被部分编译器警告，改为具体数值
int pre[MAXN], rk[MAXN];

void init() {
    memset(rk, 0, sizeof(rk));
    for (int i = 0; i < MAXN; ++i)
        pre[i] = i;
}

int _find(int x) {
    if (x == pre[x]) return x;
    int p = pre[x];
    pre[x] = _find(pre[x]);
    rk[x] ^= rk[p];
    return pre[x];
}

bool unite(int a, int b, int c) {
    int x = _find(a);
    int y = _find(b);
    if (x == y && (rk[a] ^ rk[b]) == c) return true;
    else if (x == y) return false;
    pre[x] = y;
    rk[x] = rk[a] ^ rk[b] ^ c;
    return true;
}

int main() {
    SIS;
    int n, m, x, y, pos = 0, ans = 0;
    bool flag = false;
    string s;
    map<int, int> mp;
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; ++i) {
        cin >> x >> y >> s;
        if (flag) continue;
        x--;  
        int k = (s[0] == 'e') ? 0 : 1;
        if (!mp[x]) mp[x] = ++pos;
        if (!mp[y]) mp[y] = ++pos;
        if (!unite(mp[x], mp[y], k)) {
            ans = i - 1;
            flag = true;
        } else if (i == m) {
            ans = m;
        }
    }
    cout << ans << endl;
    return 0;
}