洛谷P5937 [CEOI1999]Parity Game_学习笔记

rhineofts / 2023-08-28 / 原文

洛谷P5937 [CEOI1999]Parity Game

本来是想练习一下离散化的，结果看到这道又有并查集又有离散化的题，于是就~~逝了逝~~，在阅读题解后，

发现自己对并查集和离散化认识有点问题，于是写下这篇笔记总结一下。

看到这种给出几个条件判断矛盾的题，便想到了两种常见思路，一种是拓扑排序，一种是并查集。这道题由于是区间而不是像 P1347 排序那样几个点的询问，用拓扑应该不好做~~（也可能是我太菜了）~~，我们考虑并查集。

然而，第一眼看上去没有头绪，但区间个数这种形式让我们想到前缀和，进一步思考，发现一个关键性质：

记 s[i] 为前 $ 个数中的数量。若区间中的数量为偶数，那么有 s[r] - s[l - 1] 为偶数，从而 s[r] 与 s[l - 1] 同奇偶，同理，若区间中的数量为奇数，那么有 s[r] 与 s[l - 1] 奇偶性相反。利用这一点，我们可以直接利用并查集判断 s[r] 与 s[l - 1] 的奇偶性是否有矛盾。为此，我们可以标记两个点的奇偶性是否相同，将相同的用并查集合并，不相同的怎么办呢？我们可以将数组扩大成两倍空间，若原来的总数为 , 则 fa[x + n] 用于记录和 fa[x] 奇偶性不同的关系（或更通俗的，敌人。这里可以把奇偶性相同的比作朋友，不相同的比作敌人，且满足敌人的敌人是朋友，敌人的朋友是敌人等关系）。由此我们可以得到下面这个关键代码：$

for (int i = 0; i < m; i++) {
       if (a[i].x == 0) { // 偶数，a[i].l 与 a[i].r 奇偶相同
           if (find(a[i].l) == find(a[i].r + res) or find(a[i].r) == find(a[i].l + res)) {
               cout << i << '\n';
               return 0;
          }
           merge(a[i].l, a[i].r);  
           merge(a[i].l + res, a[i].r + res);
      }
       else { // 奇数，a[i].l 与 a[i].r 奇偶不同
           if (find(a[i].l) == find(a[i].r) or find(a[i].l + res) == find(a[i].r + res)) {
               cout << i << '\n';
               return 0;
          }
           merge(a[i].l, a[i].r + res);
           merge(a[i].r, a[i].l + res);
      }
  }

这样这道题大体思路已出来了，但值域到了 $ ，显然不能直接用值作为下标，为此，我们可以用离散化进行处理。$

所谓离散化，就是把坐标（值，下标）等在保持相对大小不变时，将其映射到一个好处理的范围。例如：

1437 998244353 1000000007 314159 -> 1 3 4 2

实现离散化，可以先排序。由于相同的值离散化后也应相同，为此，最简单高效的方法是直接去重。

下面给出本题离散化代码，其他题的离散化部分也是类似思路：

sort(b, b + tot); // 排序
int res = unique(b, b + tot) - b; //去重
for (int i = 0; i < m; i++) { //由于排序 + 去重后元素满足单调性且不存在相同值，正好使用二分查找来找到离散化后的位置
   a[i].l = lower_bound(b, b + res, a[i].l) - b;
   a[i].r = lower_bound(b, b + res, a[i].r) - b; //注意这里l, r离散化时不应做区分（即对l，r分别做）只要相对位置对了就行了，不明白可以手动做几组模拟一下离散化过程（这种~~弱智~~问题不会只有我一开始不明白吧）
}

下面是本题完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
const int N = 5e3 + 10;
struct node{
   int l;
   int r;
   int x;
} a[N];
int b[N * 2], tot; //两倍空间是因为l, r都要存
int fa[N * 4]; //四倍空间是要考虑到端点对应的那个“敌人”
int find(int x) {
   while (x != fa[x]) x = fa[x] = fa[fa[x]];
   return x;
}    // 递归形式 : if (x == f[x]) {return x;} return f[x] = find(f[x]);
void merge(int a, int b) {
   fa[find(a)] = find(b);
}
int main() {
   cin.tie(0)->sync_with_stdio(0);
   cin >> n >> m;
   string str;
   for (int i = 0; i < m; i++) {
       cin >> a[i].l >> a[i].r >> str;
       a[i].l--;
       b[tot++] = a[i].l;
       b[tot++] = a[i].r;
       a[i].x = str.size() % 2; //一个没用的东西:even 和 odd 所对应的奇偶性与其长度的奇偶性一致
  } //其实可以直接比较首字符号
   sort(b, b + tot); //离散化，详细见上
   int res = unique(b, b + tot) - b;
   for (int i = 0; i < m; i++) {
       a[i].l = lower_bound(b, b + res, a[i].l) - b;
       a[i].r = lower_bound(b, b + res, a[i].r) - b;
  }
   for (int i = 1; i <= 2 * res; i++) { //并查集初始化
       fa[i] = i;
  }
   for (int i = 0; i < m; i++) { //处理，详细见上
       if (a[i].x == 0) {
           if (find(a[i].l) == find(a[i].r + res) or find(a[i].r) == find(a[i].l + res)) {
               cout << i << '\n';
               return 0;
          }
           merge(a[i].l, a[i].r);  
           merge(a[i].l + res, a[i].r + res);
      }
       else {
           if (find(a[i].l) == find(a[i].r) or find(a[i].l + res) == find(a[i].r + res)) {
               cout << i << '\n';
               return 0;
          }
           merge(a[i].l, a[i].r + res);
           merge(a[i].r, a[i].l + res);
      }
  }
   cout << m << '\n';
   return 0;
}