H - Parity game-poj1733（需要离散化）

题意：给一个序列这个序列都是由0和1组成，现在随意拿出来一个序列，然后说出他的和是奇数还是偶数，因为有可能存在假话，让你判断前多少条没有假话，也就是查找第一个假话的位置-1

//

这道题很像D题，都是线段区间，不过数据比较大，需要离散化一下。

#include <stdio.h>
#include<algorithm>
using namespace std;

const int maxn = 100005;

int f[maxn], val[maxn];//val记录区间奇偶值
int p[maxn];//p数组保存需要离散化的数据

struct node{int u, v, sum;}a[maxn];//保存输入

int Find(int x)
{
    int k = f[x];

    if(f[x] != x)
    {
        f[x] = Find(f[x]);
        val[x] = (val[x]+val[k])%2;
    }

    return f[x];
}

int main()
{
    int N;

    while(scanf("%d", &N) != EOF)
    {
        int i, M, k=0;
        char s[10];

        scanf("%d", &M);

        for(i=0; i<M; i++)
        {
            scanf("%d%d%s", &a[i].u, &a[i].v, s);
            a[i].sum = (s[0] == 'e' ? 0 : 1);
            //为防止不在两个不相邻的数离散化后相邻，在他们中间加一个数
            p[k++] = a[i].u, p[k++] = a[i].u-1;
            p[k++] = a[i].v, p[k++] = a[i].v-1;
        }
        p[k++] = N, p[k++] = N-1;
        sort(p, p+k);
        N = unique(p, p+k) - p;//去重复函数

        for(i=0; i<N; i++)
            f[i] = i, val[i] = 0;

        for(i=0; i<M; i++)
        {
            int u = lower_bound(p, p+N, a[i].u-1) - p;//二分查询
            int v = lower_bound(p, p+N, a[i].v) - p;

            int ru = Find(u), rv = Find(v);

            if(ru == rv && (val[u]+a[i].sum)%2 != val[v])
                break;
            if(ru < rv)
            {
                f[rv] = ru;
                val[rv] = (val[u]+a[i].sum-val[v]+2)%2;
            }
            else if(ru > rv)
            {
                f[ru] = rv;
                val[ru] = (val[v]-a[i].sum-val[u]+2)%2;//注意别写错val里面的参数
            }
        }

        printf("%d\n", i);
    }

    return 0;
}