#离散，并查集#JZOJ 1375（初中） 1779（高中）奇偶游戏 poj 1733 codevs 2546 parity game

首先用s数组来表示这个01序列从第一个开始到第i个的奇偶性。

a b even说明s[b]和s[a-1]的奇偶性相同，否则不同。

当a b even且s[b]和s[a-1]的奇偶性不同或a b odd且s[b]和s[a-1]的奇偶性相同时为错误信息。

离散化+并查集。

#include <cstdio>
#include <algorithm>
using namespace std;
int len,n,p[10001],b[10001],f[10001],x[10001],y[10001],s[10001];
int bs(int u){
    int l=1,r=len,mid;
    while (l<=r){
        mid=(l+r)>>1;
        if (u==p[mid]) return mid;
        if (u>p[mid]) l=mid+1; else r=mid-1;}
}
int getf(int u){
    if (f[u]==u) return u;
    int y=getf(f[u]);
    s[u]=(s[f[u]]+s[u])&1;//改变奇偶
    return f[u]=y;
}
void uni(int i){
    s[f[x[i]]]=(s[x[i]]+b[i])&1;//存储奇偶
    f[f[x[i]]]=y[i];//合并
}
int main(){
    scanf("%*d%d",&n);
    for (int i=1;i<=n;i++){
        char t; scanf("%d%d %c",&x[i],&y[i],&t);
        if (t=='o') b[i]=1; while (getchar()!='\n');//标记奇数（/2余数为1）
        p[(i<<1)-1]=--x[i]; p[i<<1]=y[i]; //存储前面的地址和后面的地址
    } 
    stable_sort(p+1,p+1+2*n); p[0]=1; for (int i=2;i<=2*n;i++) //快排并去重
    if (p[i]!=p[p[0]]) p[++p[0]]=p[i]; len=p[0];
    for (int i=1;i<=len;i++) f[i]=i;
    for (int i=1;i<=n;i++){
        x[i]=bs(x[i]); y[i]=bs(y[i]);//二分查找
        if (getf(x[i])==getf(y[i])){//之前有信息证明
            if (((s[x[i]]+s[y[i]])&1)!=b[i]) {printf("%d",i-1);return 0;}}//奇偶性不同
        else uni(i);}
    printf("%d",n);
    return 0; 
}