如果用$sum$数组表示前缀和,那么对于$S[l\sim r]$是偶数时,$sum[l-1]$与$sum[r]$的奇偶性相同。
反之则相反,根据这个性质,可以进行“扩展域并查集”或“边带权并查集”操作。
扩展域并查集:
将范围从$n$扩大到$2n$,将元素$x$分裂成$x+n,n$
如果奇偶性相同,则$x,y$并在一个集合,$x+n,y+n$并在一个集合,其意思表示,$x_{even},y_{even}$并在一起,$x_{odd},y_{odd}$并在一起。
如果相反,则$x,y+n$并在一个集合,$x+n,y$并在一个集合。

扩展域代码实现较为简单。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
using namespace std;
const int N=1e4+10;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int l[N],r[N],arr[N<<1],sz,Q[N];
void disc()
{
    sort(arr+1,arr+sz+1);int len=0;
    for(int i=1;i<=sz;i++)
        if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
    sz=len;
}
inline int g(int d)
{
    int l=1,r=sz+1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(arr[mid]<d)l=mid+1;
        else r=mid;  
    }
    return l;
}
int fa[N<<2];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int main()
{
    int m,n;qr(m),qr(n);char s[7];
    for(int i=1;i<=n;i++){qr(l[i]),qr(r[i]),scanf("%s",s+1);if(s[1]=='e')Q[i]=0;else Q[i]=1;arr[++sz]=l[i],arr[++sz]=r[i];}
    disc();for(int i=0;i<=sz*2;i++)fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        int x=g(l[i]-1),y=g(r[i]);
        int x1=x,x2=x+sz,y1=y,y2=y+sz;
        if(Q[i]==1)
        {
            if(get(x1)==get(y1)){qw(i-1);puts("");return 0;}
            int p=get(x1),q=get(y2);fa[p]=q;
                p=get(x2),q=get(y1);fa[p]=q;
        }
        else
        {
            if(get(x1)==get(y2)){qw(i-1);puts("");return 0;}
            int p=get(x1),q=get(y1);fa[p]=q;
                p=get(x2),q=get(y2);fa[p]=q;
        }
    }
    qw(n);puts("");
    return 0;
}

“边带权做法”
$d[x]$表示$x$与父亲之间的"关系",如果$d[x]=1$,则x与父亲处于相反集合,反之则相同。
由于关系具有传递性,
那么合并$x,y$,当在不同集合时,$d[p]$取什么值?
由于$x~ to~ y =1$,那么$d[x]^d[y]^d[p]=1$,因此$d[p]$就被表示出来了。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=1e4+5;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int l[N],r[N],arr[N<<1],sz,Q[N];
void disc()
{
    sort(arr+1,arr+sz+1);int len=0;
    for(int i=1;i<=sz;i++)
        if(i==1||arr[i]!=arr[i-1])arr[++len]=arr[i];
    sz=len;
}
inline int g(int d)
{
    int l=1,r=sz+1;
    while(l<r)
    {
        int mid=l+r>>1;
        if(arr[mid]<d)l=mid+1;
        else r=mid;  
    }
    return l;
}
int fa[N<<1],d[N<<1];
int get(int x)
{
    if(x==fa[x])return x;
    int root=get(fa[x]);
    d[x]^=d[fa[x]];
    return fa[x]=root;
}
int main()
{
    int m,n;qr(m),qr(n);char s[7];
    for(int i=1;i<=n;i++){qr(l[i]),qr(r[i]),scanf("%s",s+1);if(s[1]=='e')Q[i]=0;else Q[i]=1;arr[++sz]=l[i],arr[++sz]=r[i];}
    disc();
    for(int i=0;i<=sz;i++)fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        int x=g(l[i])-1,y=g(r[i]),p=get(x),q=get(y);
        if(p==q)
        {
            if(d[x]^d[y]!=Q[i]){qw(i-1);puts("");return 0;}
        }
        else fa[p]=q,d[p]=d[x]^d[y]^Q[i];//Q[i]=d[x]^d[y]^d[p];
    }
    qw(n);puts("");
    return 0;
}