Parity game

题目

解题思路：

sum数组表示序列S的前缀和
S[l~r]有偶数个1，等价于sum[l-1]&sum[r]奇偶性相同。
S[l~r]有奇数个1，等价于sum[l-1]&sum[r]奇偶性不同。
我们发现N很大，但是问题数M却不多，于是我们可以用离散，把每个问题的两个整数l-1&r缩小到等价的1~2M以内的范围

Accepted code：

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
struct node {
    int l,r,v;
}q[10001];
int a[20001],fa[20001],d[20001],n,m;


inline void read(int &f) {
    f=0;char c=getchar();int ag=1;
    while(!isdigit(c)) {if (c=='-') ag=-1; c=getchar();}
    while(isdigit(c)){f=(f<<3)+(f<<1)+c-48;c=getchar();}
    f*=ag; return;
}
void write(int x) {
    if (x<0) putchar('-'),x*=-1;
    if (x>9) write(x/10);putchar(x%10+48);return;
}


inline void read_init() {
    int t=0; read(n);read(m);
    for (int i=1;i<=m;i++) {
        char c[5];
        read(q[i].l); read(q[i].r);
        scanf("%s",c);
        q[i].v=c[0]=='o'?1:0;
        a[++t]=q[i].l-1;
        a[++t]=q[i].r;
    }
    sort(a+1,a+t+1);
    n=unique(a+1,a+t+1)-a-1;
    return;
}
int find(int x) {
    if (x==fa[x]) return x;
    int root=find(fa[x]); d[x]^=d[fa[x]];
    return fa[x]=root;
}
int main() {
    read_init();
    for (int i=1;i<=n;i++) fa[i]=i;
    for (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;
        int P=find(x),Q=find(y);
        if (P==Q)
            if ((d[x]^d[y])!=q[i].v) {
                write(i-1); return 0;
            }
        fa[P]=Q; d[P]=d[x]^d[y]^q[i].v;
    }
    write(m); return 0;
}