AcWing 239. 奇偶游戏（边带权/扩展域并查集 离散化 xor）

题意：

有一个长度为n的序列，给出m条限制，给出区间[l，r]和parity（中文意思是奇偶性）。

①parity == "odd" 表示[l,r]区间内'1'的个数是奇数。
②parity == "even" 表示[l,r]区间内'1'的个数是偶数。

请你输出最小的不满足条件的编号减一，如果全部满足，输出限制条件总数m。

思路：

对于本题我们可以有两种做法，第一种是“边带权”并查集，第二种是“扩展域”并查集。两种做法的运行效率差不多，不过第二种会更好写，且更容易理解，现在我们先讲边带权并查集。

一、

由题意，我们很容易了解到，这个题描述的是区间关系，而并查集只能作用于两个点的关系，因此我们要进行关系转换。

如果我们用sum数组表示序列s的前缀和，那么，在输入问题每一个小A的回答中：

• (1)s[l~r]中有偶数个1，等价于sum[r]-sum[l-1]的值为偶数，即(s[r]-s[l-1])%2==0，也即sum[l-1]和sum[r]奇偶性是相同的（因为两个奇数或两个偶数相减的结果无论如何都是偶数）

• (2)s[l~r]中有奇数个1，等价于sum[r]-sum[l-1]的值为奇数，即(s[r]-s[l-1])%2==1，也即sum[l-1]和sum[r]奇偶性是不同的（因为一个奇数和一个偶数相减无论如何都是奇数）

（注意，我们并没有真正求出sum数组，我们只是把sum视作变量，这时，这道题与之前的AcWing 237. 程序自动分析（第二类离散化 并查集） 一题就非常相像了，共同点：都是给定若干变量和关系，判定这些关系是否满足的问题。不同点：传递关系不一样）

二、

另外，题目中还提到，输入序列的长度n非常的大，达到了1e9，但是输入的问题数m却很少，只有1e5，而每个问题中包含2个区间的端点值，因此我们首先要用离散化将每个问题的两个整数：l-1和r缩小到等价的1~2m，即1~2e5以内的范围。

我们是用的是第二类离散化，不要求保序：

int idx;
unordered_map<int, int> umi;

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

三、

为了处理多种传递关系，我们是用“边带权”的并查集解决。

定义边权数组d[]，d[x]=0表示x与父节点p[x]的奇偶性相同，d[x]=1表示x与父节点p[x]奇偶性相反。（注意是父节点，父节点也可以是根节点的）

我们在find函数中进行路径压缩的时候，联系dfs的思想，我们发现，在递归到尽头后回溯的时候对x到其所属的根节点路径上所有边权进行异或运算（xor），就可以轻松得到x和根节点的奇偶性关系。

（由于按位加法运算在模2的意义下等价于按位异或运算，因此也可以用相加模2来代替。注意，一定要加上“按位”俩字，按位即按二进制位，只有0、1参与操作，如果 任给两个整数相加模2 的结果当然可能不会等于 两个整数异或的结果。可详见此处。）

find函数：

int find(int x)
{
        if(p[x]!=x)
        {
//先用一个变量root记录根节点find(p[x])，那么p[x]指向的还会是它的父亲而不是根节点，这时已经递归到了最底层，
//所以一步步冒泡 d[x]+=d[p[x]] 就是将x一直到根节点一段段加起来，最后用完p[x]之后再将p[x]指向根节点。

                int root = find(p[x]);
                d[x]^=d[p[x]];//联系dfs的思想，我们在回溯的时候对x到其所属的根节点路径上所有边权进行异或运算，也可写为：d[x] = (d[x] + d[p[x]]) % 2;
                p[x] = root;//路径压缩
        }
        return p[x];
}

四、

对于每一个问题，设在离散化之后l-1、r的值分别是a、b，设ans表示对于当前问题小A给出的的答案。

（当ans等于0，代表当前区间[l, r]内有偶数个'1'，且a、b奇偶性相同。如等于1，代表当前区间内有奇数个'1'，且a、b奇偶性不同）。

先判断a和b是否属于同一集合（是否已知奇偶关系），当查询函数find(a)、find(b)都执行完成后，d[a]^d[b]即为a和b的奇偶关系。

• ①如果属于同一集合，如果我们发现d[a]^d[b]!=ans，我们求得的a、b之间的关系和之前输入的小A所判断a、b间的关系ans相矛盾，则可以确定小A在撒谎。（具体见主代码）

• ②如果不属于同一集合，则合并两个集合，应该进行的操作：

