题意:一个长度为N(N < 1e9)内的01串，之后有K(K <= 5000)组叙述，表示区间[l,r]之间1的个数为odd还是even；问在第一个叙述矛盾前说了几句话？
Sample Input
10 N
5 K
1 2 even
3 4 odd
5 6 even
1 6 even (错误)
7 10 odd
Sample Output
3
思路:对于判断正误的问题，一定要知道什么情况会导致错误。如样例:当前输入的区间[1,6]的端点均包含于前面输入的端点中时(包含并不是指区间相同而是区间延拓(使用并查集))后可以计算出来该区间的奇偶即可，那么易知并查集中合并的元素就为区间的端点，对端点标记(离散化)之后和hdu3047一样处理下压缩时当前节点到根节点路径中1的奇偶即可；
**区间延拓:原本区间的表示可以[l,r],但是会发现不能将相邻的区间如[1,2]和[3,4]合并(因为区间没有相同的端点)，那么就(l,r]这样就变成了(0,2]&(2,4];可以实现延拓(实现细节)
ps:对于mod2的加减运算，就是XOR,但是全部将mod2替换成XOR竟然用时更长；
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
map<int,int> mp;
const int MAXN = *;
int f[MAXN];
int kind[MAXN];
int Find(int a)
{
if(a == f[a]) return f[a];
int fa = Find(f[a]);
kind[a] ^= kind[f[a]];//这是当前的fa并没有压缩，但是f[fa]已经压缩了，dist[]里面还是要写f[a],而不是fa
return f[a] = fa;
}
bool _union(int u,int v,int d)//union时将区间的奇偶标记在子节点上；
{
int fu = Find(u),fv = Find(v);
if(fu == fv){
if((kind[u] ^ kind[v]) != d) return true;//区间端点XOR得到区间的奇偶；不是[fu] ^[fv]的xor
return false;
}
f[fu] = fv;
kind[fu] = kind[v]^d^kind[u]; //偏移向量 等同于kind[fu] = (kind[v]+d-kind[u]+2)%2;
return false;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
int x,y,id = ,ret;
char s[];
bool flag = false;
rep1(i,,MAXN) f[i] = i,kind[i] = ;
rep0(i,,k){
scanf("%d%d%s",&x,&y,s);//(x-1,y];区间延拓；
if(flag) continue;
int d = (s[] == 'e')?:;
if(mp.find(--x) == mp.end()){
mp[x] = ++id;
}
if(mp.find(y) == mp.end()){
mp[y] = ++id;
}
if(_union(mp[x],mp[y],d)){
ret = i;flag = true;
}
}
printf("%d\n",flag?ret:k);
return ;
}