《算法竞赛进阶指南》0x41并查集 奇偶游戏

题目链接：https://www.acwing.com/problem/content/241/

给出长度n，和m条记录，每条记录中说明一个区间中1的数量，其中序列是01序列，问到哪一个是最后一个正确的。

可以通过并查集解决，用前缀异或和作为一段区间中1的个数的象征。可以通过“边带权”的方式计算也可以通过扩展域的方式进行求解。

第一种求解方案：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 10010;
int f[maxn*2],d[maxn*2],a[maxn*2];
struct node{
    int l,r;
    int ans;
}query[maxn];
int n,m;
int num;
int find(int x){
    if(x==f[x])return x;
    int root=find(f[x]);
    d[x]^=d[f[x]];
    return f[x]=root;//记住一定要用f[x]=root，否则f[x]没得到更新 
}
int get(int x){
    return lower_bound(a+1,a+num+1,x)-a;
}
int main(){
    cin>>n>>m;
    char s[10];
    for(int i=1;i<=m;i++){
        scanf("%d%d%s",&query[i].l,&query[i].r,s);
        if(s[0]=='e')query[i].ans=0;
        else query[i].ans=1;
        a[2*i-1]=query[i].l-1;
        a[2*i]=query[i].r;
    }
    sort(a+1,a+2*m+1);
    num=unique(a+1,a+2*m+1)-(a+1);
    for(int i=1;i<=num;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int x=get(query[i].l-1);
        int y=get(query[i].r);
        int ans=query[i].ans;
        int fx=find(x),fy=find(y);
        if(fx==fy){
            if(d[x]^d[y]==ans)continue;
            else{
                cout<<i-1<<endl;
                return 0;
            }
        }else{
            f[fx]=f[y];
            d[fx]=ans^d[x]^d[y];
        }
    }
    cout<<m<<endl;
    return 0;
}

第二种求解方案：构建扩展域，将一个点可能归属的集合拆成两个推导集。

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn = 10010;
int f[maxn*2];
int a[maxn*2];
int n,m,num;
struct node{
    int l,r,ans;
}query[maxn];
int find(int x){
    return (x==f[x]?x:f[x]=find(f[x]));
}
void Union(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx==fy)return ;
    f[fx]=fy;
    return ;
}
int get(int x){
    return lower_bound(a+1,a+num+1,x)-a;
}
int main(){
    cin>>n>>m;
    char s[10];
    for(int i=1;i<=m;i++){
        scanf("%d%d%s",&query[i].l,&query[i].r,s);
        query[i].ans=(s[0]=='o'?1:0);
        a[2*i-1]=query[i].l-1;
        a[2*i]=query[i].r;
    }
    sort(a+1,a+2*m+1);
    num=unique(a+1,a+2*m+1)-(a+1);
    for(int i=1;i<maxn-1;i++)f[i]=i;
    for(int i=1;i<=m;i++){
        int x_odd=get(query[i].l-1);
        int y_odd=get(query[i].r);
        int x_even=x_odd+num;
        int y_even=y_odd+num;
        int ans=query[i].ans;
        if(ans){
            if(find(x_odd)==find(y_odd))
            {
                cout<<i-1<<endl;
                return 0;
            }
            Union(x_odd,y_even);
            Union(y_odd,x_even);
        }else{
            if(find(x_odd)==find(y_even))
            {
                cout<<i-1<<endl;
                return 0;
            }
            Union(x_odd,y_odd);
            Union(y_even,x_even);
        }
    }
    cout<<m<<endl;
    return 0;
}