POJ 1733 Parity Game

前缀知识

思路

离散化：

由于 $n$ 太大，但查询最多只有 $5e3$ 次，所以最多只有 $1e4$ 个不同的数，先将查询的区间两端编号离散化。
读入时将区间 $[x,y]$ 变为区间 $(x-1,y]$（这两个是等价的），离散化时加入离散数组 $hush$ 的两个数是 $x-1$ 和 $y$ 而不是 $x$ 和 $y$（至于为什么这么做等会会说）。

并查集：

并查集是此题核心思路，用到的是带权并查集。

我们将每个位置视为并查集生成树中的一个节点，最开始每个节点之间互无连线且都以自己为根节点。

现在读入处理好的第一个操作，说某个区间 $(x,y]$ 中 $1$ 数量的奇偶性（由于离散化时左端点左移了一位，因此是左开右闭区间），我们就将节点 $x$ 和 $y$ 连在一起（即 $fa[y]=x$）。现在 $x$ 就是 $y$ 所在并查集生成树的根节点（由于这是第一个操作，所以该生成树中就 $x$ 和 $y$ 两个节点）。
此时我们用一个数组 $d[u]$ 记录节点 $u$ 到其所在并查集生成树的根节点的距离（距离的定义就是：该节点到根节点所代表区间 $“1"$ 个数的奇偶性，取值范围就是 $d[u]\in ｛0,1｝$，$1$ 表示奇数，$0$ 表示偶数），那么 $d[y]=1$ 。

在接下来每次操作中，每读入一组 $x,y$（代表查询的区间是 $(x,y]$），就看看他们是否在同一个并查集中。
若是，那么我们就可以先分别知道【$x$ 到根节点的距离】与【$y$ 到根节点的距离】，也就是它们所代表区间 $1$ 的奇偶个数，再由 " 奇数 $+$ 奇数 $=$ 偶数，奇数 $+$ 偶数 $=$ 奇数 " 判断出区间 $(x,y]$ 中 $1$ 的奇偶个数，看看是否符合数据所给，不符就直接输出；
若不是，就将 $x$ 所在并查集与 $y$ 所在并查集合并。

合并细节：

设 $fx$ 为 $x$ 所在并查集的根节点，$fy$ 为 $y$ 所在并查集的根节点。
先如普通并查集一般，让 $fa[fy]=fx$，
再更新 $fy$ 到根节点的距离，让 $d[fy]=d[x]\oplus d[y]\oplus op$ （$\oplus$ 是异或，$op$ 是数据给的 $(x,y]$ 内 $“1”$ 个数的奇偶性）。

为什么是这样呢？
我们将两个区间合并，实际上是推出 $fy$ 到 $fx$ 距离。

如下图，$w$ 就是我们要求的 $d[fy]$。
（图片上传不上去，以后再补）
很显然 $w\oplus d[y]=d[x]\oplus op$，再给两边同时异或 $d[y]$，就变成了上述式子。

代码

#include <bits/stdc++.h>

#define mkpr make_pair

using namespace std;


typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int maxn = 5e3 + 7;
const int inf  = 0x3f3f3f3f;

int n, m; 
struct Query {
	int x, y, op;
} q[maxn];

int hcnt, hush[maxn << 1];
unordered_map<int, int> ump;

int fa[maxn], d[maxn];
int find(int x) {
	if (x != fa[x]) {
		int rtx = find(fa[x]);
		d[x] ^= d[fa[x]];
		fa[x] = rtx;
	}
	return fa[x];
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		char opt[5];
		scanf("%d%d%s", &q[i].x, &q[i].y, opt);
		q[i].op = (opt[0] == 'o' ? 1 : 0);  // 1 表示奇数, 0 表示偶数 
	    --q[i].x;
	    hush[++hcnt] = q[i].x, hush[++hcnt] = q[i].y;
	}
	
	// 离散化 
	sort(hush + 1, hush + hcnt + 1);
	hcnt = unique(hush + 1, hush + hcnt + 1) - hush - 1;
	for (int i = 1; i <= hcnt; ++i) 
	    ump[hush[i]] = i;
	for (int i = 1; i <= m; ++i)
	    q[i].x = ump[q[i].x],
	    q[i].y = ump[q[i].y];
	
	for (int i = 1; i <= hcnt; ++i) 
		fa[i] = i, d[i] = 0;
	
	for (int i = 1; i <= m; ++i) {
		int x = q[i].x, y = q[i].y;
		int fx = find(x), fy = find(y);
		
		if (fx == fy) {  // 判断是否合法
			if (d[x] == d[y] && q[i].op == 1) {
				printf("%d", i - 1);
				return 0;
			} 
			if (d[x] != d[y] && q[i].op == 0) {
				printf("%d", i - 1);
				return 0;
			}
		} else {  // 合并
		    fa[fy] = fx;
			d[fy] = d[x] ^ d[y] ^ q[i].op; 
		}
	}
	printf("%d\n", m);
	return 0;
}