#题目描述
Sam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2×2的方形区 域都包含奇数个（1个或3个）红色方格。 可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍然满足她们的要求。如果可能的话，满足他们要求的染色方案数有多少呢？
#做法
见代码下注释
#复杂度分析 \(O(K)\)其中每个点访问一次，利用平衡树，每次压入、查询前驱、查询后继、删除操作都是\(O(\log N)\)的
#AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxk=100005,maxn=200005,mod=1000000000;
int n,m,k;
int q[maxk][3];
int si11;
int gr[maxn],si[maxn];
int ex;
int find(int e,int &s)
{
if (gr[e]<=0)
{
s=0;
return e;
}
gr[e]=find(gr[e],s);
si[e]^=s;
s=si[e];
return gr[e];
}
bool uni(int e1,int e2,int s)
{
int s1,s2;
int g1=find(e1,s1),g2=find(e2,s2);
if (g1==g2)
{
return (s1^s2)==s;
}
if (gr[g1]>=gr[g2])
{
if (gr[g1]==gr[g2])
gr[g2]--;
si[g1]=(s1^s2^s);
gr[g1]=g2;
}else
{
si[g2]=(s1^s2^s);
gr[g2]=g1;
}
ex--;
return true;
}
long long Pow(long long n,long long k)
{
long long r=1;
for (;k;(n*=n)%=mod,k>>=1)
if (k&1)
(r*=n)%=mod;
return r;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
uni(n+m+1,n+m+2,1);
ex=n+m-1;
for (int i=1;i<=k;i++)
{
scanf("%d%d%d",&q[i][0],&q[i][1],&q[i][2]);
if (q[i][0]==1 && q[i][1]==1 && q[i][2]==1)
si11=1;
}
for (int i=1;i<=k;i++)
{
int r=q[i][0],c=q[i][1],co=q[i][2];
if (r==1)
{
if (!uni(c,n+m+1+(co^si11),0))
{
printf("0\n");return 0;
}
}else if (c==1)
{
if (!uni(m+r,n+m+1+(co^si11),0))
{
printf("0\n");return 0;
}
}else
{
int cco=!(r&1)&&!(c&1);
if (!uni(c,m+r,co^cco^si11))
{
printf("0\n");return 0;
}
}
}
printf("%lld\n",Pow(2,ex));
return 0;
}
/**************************************************************************\
apio2011 棋盘染色
并查集
+ . . . . | . . . .
. . . . . v . . . .
. . . . . ' . . . .
->''''''''* . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
如上图，一个点(x,y)的颜色可以由(1,1)['+'],(x,1)['|'],(1,y)['-']唯一确定
跟据题目所给的条件，我们可以确定若干对诸如“(x,1)和(1,y)必须相同”的东西
用并查集维护它，如果遇到矛盾的信息，答案显然为0
\*************************************************************************/