B - Parity

题目：

你的朋友写下一串包含1和0的串让你猜，你可以从中选择一个连续的子串（例如其中的第3到第5个数字）问他，该子串中包含了奇数个还是偶数个1，他会回答你的问题，然后你可以继续提问......你怀疑朋友的答案可能有错，或说同他之前的答案相互矛盾，例如：1 - 2 奇数，3 - 4 奇数，那么可以确定1 - 4 一定是偶数，如果你的朋友回答是奇数，就产生了矛盾。给出所有你朋友的答案，请你找出第一个出现矛盾的答案。

Input

第1行：2个数N, Q，N为串的长度，Q为询问的数量。（2 <= N <= 100000, 2 <= Q <= 50000) 
第2 - Q + 1行：每行包括两个数以及一个字符串来描述朋友的回答，2个数中间用空格分隔，分别表示区间的起点和终点，后面的字符为"even"或"odd"，表示朋友的答案。

Output

输出1个数，表示朋友的答案中第一个错误答案的位置，如果所有答案均不矛盾，则输出-1。

Sample Input

10 5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

Sample Output

4

思路:

如果[aa,bb]是even,那么[1,aa-1]和[1,bb]中1的个数都是偶数 或奇数(奇偶性相同).
如果[aa,bb]是odd,那么 [1,aa-1] 和 [1,bb]的奇偶性不同.就转换成了判断前缀和的问题
所以用[1,n]表示‘相同‘关系,[n+1,2*n]虚拟表示‘不同‘关系.

建立两个集合判断 (aa-1+n,bb) && (aa-1,bb+n) 就能确定aa-1和bb是否为‘相同‘关系.

代码如下：

#include<stdio.h>
#include<string.h>
#define N 200010

int n,m,aa,bb;
int f[N];
char a[10];

void init()//初始化，自己的祖宗是自己；
{
    for(int i=0;i<N;i++)
        f[i]=i;
    return ;
}

int getf(int v)//找祖宗；
{
    if(f[v]==v)
        return v;
    else
        return f[v]=getf(f[v]);
}

void merge(int u,int v)//合并；
{
    int t1=getf(u);
    int t2=getf(v);
    if(t1!=t2)
        f[t2]=t1;
    return ;
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(f,0,sizeof f);
        int flag=0;
        int i,j,ans=-1;
        init();
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%s",&aa,&bb,a);
            if(flag==1)
               continue;
            if(strcmp(a,"even")==0)//偶数；
            {
                if(getf(aa-1)==getf(bb+n)&&getf(aa-1+n)==getf(bb))
                {
                    flag=1;
                    ans=i;
                }
                else//合并；
                {
                    merge(aa-1,bb);
                    merge(aa-1+n,bb+n);
                }
            }
            else//奇数；
            {
                if(getf(aa-1)==getf(bb)&&getf(aa-1+n)==getf(bb+n))
                {
                    flag=1;
                    ans=i;
                }
                else//合并；
                {
                    merge(aa-1,bb+n);
                    merge(aa-1+n,bb);
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}