描述 Description
huyichen 和 xuzhenyi 在玩一个游戏：他写一个由 0 和 1 组成的序列。
huyichen 选其中的一段（比如第 3 位到第 5 位），问他这段里面有奇数个 1 还是偶数个 1。xuzhenyi 回答你的问题，然后 huyichen 继续问。
xuzhenyi 有可能在撒谎。huyichen 要检查 xuzhenyi 的答案，指出在 xuzhenyi 的第几个回答一定有问题。
有问题的意思就是存在一个 01 序列满足这个回答前的所有回答，而且不存在序列满足这个回答前的所有回答及这个回答。
输入格式 InputFormat
第 1 行一个整数，是这个 01 序列的长度（<=1000000000)
第 2 行一个整数，是问题和答案的个数。
第 3 行开始是问题和答案，每行先有两个整数，表示你询问的段的开始位置和结束位置。然后是 xuzhenyi 的回答。odd 表示有奇数个 1，even 表示有偶数个 1。
输出格式 OutputFormat
输出一行，一个数 X, 表示存在一个 01 序列满足第 1 到第 X 个回答，但是不存在序列满足第 1 到第 X+1 个回答。如果所有回答都没问题，你就输出所有回答的个数。
样例输入 SampleInput
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
样例输出 SampleOutput
3
来源 Source
huyichen
代码 Code
这种类型的并查集好像很少做~~(>_<)~~ 本来想用两个数组分开存 same 和 diff 的，但两个都要考虑到的话找祖先和合并的时候好像很麻烦、、还是用一个数组来的方便。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
const int hmod=271127;
int h[hmod+5];
int fa[2*hmod+5]; //fa[0~hmod]==same[],fa[hmod~2*hmod]==diff[]
char ch[5];
inline int hash(int s)
{
int t=s%hmod;
while (h[t]!=-1 && h[t]!=s) t=(t+1)%hmod;
h[t]=s;
return t;
}
int getfa(int s)
{
if (fa[s]==s) return s;
fa[s]=getfa(fa[s]);
return fa[s];
}
inline void uni(int x,int y)
{
if (getfa(x)!=getfa(y)) fa[getfa(x)]=y;
}
int main()
{
for (i=0;i<=hmod;i++) fa[i]=i,fa[i+hmod]=i+hmod,h[i]=-1;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d%s",&x,&y,ch);
if (strcmp(ch,"even")==0)
{
if (getfa(hash(x-1))==getfa(hash(y)+hmod))
{
printf("%d\n",i-1);
return 0;
}
uni(hash(x-1),hash(y));
uni(hash(x-1)+hmod,hash(y)+hmod);
}
if (strcmp(ch,"odd")==0)
{
if (getfa(hash(x-1))==getfa(hash(y)))
{
printf("%d\n",i-1);
return 0;
}
uni(hash(x-1),hash(y)+hmod);
uni(hash(x-1)+hmod,hash(y));
}
}
printf("%d\n",m);
return 0;
}