题目大意：有一个长度为n的0,1字符串, 给m条信息，每条信息表示第x到第y个字符中间1的个数为偶数个或奇数个, 若这些信息中第k+1是第一次与前面的话矛盾, 输出k;
思路：x， y之间1的个数为偶数个, 那么1~x 与1~y中1的个数奇偶性相同；若x，y间1的个数为奇数个，那么1~x与1~y中1的奇偶性相同。奇偶性相同的加入同一个并查集
eg：数据范围大，先离散化
#include<stdio.h>
#include<algorithm>
#define N 100006
using namespace std;
struct Node
{
int u,v;
char str[];
}que[N];
int a[N*],n,q,cnt;
int pre[N*],r[N*];
int Bin(int x)
{
int low=,high=cnt-,mid;
while(low<=high)
{
mid=(low+high)/;
if(a[mid]==x) return mid;
if(a[mid]<x) low=mid+;
else high=mid-;
}
return ;
}
int find(int x)
{
if(x!=pre[x])
{
int f=pre[x];
pre[x]=find(pre[x]);
r[x]=r[x]^r[f];
}
return pre[x];
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
scanf("%d",&q);
cnt=;
for(int i=;i<q;i++)
{
scanf("%d%d%s",&que[i].u,&que[i].v,&que[i].str);
que[i].u--;
a[cnt++]=que[i].v;a[cnt++]=que[i].u;
}
sort(a,a+cnt);
cnt=unique(a,a+cnt)-a;
for(int i=;i<cnt;i++) pre[i]=i,r[i]=;
int ans=;
for(int i=;i<q;i++)
{
int u=Bin(que[i].u),v=Bin(que[i].v);
int ra=find(u),rb=find(v);
if(ra==rb)
{
if(r[u]==r[v]&&que[i].str[]=='o') break;
if(r[u]!=r[v]&&que[i].str[]=='e') break;
ans++;
}
else
{
if(que[i].str[]=='o')
{
pre[ra]=rb;
r[ra]=r[u]^r[v]^;
}
else
{
pre[ra]=rb;
r[ra]=r[u]^r[v];
}
ans++;
}
}
printf("%d\n",ans);
}
return ;
}