题意：
一个长度为n的0,1字符串，给出m行数据，每行数据给出区间[xi,yi]内的1的个数为奇数个或者偶数个。
输出最小k，使得前k行数据不矛盾。
题解：
带权并查集类型题：
区间[xi,yi]内1的个数为偶数个，代表区间[1,xi-1]，[1,yi]内含1的个数同奇偶，xi-1,yi种类相同
反之异奇偶，种类不相同。
于是种类并查集！
注意：给的 5000种语句，但是却有最大a为10亿，所以要离散化！！！
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<functional>
#include<utility>
#include<set>
#include<map>
#include<cmath>using namespace std;const int maxn=5010;int pa[maxn];
int d[maxn];//0同奇偶，1异奇偶。int ans;int findset(int x)
{int root;if(pa[x]==-1)return x;else{root=findset(pa[x]);d[x]=(d[x]+d[pa[x]])%2;return pa[x]=root;}
}bool unionset(int x,int y, int l)
{int rootx=findset(x);int rooty=findset(y);if(rootx==rooty){if((d[x]-d[y]+2)%2!=l)return false;return true;}else{pa[rootx]=rooty;d[rootx]=(d[y]-d[x]+l+2)%2;return true;}
}int main()
{int n,m;while(cin>>n>>m){memset(pa,-1,sizeof(pa));memset(d,0,sizeof(d));map<int, int>mp;bool flag=true;int ans=m;int k=0;for(int i=0;i<m;i++){ int a,b;char s[10];scanf("%d%d%s",&a,&b,s);if(!flag)continue;int l=(s[0]=='e'?0:1);b++;if(mp.find(a)==mp.end())mp[a]=k++;//离散化！if(mp.find(b)==mp.end())mp[b]=k++;if(!unionset(mp[a],mp[b],l)){flag=false;ans=i;}}cout<<ans<<endl;}
}