很喜欢这样的题啊，有一定的思维难度且很典型。

首先拿到题目，我是没有思路的。想过用线段树维护区间信息，判断是否符合条件。想来想去发现实现不了。看到了lyd大神的想法后，感觉很巧。

维护前缀和，如果区间[l, r]有偶数个1，那么s[r]和s[l-1]的奇偶性一定相同。如果区间[l, r]有奇数个1，那么s[r]和s[l-1]的奇偶性一定不同。

这样一来，维护区间信息就变成维护俩端点的信息了。

法一：二分图染色+二分

其实如果想到这并且会扩展/带权并查集的话，这题就直接A了。

可是我当时还不会扩展/带权并查集，于是我用了二分图染色做的。思考过程如下：

首先如果一个局面不矛盾的前提，是能构成一个二分图。（显然）

可以用二分图染色法判断一个图是否为二分图，复杂度为O(n)（n为点数）。

因为二分图染色法判断二分图是不能叠加的，也就是每新加一个限制条件都要重新O(n)判断一次。

那就套个二分呗，每次二分用染色法check一下即可。

具体二分图染色法如何实现这里不再展开（其实就是一个普通的dfs打标记，看我代码应该就可以看懂了）

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int M=20005;

struct E {int nex,to,dis;} e[M*2];
int n,m,len,num,flag;
int l[M],r[M],op[M],lsh[M*2],h[M*2],col[M*2];

void add(int u,int v,int w) {e[++num]={h[u],v,w},h[u]=num;}
int val(int v) {return lower_bound(lsh+1,lsh+1+len,v)-lsh;}

void dfs(int x) {
    if(!flag) return;
    for(int i=h[x];i;i=e[i].nex) {
        int y=e[i].to;
        if(e[i].dis==2) { //不相同
            if(col[y]==0) {col[y]=-col[x],dfs(y);}
            else if(col[y]==col[x]) {flag=0; break;}   
        }
        else { //相同
            if(col[y]==0) {col[y]=col[x],dfs(y);}
            else if(col[y]!=col[x]) {flag=0; break;}
        }
    }
}

bool check(int mid) {
    num=0,memset(h,0,sizeof(h));
    flag=1,memset(col,0,sizeof(col));
    for(int i=1;i<=mid;i++)
        if(op[i]==1) add(l[i],r[i],1),add(r[i],l[i],1);
        else add(l[i],r[i],2),add(r[i],l[i],2);
    for(int i=1;i<=len;i++)
        if(col[i]==0) {
            col[i]=1,dfs(i);
            if(!flag) break;
        }
    return flag;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        scanf("%d%d",&l[i],&r[i]),r[i]++;
        char c[7]; scanf("%s",c);
        c[0]=='e'?op[i]=1:op[i]=2;
        lsh[i]=l[i],lsh[i+m]=r[i];
    }
    sort(lsh+1,lsh+1+2*m);
    len=unique(lsh+1,lsh+1+2*m)-lsh-1;
    for(int i=1;i<=m;i++) l[i]=val(l[i]),r[i]=val(r[i]);
    if(check(m)) {cout<<m; return 0;}
    if(!check(0)) {cout<<0; return 0;}
    int l=0,r=m,ans;
    while(l<=r) {
        int mid=l+r>>1;
        if(check(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}

法二：带权并查集

A了之后就去学习了lyd大大的带权并查集写法。感受到了什么才叫真正会用数据结构。

以往我用并查集只是用来维护俩俩是否联通。

但其实，往广义的来说，并查集维护的是俩俩元素之间的信息。（这个信息，可以是是否联通，也可以是奇偶性是否相同，还可以是两点距离等等）

对于这一题，并查集维护的是俩元素间的奇偶性关系。就像书上说的，d[x]表示x点与父亲的关系，1代表奇偶性相同，0代表奇偶性不同。那么显然每个点与根的奇偶关系就可以通过做路径上的边权做一遍异或即可。

算法流程如下：查询x, y奇偶性是否相同？

如果x、y在一个集合里（关系确定），那么就先执行一遍getFat()（更新d[x]），执行完后，d[x]表示的就是x与根的奇偶关系了。这时只需检查d[x] xor d[y] 是否 == 题中所给奇偶关系即可。

如果x、y不在一个集合，显然要将其所在的两个集合合并，合并只需添加一条边，x树的根与y树的根相连。其权值可以利用题目所给奇偶性和d[x]、d[y]推出（简单的初中数学问题）。然后合并即可。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int M=20005;

int n,m,len;
int l[M],r[M],op[M],lsh[M*2],fat[M*2],d[M*2];

int val(int v) {return lower_bound(lsh+1,lsh+1+len,v)-lsh;}
int getFat(int x) {
    if(x==fat[x]) return x;
    int root=getFat(fat[x]);
    d[x]^=d[fat[x]];
    return fat[x]=root;
}
void merge(int x,int y,int v) {
    int fx=fat[x],fy=fat[y];
    d[fx]=(v^d[x]^d[y]),fat[fx]=fy;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        scanf("%d%d",&l[i],&r[i]),r[i]++;
        char c[7]; scanf("%s",c);
        c[0]=='e'?op[i]=1:op[i]=2;
        lsh[i]=l[i],lsh[i+m]=r[i];
    }
    sort(lsh+1,lsh+1+2*m);
    len=unique(lsh+1,lsh+1+2*m)-lsh-1;
    for(int i=1;i<=len;i++) fat[i]=i;
    for(int i=1;i<=m;i++) l[i]=val(l[i]),r[i]=val(r[i]);
    int flag=1;
    for(int i=1;i<=m;i++) {
        //元素间没有关系就合并，有关系就检查是否符合
        if(getFat(l[i])!=getFat(r[i])) {
            if(op[i]==1) merge(l[i],r[i],0);
            else merge(l[i],r[i],1);
        }
        else {
            int v=(d[l[i]]^d[r[i]]);
            if(v==1 && op[i]==1) {cout<<i-1,flag=0; break;}
            if(v==0 && op[i]==2) {cout<<i-1,flag=0; break;}
        }
    }
    if(flag) cout<<m;
    return 0;
}

总结

你们可以发现我并没有写扩展并查集，因为个人认为跟带权并查集比起来不够通用，跟二分图染色比起来，不容易理解。所以我就不将其写出来了。其实这是一道很典型的题，再写完题后我想：如果有三分图呢？怎么做呢？（刚好下一题食物链就是这种情况23333）

如果用二分图染色，很好理解也很好改。只需在dfs打标记那增加几个对【关系判断】的if条件即可。

如果用扩展并查集，数组扩大倍数处理即可。

如果用带权并查集，异或不了啊。因为只有二分图情况时刚好可以利用异或的特殊性质。怎么办呢？

其实想了一下很好改，本质根二分图染色方法一样。只需在getFat()函数里将d[x]的更新方式改为对【关系判断】的if条件，再在merge()函数里改一下d[fx]的更新规则即可。

我继续思考，如果要维护n种关系呢？（也就是n分图）

这时扩展并查集就不同考虑了，空间炸裂。至于二分图染色和带权并查集，只需用循环去写对于【关系判断】的条件即可。

综上，可以看出。并查集能维护数据间的信息，这个信息不只是联通信息。维护的关键在于魔改树中的边。