POJ

分析

用$sum[]$来表示$S$的前缀和，然后：

• 若$S[l\sim r]$有偶数个$1$，那么$sum[l-1]$和$sum[r]$奇偶性相同。
• 若$S[l\sim r]$有奇数个$1$，那么$sum[l-1]$和$sum[r]$奇偶性不同。

然后就可以用并查集来维护这个关系。

注意要离散化。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=10000+10;

int root[MAXN];
inline void init(int n) { for (re int i=1;i<=n;++i) root[i]=i; }
inline int find(int x) { return x==root[x]?x:root[x]=find(root[x]); }
inline void merge(int a,int b) { a=find(a),b=find(b); if (a!=b) root[a]=b; }
inline int check(int a,int b) { return find(a)==find(b); }

struct query { int l,r,type; } q[MAXN];
int a[MAXN],top=0;

int main() {
    int n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        char tmp[5];
        q[i].l=read(),q[i].r=read(); scanf("%s",tmp);
        q[i].type=(tmp[0]=='o');
        a[++top]=q[i].l-1,a[++top]=q[i].r;
    }
    sort(a+1,a+top+1); n=unique(a+1,a+top+1)-a-1;
    init(2*n+10);
    for (re int i=1;i<=m;++i) {
        int x=lower_bound(a+1,a+n+1,q[i].l-1)-a;
        int y=lower_bound(a+1,a+n+1,q[i].r)-a;
        if (q[i].type==1) { //有奇数个1，x、y奇偶性不同 
            if (check(x,y)) { printf("%d\n",i-1); return 0; }
            merge(x,y+n); merge(x+n,y);
        }
        else { //有偶数个1，x、y奇偶性相同 
            if (check(x,y+n)) { printf("%d\n",i-1); return 0; }
            merge(x,y); merge(x+n,y+n);
        }
    }
    printf("%d\n",m);
    return 0;
}