题目大意是：一个由0,1组成的数字串~~，现在你问一个人，第i位到第j位的1的个数为奇数还是偶数。一共会告诉你几组这样的数
要你判断前k组这个人回答的都是正确的，到第k+1组，这个人说的是错的，要你输出这个k，要是这个人回答的都是正确的，则输出组数
odd为奇数，even为偶数。
Sample Input
10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd
Sample Output
3
思路：赤裸裸的种类并查集吧.......其中，我们把一段区间为奇数标记为0，为偶数标记为1，然后如果区间连贯，也就是说区间1到区间2，区间3到区间4，那么就是可以连贯成区间1到区间4的，如此的话，可以是左极限-1，或者右极限+1......判断是否在同一个树上，在的话，判断是否正确，不在的话，连接起来，在连接的时候，按照种类并查集的操作即可.......
ac代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int father[50005],rank[50005],ans=0;
struct node
{
int v1,v2;
char ch[10];
int num;
} s[50005];
int t[50005],flag;
int cmp(const node a,const node b)
{
if(a.num<b.num)
return 1;
else
return 0;
}
int find(int x)
{
if(x==father[x])
return x;
int tmp=father[x];
father[x]=find(tmp);
rank[x]=(rank[x]+rank[tmp])%2;
return father[x];
}
void liantong(int x,int y,int k)
{
int xx=find(x);
int yy=find(y);
if(xx==yy)
{
int sum=(2-rank[x]+rank[y])%2;
if(sum!=k)
flag=0;
// return;
}
if(xx>yy)
{
father[xx]=yy;
rank[xx]=(2-k+2-rank[x]+rank[y])%2;
}
if(xx<yy)
{
father[yy]=xx;
rank[yy]=(2-k+2-rank[y]+rank[x])%2;
}
//printf("%d %d %d %d %d
",x,y,rank[x],rank[y],k);
}
int erfen(int ll,int rr,int k)
{
while(ll<=rr)
{
int mid=(ll+rr)/2;
if(t[mid]>k)
rr=mid-1;
else
ll=mid+1;
}
return rr;
}
int main()
{
int n,m;
while(scanf("%d",&n)>0)
{
if(n==-1)
break;
scanf("%d",&m);
for(int i=0; i<=20005; i++)
{
father[i]=i;
rank[i]=0;
}
/*if(m==0)
{
printf("0
");
return 0;
}*/
int cnt=0;
for(int i=0; i<m; i++)
{
s[i].num=i;
scanf("%d%d%s",&s[i].v1,&s[i].v2,s[i].ch);
t[cnt++]=s[i].v1;
t[cnt++]=s[i].v2;
}
sort(t,t+cnt);
int cnt1=1;
for(int i=1; i<cnt; i++)
if(t[i]!=t[i-1]) t[cnt1++]=t[i];
for(int i=cnt1-1; i>0; i--)
if(t[i]!=t[i-1]+1) t[cnt1++]=t[i-1]+1;
sort(t,t+cnt1);
for(int i=cnt1; i>0; i--)
t[i]=t[i-1];
//for(int i=1; i<=cnt1; i++)
// printf("%d ",t[i]);
int ans=m;
flag=1;
for(int i=0; i<m; i++)
{
int x=erfen(1,cnt1,s[i].v1);
int y=erfen(1,cnt1,s[i].v2);
if(s[i].ch[0]=='e')
liantong(x-1,y,0);
else
liantong(x-1,y,1);
if(flag==0)
{
ans=i;
break;
}
}
//for(int i=0;i<=n;i++)
//printf("%d
",rank[i]);
printf("%d
",ans);
}
return 0;
}
/*
3
3
1 2 odd
2 3 odd
1 3 even
*/