1204 Parity
题目来源： Ural
基准时间限制：1 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
你的朋友写下一串包含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
/*
51nod 1204 Parity(并查集应用)
problem:
你可以从中选择一个连续的01子串,然后是q个询问和回答. 表示区间[l,r]中有奇数或者偶数个1. 求第一个出现矛盾的位置
solve:
考虑了下线段树什么的,发现并不怎么靠谱. 没做过类似的,完全没想到并查集,卒.....
如果[l,r]是even,那么[1,l-1]和[1,r]中1的个数都是偶数 or 奇数.
如果[l,r]是odd,那么 [1,l-1] 和 [1,r]的奇偶性不同.
就转换成了判断前缀和的问题
所以用[1,n]表示'相同'关系,[n+1,2*n]虚拟表示'不同'关系.建立两个集合
判断 (l-1+n,r) && (l-1,b+n) 就能确定 l-1和r是否为'相同'关系. 其它同理
hhh-2016/09/06-20:47:14
*/
#pragma comment(linker,"/STACK:124000000,124000000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#define lson i<<1
#define rson i<<1|1
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
#define scanfi(a) scanf("%d",&a)
#define scanfs(a) scanf("%s",a)
#define scanfl(a) scanf("%I64d",&a)
#define scanfd(a) scanf("%lf",&a)
#define key_val ch[ch[root][1]][0]
#define eps 1e-7
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const ll mod = 1000000007;
const int maxn = 300050;
const double PI = acos(-1.0);
const int limit = 33;
int pre[maxn];
template<class T> void read(T&num)
{
char CH;
bool F=false;
for(CH=getchar(); CH<'0'||CH>'9'; F= CH=='-',CH=getchar());
for(num=0; CH>='0'&&CH<='9'; num=num*10+CH-'0',CH=getchar());
F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p)
{
if(!p)
{
puts("0");
return;
}
while(p) stk[++ tp] = p%10, p/=10;
while(tp) putchar(stk[tp--] + '0');
putchar('
');
}
int fin(int x)
{
if(pre[x ]== x) return x;
return pre[x] = fin(pre[x]);
}
void unio(int a,int b)
{
int ta= fin(a);
int tb = fin(b);
pre[ta] = tb;
}
char op[10];
int main()
{
// freopen("in.txt","r",stdin);
int n,q,flag = 0;
int a,b;
read(n);
read(q);
for(int i = 0;i <= 2*n;i++)
pre[i] = i;
for(int i = 1; i <= q; i++)
{
scanf("%d%d%s",&a,&b,op);
if(flag)
continue;
if(op[0] == 'e')
{
if(fin(a-1+n) == fin(b) && fin(a-1) == fin(b + n))
{
flag = i;
}
unio(a-1,b);
unio(a-1+n,b+n);
}
else
{
if(fin(a-1) == fin(b) && fin(a-1+n) == fin(b+n))
{
flag = i;
}
unio(a-1+n,b);
unio(a-1,b+n);
}
}
if(flag)
printf("%d
",flag);
else
printf("-1
");
return 0;
}