拓展域并查集_扩展域并查集

拓展域并查集

拓展域并查集。就是通过“拓展域”的方式，将一个点的多个情况拆解成多个仅有单一状态的点，从而将问题转化为可用并查集维护的形式。
例题：P5937 [CEOI1999]Parity Game
将条件通过前缀和（设为sum[x])转化为以下形式：
[l,r]之间1的个数为奇数/偶数 --> sum[l-1]与sum[r]的奇偶性不同/相同
这样做转化后，这个问题就转化为“团伙问题”模型。但是由于要介绍拓展域并查集，故暂且将“设立敌人集合”的做法放置，讲解拓展域并查集
将"sum[x]为奇数或偶数“拆解成”sum[x]为奇数“和"sum[x]为偶数”两个条件，对每一个情况设一个点(分别设为X[odd],X[even])，当sum[x]与sum[y]之间的关系为奇偶性不同时，将x[odd]与y[even]，y[odd]与x[even]做并集。关系为奇偶性相同时，则将x[odd]与y[odd],x[even]与y[even]做并集，表明两种情况必定同时出现。当需要判定合法性时，若 x[odd]与y[odd]在同一集合，说明奇偶性相同，反之亦然。
讲解到这里就会发现，“团伙问题”中的“建立敌对集合”的方法就是一种拓展域并查集。

#include<bits/stdc++.h>
using namespace std;//拓展域并查集 
#define il inline
#define re register
il int read()
{
   
	int s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){
    if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){
    s=(s<<1
1
2
3
4
5
6
7
8
9
10
11