• • 通过find得到两个集合a、b的根节点，设为pa、pb。
• • 若要合并，则先使pa为pb的儿子。
• • 接下来，我们知道d[a]与d[b]分别表示路径a~pa和b~pb之间所有边权的“xor和”，pa~pb之间的边权d[pa]是我们亟待求解的值。
• • 显然路径a~b由a~pa、pa~pb、pb~b三部分组成（在纸上画图就很明了了），因此a和b的奇偶性ans（这里的ans是小A判断的值）=d[a]^d[pa]^d[b]，进行一下数学推导，这一步用到了异或运算的性质：d[pa]=d[a]^d[b]^ans（新连接的边权）。

异或运算的性质：

合并两集合要进行的操作：

if(pa!=pb) _union(pa, pb), d[pa] = d[a]^d[b]^ans;

时间复杂度：

应该是mlogm

代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 2*5000+10;
int p[N], d[N];
int n, m;

struct Query
{
        int l, r;
        int parity;
}query[N];

int idx;
unordered_map<int, int> umi;
int get(int x)
{
        if(!umi.count(x)) return umi[x] = ++idx;
        return umi[x];
}

void init(int n) { for(int i=1;i<=n;++i) p[i] = i; }

int find(int x)
{
        if(p[x]!=x)
        {
//先用一个变量root记录根节点find(p[x])，那么p[x]指向的还会是它的父亲而不是根节点，这时已经递归到了最底层，
//所以一步步冒泡 d[x]+=d[p[x]] 就是将x一直到根节点一段段加起来，最后用完p[x]之后再将p[x]指向根节点。

                int root = find(p[x]);
                d[x]^=d[p[x]];//联系dfs的思想，我们在回溯的时候对x到其所属的根节点路径上所有边权进行异或运算，也可写为：d[x] = (d[x] + d[p[x]]) % 2;
                p[x] = root;//路径压缩
        }
        return p[x];
}

void _union(int pa, int pb) { p[pa] = pb; }

int main()
{
        cin>>n>>m;
        idx = 0;
        for(int i=1;i<=m;++i)
        {
                int l, r; string par;
                cin>>l>>r>>par;
                query[i] = {get(l-1), get(r), par=="odd" ? 1 : 0};//注意啊，我们想要离散化的第一个值是l-1而不是l，联系前缀和的思想就行
        }
        init(idx);
        int res = m;
        for(int i=1;i<=m;++i)
        {
                int a = query[i].l, b = query[i].r, ans = query[i].parity;
                int pa = find(a), pb = find(b);
                if(pa!=pb) _union(pa, pb), d[pa] = d[a]^d[b]^ans;
                else
                {
                        if(d[a]^d[b]!=ans)
                        {
                                res = i-1;
                                break;
                        }
                }
        }
        cout<<res<<endl;

        return 0;
}

扩展域并查集做法

上面讲的“边带权”并查集主要思想是存储相对关系，即当前节点和根的关系，由于关系具有传递性，我们使用 当前节点和根的关系 就可以知道 集合内任意两个元素的关系。

接下来，扩展域并查集做法则换了一种全新的思考方式。

可以看出，扩展域并查集解决此题相对于前两种更加好理解，无需维护d[]数组，也更好写一点，扩展域并查集对于条件来划分集合，引申出x和x+idx点，此处x点表示为x是奇数，x+idx表示x为偶数。

扩展域并查集适合种类不是很多的情况，如果太多显然会导致空间爆炸。典型的以空间换时间思想。

代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 2*2*5000+10;
int p[N];
int n, m;

struct Query
{
        int l, r;
        int parity;
}query[N];

int idx;
unordered_map<int, int> umi;
int get(int x)
{
        if(!umi.count(x)) return umi[x] = ++idx;
        return umi[x];
}

void init(int n) { for(int i=1;i<=n;++i) p[i] = i; }

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

void _union(int pa, int pb) { p[pa] = pb; }

int main()
{
        cin>>n>>m;
        idx = 0;
        for(int i=1;i<=m;++i)
        {
                int l, r; string par;
                cin>>l>>r>>par;
                query[i] = {get(l-1), get(r), par=="odd" ? 1 : 0};//注意啊，我们想要离散化的第一个值是l-1而不是l，联系前缀和的思想就行
        }
        init(2*idx);
        int res = m;
        for(int i=1;i<=m;++i)
        {
                int a = query[i].l, b = query[i].r, ans = query[i].parity;
                int a_odd = a, a_even = a + idx, b_odd = b, b_even = b + idx;

                if(ans == 0)//回答奇偶性相同
                {
                    if(find(a_odd) == find(b_even))//与已知情况矛盾
                    {
                        res = i - 1;
                        break;
                    }
                    _union(find(a_odd), find(b_odd)), _union(find(a_even), find(b_even));//合并
                }

                else
                {
                    if(find(a_odd) == find(b_odd))//与已知情况矛盾
                    {
                        res = i - 1;
                        break;
                    }
                    _union(find(a_odd), find(b_even)), _union(find(a_even), find(b_odd));//合并
                }
        }
        cout<<res<<endl;

        return 0;
}