acwing 239. 奇偶游戏 并查集

地址  https://www.acwing.com/problem/content/241/

小A和小B在玩一个游戏。

首先，小A写了一个由0和1组成的序列S，长度为N。

然后，小B向小A提出了M个问题。

在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。

请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k，使得01序列S满足第1~k个回答，但不满足第1~k+1个回答。

输入格式

第一行包含一个整数N，表示01序列长度。

第二行包含一个整数M，表示问题数量。

接下来M行，每行包含一组问答：两个整数l和r，以及回答“even”或“odd”，用以描述S[l~r] 中有奇数个1还是偶数个1。

输出格式

输出一个整数k，表示01序列满足第1~k个回答，但不满足第1~k+1个回答，如果01序列满足所有回答，则输出问题总数量。

数据范围
N≤10^9,M≤10000
输入样例：
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出样例：
3

解答1：

带权并查集

本题目有两个难点 

1 数据范围过大  有 10^9 

2 询问的内容如何转化到并查集

问题1 的解决办法是 使用离散化 将不同的数据映射到1 2 3 4。。。，由于只有10000次 询问，每次询问提供两个数据 所以只要提供10000*2的数据范围即可

问题2 的解决办法是 前缀和 如果提供 l和r的范围内1有奇数个还是偶数个 也就是计算 前缀和 sum[r] - sum[l-1]

另由于有偶数减偶数 奇数减奇数 都是偶数   只有两者不同类型分别是奇数偶数中的一种 才会出现最后的差是奇数

那么并查集其实也就是前缀和中每个元素的奇偶性

增加带权数组 所有的前缀和元素都会合并到一个祖先中，d[x]带权数组会记录x元素是否与根是同样的奇偶性

当得到新的询问时候 如果两个元素已经合并在同一个祖先下，那么就可以根据他们与祖先的异同得到他们的异同，再来判断他们与输入的异同是否一致 如果不一致就是发生矛盾，返回即可

代码如下

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

const int MAX_M = 20010;

int N, M;
int n, m;

int fa[MAX_M];
int d[MAX_M];

int idx = 0;

unordered_map<int, int> S;


//离散化
int get(int x) {
    if (S.count(x) == 0) S[x] = ++idx;
    return S[x];
}

void init()
{
    for (int i = 0; i < MAX_M; i++) {
        fa[i] = i;
    }
}

int find(int x) {
    if (fa[x] != x) {
        int root = find(fa[x]);
        d[x] += d[fa[x]]%2;
        fa[x] = root;
    }

    return fa[x];
}


int main()
{
    
    cin >> n >> m;
    int res = m;
    init();
    for (int i = 1; i <= m; i++) {
        int a, b; string s;
        cin >> a >> b >> s;
        a = get(a - 1); b = get(b);
        int pa = find(a), pb = find(b);

        if (pa == pb) {
            //查看两者是否符合之前的信息
            if (s == "even")
            {
                //两者奇偶性相同
                if( (d[a] + d[b]) % 2 != 0){
                    //有矛盾
                    res = i - 1;
                    break;
                }
            }
            else if (s == "odd") {
                //两者奇偶性不同
                if ((d[a] + d[b]) % 2 != 1) {
                    //有矛盾
                    res = i - 1;
                    break;
                }
            }
            else {
                cout << s << endl;
                cout << "error" << endl;
                break;
            }
        }
        else {
            //pa != pb
            //合并
            fa[pa] = pb;
            int add = 0;
            if (s == "odd") add = 1;
            d[pa] = (d[a] + d[b] + add)%2;
        }


    }
    cout << res << endl;



    return 0;
}

解法2 并查集扩展域

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

const int MAX_N = 20020*2; 
const int Base = MAX_N / 2;

unordered_map<int, int> S;
int n, m;

int p[MAX_N];

int idx = 0;
//离散化
int get(int x) {
    if (S.count(x) == 0) S[x] = ++idx;
    return S[x];
}

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);

    return p[x];
}

int main()
{
    cin >> n >> m; int res = m;
    for (int i = 0; i < MAX_N; i++) p[i] = i;

    for (int i = 1; i <= m; i++) {
        int a, b; string s;
        cin >> a >> b >> s;
        a = get(a - 1); b = get(b);

        if (s == "even") {
            //相同
            if (find(a + Base) == find(b)) {
                res = i - 1;
                break;
            }
            p[find(a)] = find(b);
            p[find(a + Base)] = p[find(b + Base)];
        }
        else {
            if (find(a) == find(b)) {
                res = i - 1;
                break;
            }
            p[find(a+Base)] = find(b);
            p[find(a )] = p[find(b + Base)];

        }
        

    }
    cout << res << endl;

    return 0;
}