题意:一个长度为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 = 5050*2; 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 = 0,ret; char s[5]; bool flag = false; rep1(i,0,MAXN) f[i] = i,kind[i] = 0; rep0(i,0,k){ scanf("%d%d%s",&x,&y,s);//(x-1,y];区间延拓； if(flag) continue; int d = (s[0] == 'e')?0:1; 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 ",flag?ret:k); return 0; }