并查集详解
https://blog.csdn.net/sjystone/article/details/115406797

奇偶游戏 https://www.acwing.com/problem/content/241/

数据范围：序列长度1～1e9 询问数量1～1e4

前缀和 + 离散化 + 并查集 + 异或运算

并查集 1)带边权 - 集合内两点的相对关系 - 复杂度和分类的数量无关
2)带邻域 - 枚举的思路 - 复杂度和分类的数量有关 - 类别多的时候不能用

令si = a1 + a2 + … + ai (a = 0/1)
ai = |si - si-1| -> 若si和si-1奇偶性相同，ai=0，若si和si-1奇偶性不同，ai=1
-> 故能够造出01数列a，满足条件

s[l~r]中有奇数个1 s[l~r]中有偶数个1
-> s[r] - s[l-1] 为奇数 -> s[r] - s[l-1] 为偶数
-> s[r]与s[l-1]奇偶性不同 -> s[r]与s[l-1]奇偶性相同

若每次输入的奇偶性与存在的奇偶性无矛盾 <-> 问题无矛盾

1.带边权的并查集

维护相对关系，每个点存他和跟节点的关系d[x]
通过每个点与跟节点的相对关系，得到每个点间的关系 ⌬
d[x]存0/1，表示x和px的关系
若d[x] = 0，表示x与px同类，否则不同类
    对于点x和y：
    若d[x] + d[y]为偶数(d[x]^d[y] = 0) 
        -> 则x与根同类，y与根同类 -> x与y同类(奇偶性相同)
    若d[x] + d[y]为奇数(d[x]^d[y] = 1) 
        -> x(y)与根同类，y(x)与根不同类 -> x与y不同类(奇偶性不同)

1）若告诉我们x和y是同类
    若px = py
        -> 说明x和y在同一个集合中
        (点x)o->o->...-> o(跟节点) <-o<-o<-o(点y)
        若d[x]^d[y] = 0 -> x与y同类 -> 无矛盾
        若d[x]^d[y] = 1 -> x与y异类 -> 有矛盾
    若px != py
        将x集合合并到y集合
        x和y是同类 -> d[x] + d[px] + d[y]为偶数  (d[px]表示px到py的距离)
        -> d[px] = d[x]^d[y]^0  (该取值可满足上一行要求)

2）若告诉我们x和y是异类
    若px = py
        -> 说明x和y在同一个集合
        若d[x]^d[y] = 0 -> x和y是同类 -> 有矛盾
        若d[x]^d[y] = 1 -> x和y是异类 -> 无矛盾
    若px != py
        将x集合合并到y集合
        x和y是异类 -> d[x] + d[px] + d[y]为奇数
        d[px] = d[x]^d[y]^1  (该取值可满足上一行要求)

//带边权
#include <iostream>
#include <cstdio>
#include <unordered_map>
using namespace std;

const int N = 20010;
int p[N], d[N], n, m, cnt;
unordered_map<int, int> mp;

int get(int x)
{
    if ( !mp.count(x) ) mp[x] = ++ cnt;
    return mp[x];
}

int find(int x)
{
    if ( x != p[x] ) 
    {
        int root = find(p[x]);
        d[x] += d[p[x]] % 2; //防止数据越界，也可以这里不mod2，下面判断时(...mod2+2)%2转为正数(奇偶不影响)
        p[x] = root;
    }
    return p[x];
}

int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= N; i ++ ) p[i] = i;
    int res = m;
    for ( int i = 1; i <= m; i ++ )
    {
        int a, b;
        string type;
        cin >> a >> b >> type;
        a = get(a - 1), b = get(b); //对于虚拟数组a的前缀和，为s[l-1]到s[r]
        int t = 0;
        if ( type == "odd" ) t = 1; //用t控制奇偶性，巧妙运用
        int pa = find(a), pb = find(b);
        if ( pa == pb )
        {
            if ( (d[a] + d[b]) % 2 != t )   //如果奇偶性不匹配
            {
                res = i - 1;
                break;
            } 
        }
        else 
        {
            p[pa] = pb;
            d[pa] = d[a] ^ d[b] ^ t;    //按输入处理d[a] d[b]的关系
        }
    }
    cout << res;
    return 0;
}