Parity game

题目

有一个长度为n的序列
给出Q条限制
l,r,str str==odd 表示[l,r]区间内的数的和是奇数，否则为偶数
请你输出最小的不满足条件的编号-1（即最后一个满足的），如果全部满足，输出总数Q！

分析

算是一个带权并查集的模板题。dis[i]记录他到根结点的距离，假如a，b现在已经加入并查集了，现在要查询a，b之间的奇偶，只需要abs(dis[a]-dis[b])，然后拿此结果与当前answer进行比较就行了。不匹配，就break。

坑点：c++的取余可以是负数，在比较奇偶时加上绝对值

AC代码

#include <iostream>
#include <algorithm>
#include <map>
#include <stdio.h>
#include <string>
using namespace std;

int N,M;
map<int,int> fa,dis;

int find(int x){
    if(x != fa[x]) {
        int f = fa[x];
        fa[x] = find(fa[x]);
        dis[x] += dis[f];
    }
    return fa[x];
}
void join(int x,int y,int v){
    int fx = find(x),fy = find(y);
    if(fx != fy){
        fa[fx] = fy;
        dis[fx] = dis[y]+v-dis[x];
    }
}
int main(){
    cin>>N>>M;
    int a,b,v,res =0;string s;
    while(M--){
        scanf("%d %d",&a,&b);b++;
        if(!dis.count(a)) {
            dis[a] = 0;
            fa[a] = a;
        }
        if(!dis.count(b)) {
            dis[b] = 0;
            fa[b] = b;
        }
        cin>>s;
        if(s == "even") v = 0;
        else v = 1;
        if(find(a) == find(b)){
            if(abs((dis[a]-dis[b])%2) != v){ //注意要取绝对值
                break;
            }
        }else{
            join(a,b,v);
        }
        res++;
    }
    cout<<res<<endl;

    return 0;
}