Parity game
边带权并查集与扩展域并查集。
首先我们有一个基本想法，那就是把区间和的奇偶性转变为两个前缀和的奇偶关系。
简单来说，设 $c(x)$ 为这个序列的前缀和。
如果说 $c(r)-c(l-1)$ 为偶数，则 $c(r)$ 和 $c(l-1)$ 是奇偶性相同的。
如果说 $c(r)-c(l-1)$ 为奇数，则 $c(r)$ 与 $c(l-1)$ 是奇偶性不同的。
那么离散化询问后，我们考虑使用并查集解决问题。
先说边带权。这里设 0 为与其奇偶性相同，1 为与其奇偶性不同。
那么边权一路异或到树根就是 $x$ 与树根的奇偶性关系。
每次合并之前，我们先用 Get 检查 $x$ 和 $y$ 是否在同一个集合内（顺便得到 $d(x)$ 与 $d(y)$，即两者分别与树根的奇偶性关系），如果是的话，$d(x)\operatorname{xor} d(y)$ 即为 $x$ 与 $y$ 的奇偶关系。那么此时如果输入给出的奇偶关系与其不符的话，这个时刻就是答案；反之，跳过。
如果两者不在同一集合中，我们就要考虑合并。
假设 $u$ 是 $x$ 的祖先，$v$ 是 $y$ 的祖先，不妨将 $u$ 连为 $v$ 的子节点。
那么 $d(u)$ 即 $u$ 与 $v$ 的奇偶关系，由于我们给出的奇偶关系 $ans=d(x)\operatorname{xor} d(u)\operatorname{xor} d(y)$，移项就能得到 $d(u)=d(x)\operatorname{xor}d(y)\operatorname{xor} ans$。
于是我们就可以很好的维护整个并查集系统了。
代码（边带权并查集）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x){write(x);putchar(10);}
const ll N=1e6;
ll n,m,amt;
ll fa[N+5],d[N+5],uq[N+5];
struct Qry{ll l,r,ans;}q[N+5];
inline ll Get(ll x) {
if(x==fa[x]) return x;ll rt=Get(fa[x]);d[x]^=d[fa[x]];return fa[x]=rt;
}
int main() {
n=read();m=read();
for(ll i=1;i<=m;i++) {
q[i].l=read();q[i].r=read();char op[5];scanf("%s",op);
if(op[0]=='o') q[i].ans=1;else q[i].ans=0;
uq[++amt]=q[i].l-1;uq[++amt]=q[i].r;
}
sort(uq+1,uq+amt+1);amt=unique(uq+1,uq+amt+1)-uq-1;
for(ll i=1;i<=amt;i++) fa[i]=i;
ll flg=0;
for(ll i=1;i<=m;i++) {
ll x,y;
x=lower_bound(uq+1,uq+amt+1,q[i].l-1)-uq;
y=lower_bound(uq+1,uq+amt+1,q[i].r)-uq;
ll u=Get(x),v=Get(y);
if(u==v) {
if((d[x]^d[y])!=q[i].ans) {writeln(i-1);flg=1;break;}
}
else {fa[u]=v;d[u]=d[x]^d[y]^q[i].ans;}
}
if(!flg) writeln(m);
return 0;
}
|
我们还有另一种思路，就是扩展域并查集。
把每个点 $x$ 拆成两个点 $x_{odd}$ 和 $x_{even}$，分别表示 $x$ 是奇数和 $x$ 是偶数这两个命题。
那么连边变成了条件可以相互推出，那么我们的思路就简单很多，只要判断与给出条件矛盾的命题在并查集系统中是否成立，就能够得到答案。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x){write(x);putchar(10);}
const ll N=1e6;
ll n,m,amt;
ll fa[N+5],uq[N+5];
struct Qry{ll l,r,ans;}q[N+5];
inline ll Get(ll x) {
if(x==fa[x]) return x;return fa[x]=Get(fa[x]);
}
int main() {
n=read();m=read();
for(ll i=1;i<=m;i++) {
q[i].l=read();q[i].r=read();char op[5];scanf("%s",op);
if(op[0]=='o') q[i].ans=1;else q[i].ans=0;
uq[++amt]=q[i].l-1;uq[++amt]=q[i].r;
}
sort(uq+1,uq+amt+1);amt=unique(uq+1,uq+amt+1)-uq-1;
for(ll i=1;i<=amt*2;i++) fa[i]=i;
ll flg=0;
for(ll i=1;i<=m;i++) {
ll u,v;
u=lower_bound(uq+1,uq+amt+1,q[i].l-1)-uq;
v=lower_bound(uq+1,uq+amt+1,q[i].r)-uq;
ll u_odd=u,u_even=u+amt;
ll v_odd=v,v_even=v+amt;
if(q[i].ans==0) {
if(Get(u_odd)==Get(v_even)) {
writeln(i-1);flg=1;break;
}
fa[Get(u_odd)]=Get(v_odd);fa[Get(u_even)]=Get(v_even);
}
else {
if(Get(u_odd)==Get(v_odd)) {
writeln(i-1);flg=1;break;
}
fa[Get(u_odd)]=Get(v_even);fa[Get(u_even)]=Get(v_odd);
}
}
if(!flg) writeln(m);
return 0;
}
|