【poj1733】 Parity game

http://poj.org/problem?id=1733 (题目链接)

题意

　　一个由0,1组成的序列，每次给出一段区间的奇偶，问哪一条信息不合法。

Solution

　　并查集。

　　题目中序列的长度有很大，单纯搜索一定会TLE。

　　我们用s[i]表示前i个数的前缀和，那么a b even意味着s[b]和s[a-1]的奇偶性相同。a b odd意味着s[b]与s[a-1]的奇偶性不同。于是我们根据奇偶性的不同，用并查集依次处理他们之间的关系。当某条信息出现与并查集中记录的信息不符合时，则此信息不合法。

　　由于a和b的值可能会非常大，所以我们还需要将它离散化。

代码

// poj1733

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi 3.1415926535898

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

int n,m,p[1000010],fa[1000010],s[1000010],x[1000010],y[1000010],pos[1000010],cnt;

char ch[10];

int binsearch(int x) {

	int tl=1,tr=cnt;

	while (tl<=tr) {

		int m=(tl+tr)>>1;

		if (x==pos[m]) return m;

		if (x>pos[m]) tl=m+1;

		else tr=m-1;

	}

}

int find(int x) {

	if (fa[x]==x) return x;

	int f=find(fa[x]);

	s[x]=(s[fa[x]]+s[x])&1;

	fa[x]=f;

	return fa[x];

}

void unnion(int i) {

	s[fa[x[i]]]=(s[x[i]]+p[i])&1;

	fa[fa[x[i]]]=y[i];

}

int main() {

	scanf("%d%d",&m,&n);

	for (int i=1;i<=n;i++) {

		scanf("%d%d",&x[i],&y[i]);

		scanf("%s",ch);

		if (ch[0]=='o') p[i]=1;

		x[i]--;

		pos[++cnt]=x[i];

		pos[++cnt]=y[i];

	}

	sort(pos+1,pos+1+cnt);

	pos[0]=1;

	for (int i=2;i<=cnt;i++) if (pos[i]!=pos[pos[0]]) {pos[0]++;pos[pos[0]]=pos[i];}

	cnt=pos[0];

	for (int i=1;i<=cnt;i++) fa[i]=i;

	for (int i=1;i<=n;i++) {

		x[i]=binsearch(x[i]);

		y[i]=binsearch(y[i]);

		if (find(x[i])==find(y[i])) {if (((s[x[i]]+s[y[i]])&1)!=p[i]) {printf("%d",i-1);return 0;}}

		else unnion(i);

		}

	printf("%d",n);

	return 0;

}