题目链接
题目大意：有一串0，1组成的序列，每次A会询问B,l-r一段区间总含有1的个数是偶数还是奇数。B会回答是奇数还是偶数，但是B可能会撒谎。比如：B曾经回答过1-3中有奇数个1，4-6中有偶数个1，但是后面问B，l-r中有1的个数是奇数还是偶数，B回答是偶数，这与前面的回答相矛盾，所以B说谎了。题目要求出前1~k个数是正确的，求K是多少。

输入：输入N表示01串的长度，M表示的询问次数，接下来M行，每行输入两个数a,b和even/odd,
a,b表示区间的左右端点，even表示偶数，odd表示奇数。
输出:K.
1、带权并查集
总体思路：
我们可以用一个sum数组来记录前i个有偶数个1还是有奇数个1.
我们可以发现中间一段区间有偶数个1，那么sum[l-1]和sum[r]的奇偶行性相同。
如果中间一段区间有奇数个1，那么sum[l-1]和sum[r]的奇偶性不相同。
这两条就是我们用并查集来进行关系传递的条件。

接下来我们设数组D，初始值为0，d[x]=0表示以x+1节点为头节点，和区间的右端点的奇偶性相同，d[x]=1表示奇偶性不同。一个集合就表示一段连续的区间，将x,y合并到同一集就需要进行d[p]=ans（某种操作）d[x]（某种操作）d[y]，(d[p]表示x根节点和y节点之间的奇偶关系，ans表示x和y之间的关系）。合并是两个根节点之间的合并，根节点的d[i]都是0，所以d[p]=ans（某种操作）0（某种操作）0，当ans=1(表示区间1的个数是奇数）这是两个端点的奇偶不同，所以d[p]等于1，当ans=0(表示区间1的个数是偶数）这是两个端点的奇偶相同，所以d[p]等于0，这刚好满足异或运算，所以通过对树根d[x]的所有边权进行异或运算就可以得到x与根节点之间的奇偶关系。
图片说明
以上图片方便理解d[p]=d[x]^d[y]^ans;

同时边权的传递关系也满足异或运算：
A、如果d[y]=1表示和根节点奇偶不同，1、d[x]=0表示x和y的奇偶一样，所以d[y](某种运算）d[x]=d[x]=1;2、d[x]=1表示x和y的奇偶不一样，所以d[y](某种运算）d[x]=d[x]=0.
B、如果d[y]=0表示和根节点奇偶相同，1、d[x]=0表示x和y的奇偶一样，所以d[y](某种运算）d[x]=d[x]=0;2、d[x]=1表示x和y的奇偶不一样，所以d[y](某种运算）d[x]=d[x]=1.
这都符合异或运算。

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct ty{
    int l;
    int r;
    string x;
    int f;
};
ty t[10005];
int a[20010];
int pre[20010];
int d[20010];
int cnt=0;
/*int find(int x){
    int r=x;
    while(r!=pre[r]){
        r=pre[r];
    }
    int j=x,temp;
    这里更新d数组出现了错误，只更新了d[x],但是x到根节点的路径上其他节点的d值没有更新
    while(pre[j]!=r){
        temp=pre[j];
        pre[j]=r;
        j=temp;
        d[x]=d[x]^d[j];
    }
    return r;
}*/
int find(int x){
    if(x==pre[x]) return x;
    int root=find(pre[x]);//递归计算集合代表
    d[x]^=d[pre[x]];//维护d数组
    return pre[x]=root;//路径压缩
}
void merge(int x,int y,int ans){
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy){
        pre[xx]=yy;
        d[xx]=d[x]^ans^d[y];
    }
    return ;
}
int main(){
    for(int i=0;i<=20005;i++) pre[i]=i;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>t[i].l>>t[i].r>>t[i].x;
        if(t[i].x[0]=='o') t[i].f=1;
        else t[i].f=0;
        a[++cnt]=t[i].l-1;
        a[++cnt]=t[i].r;
    }
    sort(a+1,a+cnt+1);
    n=unique(a+1,a+cnt+1)-(a+1);//数据过大以上都是进行离散化
    for(int i=1;i<=m;i++){
        int left=lower_bound(a+1,a+n+1,t[i].l-1)-a;
        int right=lower_bound(a+1,a+n+1,t[i].r)-a;
        if(find(left)==find(right)){
            if(d[left]^d[right]==t[i].f) continue;
//如果在一个集合里表示在一个区间里，d[left]^d[right]==t[i].f表示话为真继续，否则输出i-1；
            else{
                cout<<i-1<<endl;
                return 0;
            }
        }
        else{
            merge(left,right,t[i].f);//进行区间合并
        }
    } 
    cout<<m<<endl;
    return 0;
}