并查集

1. 常用操作与优化

• 合并两个集合
• 查询某个元素的祖宗节点
• 在查询的过程中可以做路径压缩操作

2. 使用场景

常用于具有传递性质的题目中，并且传递具有双向性，即可以理解为无向图关系。

3. 例题

3.1 题意理解

使用前缀和思想: Si 表示前i个数中1的个数则 S[l~r] 中有奇数个1 de等价于 S[r] - S[l-1] 为奇数 等价于 S[r] 与 S[l-1] 的奇偶性不同；同理可推， S[l-r] 中有偶数个1 等价于 S[r] 与 S[l-1] 的奇偶性相同。

因此可以将题意简化为: 给定两个以及经它们之间的奇偶性，根据给定的条件判断是否有矛盾。

3.2 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 20004;

int fa[N];  // 并查集数组
int d[N];  // 维护到到根节点的距离
unordered_map<int, int> s;  // 用于离散化点

int n, m;

int find(int x) {
    if(x != fa[x]) {
        int root = find(fa[x]);
        // 在模 2 的状态下, 加法等价于 异或运算
        d[x] ^= d[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}

int get(int x) {
    if(s.count(x) == 0) s[x] = ++n;
    return s[x];
}

int main() {
    cin >> n >> m;
    n = 0;
    
    // 并查集初始化
    for(int i = 0; i < N; i++) fa[i] = i;
    
    int ans = m;
    for(int i = 1; i <= m; i++) {
        int a, b;
        string op;
        cin >> a >> b >> op;
        
        // 使用类似前缀和思想, 因此 b 需要 -1
        a = get(a - 1), b = get(b);
        int t = 0;
        if(op == "odd") t = 1;
        
        int pa = find(a), pb = find(b);
        if(pa == pb) {
            if((d[a] ^ d[b]) != t) {
                ans = i - 1;
                break;
            }
        } else {
            fa[pa] = pb;
            d[pa] = d[a] ^ d[b] ^ t;
        }
    }
    cout << ans;
    
    return 0;
}