51nod - 1204 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。

Input示例

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

Output示例

4

思路：

并查集。sum[i]表示前缀和的奇偶性，如果l-r为偶数，则sum[l-1]与sum[r]奇偶性相同。这时可将l-1和r合并，将l-1+n和r+n合并。否则若l-r为奇数，则将l-1与r+n合并，将r与l-1+n合并。为奇数时举例：长度为6， 1-2为odd，则0指向2+6=8，2指向0+6=6；3-4为odd，则2指向4+6=10，4指向2+6=8。这时0和4均指向8，说明sum[0]和sum[4]的奇偶性一样。

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
 
int fa[200010], n, q; 
char o[5];
 
int find(int x)
{ 
	if (x != fa[x])
	{
		fa[x] = find(fa[x]);
	}
 
	return fa[x];
}
 
void merge(int x, int y)
{
	fa[find(x)] = find(y); 
}
 
int main()
{ 
	scanf("%d%d", &n, &q); 
    for (int i = 1; i <= n << 1; ++i) 
	{
		fa[i] = i;
	}
 
	int l, r;
    for (int t = 1; t <= q; t++)
	{ 
		scanf("%d%d%s", &l, &r, o); 
		l--;
        if (*o == 'e')
		{
            if (find(l) == find(r + n)) 
			{
				printf("%d", t);
				return 0;
			}
            else if (find(l) != find(r))
			{
				merge(l, r);
				merge(l + n, r + n);
			}
        } 
		else 
		{
            if (find(l) == find(r)) 
			{
				printf("%d",t);
				return 0;
			}
            else if (find(l) != find(r + n)) 
			{
				merge(l, r + n);
				merge(r, l + n);
			}
        }
    } 
	puts("-1");
 
	return 0;
}