奇偶游戏

并查集 带权并查集 T3 239. 奇偶游戏 - AcWing题库

题目

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

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

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

数据范围

$N\le 10^9,M\le 5000$

输入样例：

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

输出样例：

3

思路

既然是区间问题, 可以定义 $S_i$ 为 $1-i$ 的数中有多少个1, 且我们没必要真的统计有多少个, 只需要记录当前的奇偶属性, 故可以 $\mathrm{mod}2$ 。

进一步分析可得, 若 $S[l,r]$有奇数个1, 即 $S_r-S_{l-1}$ 为奇数。根据奇偶性质, 同奇同偶为偶数, 不同为奇数的性质, 若差为奇数, 说明 $S_r和S_{l-1}$的奇偶性不同。 反过来, 若有偶数个1, 则 $S_r$ 和 $S_l-1$ 奇偶性相同。

于是问题转化为, 给 m 个 $S[l,r]$ 值, 判断哪一步构成了自环。即当 $S_r$ 和 $S_{l-1}$ 奇偶性既相同又不同时出错。

对于这种两个点之间有多种关系, 可以用带权并查集来做, 典型的例子是食物链一题, 本题只有两种关系。

具体实现思想是, 定义 $d_x$ 为 $x$ 点相对于 $p_x$ 根节点的关系, 该题中就是0, 1, 0代表同类, 1代表不同类。

而对于任意两点 $x,y$, 若其在一个并查集内, 即具有同一个根： 那么 两点的关系就是 $d_x+d_y$。比如当x为偶数, 根为偶数, 而y为奇数, 对应的式子就是 0 + 1 = 1 不同类。

并查集能做的题目大多具有传递性, 且为无向边。

接着开始处理询问, 若给出的 $S[x,y]$ 为偶数, 即是同一类, 分两种情况：

• $x,y$ 在同一集合内, $p_x==p_y$ , 此时若 $d_x\wedge d_y$ 为 0 则正确, 为 1 则冲突
• $x,y$ 不在同一集合内, 将其合并即可, 合并时需要确定 $p_x$ 连向 $p_y$ 的边的权值, 这里为了保证是同一类, 即权值和为偶数, $d_x\wedge d_{px}\wedge d_y=0$ , 因此只需要连一条 $d_x\wedge d_y$ 的边即可。 若给出的 $S[x,y]$ 为奇数, 即是不同类, 也分两种情况：
• $x,y$ 在同一集合内, 此时若 $d_x\wedge d_y$ 为 1 则正确, 为 0 则冲突
• $x,y$ 不在一集合内, 合并时 $p_x$ 连向 $p_y$ 的边需要保证为不同类, 即权值和为奇数, 满足 $d_x\wedge d_{px}\wedge d_y=1$, 故 $d_{px}$ 为 $d_x\wedge d_y\wedge 1$ 。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <unordered_map>
using namespace std;
const int N = 5e4 + 10;
unordered_map<int,int> S;
int f[N], d[N], n;
 
int find(int x) {
    if(x != f[x]) 
    {
        int root = find(f[x]);
        d[x] = d[x] ^ d[f[x]];
        f[x] = root;
    }
    return f[x];
}
 
int get(int x)
{
    if(S.count(x) == 0) S[x] = ++n;
    return S[x];
}
 
int main()
{
    int m, res = 0;
    cin >> m;
    
    for(int i = 1; i < N ;i ++) f[i] = i, d[i] = 0;
    cin >> m;
    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);
        
        int t = 0;
        if(type == "odd") t = 1;
        
        int pa = find(a), pb = find(b);
        if(pa == pb)
        {
            if((d[a] ^ d[b]) != t)
            {
                res = i - 1;
                break;
            }
        }
        else {
            d[pa] = d[a] ^ d[b] ^ t;
            f[pa] = pb;
        }
    }
    
    cout << res << endl;
    return 0;
}