思路

查询区间和的奇偶性，想到前缀和，那么对于给定的区间 $[l, r]$，其奇偶性即 $s_r\oplus s_{l-1}$，其中 $s_i$ 表示前 $i$ 个数中 1 数量的奇偶性。

由此可以知道，若 $[l, r]$ 内有偶数个 1，则 $s_r\oplus s_{l-1} = 0$，故 $s_r = s_{l-1}$；同理， $[l, r]$ 内有奇数个 1 时，有$s_r \neq s_{l-1}$。

这样就转化为了类似【「NOI2015」程序自动分析】的问题，于是就可以使用扩展域并查集维护两点关系并判断可行性。

AC Code

#include <bits/stdc++.h>

constexpr int MAXM = 5e3 + 10;

std::unordered_map<int, int> fa;

inline int fatherOf(int x) {
    if(!fa[x] || fa[x] == x)
        return x;
    else
        return fa[x] = fatherOf(fa[x]);
}

inline void join(int u, int v) {
    fa[fatherOf(u)] = fatherOf(v);
}

inline bool test(int u, int v) {
    return fatherOf(u) == fatherOf(v);
}

int main() {
    int N, M;
    std::cin >> N >> M;

    for(int i = 1, l, r; i <= M; ++i) {
        std::string type;
        std::cin >> l >> r >> type; l += 114514, r += 114514;

        if(type[0] == 'e') {
            if(test(l-1, -r) || test(-l+1, r))
                std::cout << i - 1, exit(0);
            else
                join(l-1, r), join(-l+1, -r);
        }
        else {
            if(test(l-1, r) || test(-l+1, -r))
                std::cout << i - 1, exit(0);
            else
                join(l-1, -r), join(-l+1, r);
        }
    }

    std::cout << M;
}

C127 带权并查集+离散化 P5937 [CEOI1999] Parity Game

#include<bits/stdc++.h>
using namespace std;
const int N=11100;
struct node{int l,r,ans;}a[N];int len,lsh[N];
int n,m,fa[N],d[N];
int findid(int x){return lower_bound(lsh+1,lsh+n+1,x)-lsh;}
int findfa(int x)
{
    if(fa[x]==x)return x;
    int tx=findfa(fa[x]);
    d[x]^=d[fa[x]];
    return fa[x]=tx;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
	{
        char op[10];
        scanf("%d%d%s",&a[i].l,&a[i].r,op+1);
        lsh[++len]=a[i].l,lsh[++len]=a[i].r;
        a[i].ans=(op[1]=='o');
    }
    
    sort(lsh+1,lsh+len+1);
    n=unique(lsh+1,lsh+len+1)-lsh-1;
    
    for(int i=1;i<=n;i++)fa[i]=i,d[i]=0;
    for(int i=1;i<=m;i++)
	{
        int x=findid(a[i].l-1),y=findid(a[i].r);
        int tx=findfa(x),ty=findfa(y);
        if(tx!=ty)
		{
			fa[tx]=ty;
			d[tx]=d[x]^d[y]^a[i].ans;
		}
        else
		{
            if((d[x]^d[y])!=a[i].ans)
			{
                printf("%d",i-1);
                return 0;
            }
        }
    }
    printf("%d",m);
    return 0;
}