题意：

有一串长为的01串，给出个问题，每个问题会给出一个区间范围和该范围内的个数的奇偶性，但是每当提出一个新问题都有可能会和已知问题产生冲突。问产生冲突的问题的最小序号。

 
 

分析：

乍一看并不像并查集能够处理的问题，但是范围的左右端点到的奇偶性是可以被统计的，所以区间内为如果偶数，则可以说明的奇偶性一样，奇数则相反。这就类似于扩展域并查集，将区间的两个端点分为两个点，分别表示这两种性质，如果这两种性质有关联（同奇偶或不同奇偶），则合并这两个点，最终检验的时候只需判断点是否属于同一个集合即可。
另外值得注意的一点是，该题的范围很大，需要做离散化处理，并且并查集的初始化需要在离散化后才可以进行，否则会出现一系列越界的情况。

 
 

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod = 1e9 +7;
//constexpr int mod2 = 998244353;
constexpr int MAXNe5 = 2e5 +7;
constexpr int MAXNe6 = 1e6 + 7;
typedef long long ll;
#pragma region 
inline long long read() {
    char c = getchar();long long flag = 1, ans = 0;
    while(c < '0' || c > '9'){if(c == '-') flag = -1; c = getchar();}
    while(c >= '0' && c <= '9'){ans = ans * 10 + c - '0'; c = getchar();}
    return (ans * flag);
}
#pragma endregion
// C'est la vie
struct {
    int a, b, tag;
}input[MAXNe5];
int fa[MAXNe5], num[MAXNe5], len = 0, k = 0, n = 0;
int find(int x) {
    return (fa[x] == x) ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y) {
    fa[find(x)] = find(y);
}

void init() {
    cin >> len >> k;
    int tmp = 0;
    for(int i = 1; i <= k; ++ i) {
        string opt;
        cin >> input[i].a >> input[i].b >> opt;
        input[i].tag = (opt == "even") ? 0 : 1;
        num[++ tmp] = input[i].a - 1;
        num[++ tmp] = input[i].b;
    }
    sort(num + 1, num + tmp + 1);
    n = unique(num + 1,num + tmp + 1) - num - 1;
    for(int i = 1; i <= 2 * n + 1; ++ i) fa[i] = i;
}

signed main() {
    ios::sync_with_stdio(false);
    init();
    for(int i = 1; i <= k; ++ i) {
        int x = lower_bound(num + 1, num + n + 1, input[i].a - 1) - num,
            y = lower_bound(num + 1, num + n + 1, input[i].b) - num;
        if(input[i].tag) {
            if(find(x) == find(y)) {
                cout << i - 1 << endl;
                return 0;
            }
            merge(x, y + n);
            merge(x + n, y);
        } else {
            if(find(x) == find(y + n)) {
                cout << i - 1 << endl;
                return 0;
            }
            merge(x, y);
            merge(x + n, y + n);
        }
    }
    cout << k << endl;
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
}