题意

• 给定长为n的01串，给出m次描述，找出第一次矛盾的描述序号

思路

• 将区间值转化为端点值
• eg:[5,10]中有奇数个1，说明前4个数中1的个数和前10个数中1的奇偶性不同，也就是前4个数中有奇数个一的时候前10个数有偶数个1
• 维护一个大小为2n的father数组，当属于1-n表明为奇数，属于n+1-2n表明为偶数，区间奇偶性不同就建边，奇偶性相同就在同区间建边
• 直到出现矛盾或者全部通过

注意

• 由于区间范围很大，不能开数组来存，需要使用map进行离散化
• 由于使用map，需要用count方法来判断是否已经存在，如果不存在就赋初值使得父节点是自己
• 如果存在就不用管

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int>fa;

int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
	fa[find(x)]=find(y);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    n+=5;
    int ans=m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if (!fa.count(a-1)) {fa[a-1]=a-1;fa[a-1+n]=a-1+n;}
        if (!fa.count(b)) {fa[b]=b;fa[b+n]=b+n;}
        string s;
        cin>>s;
        if(s=="even"){
            if(find(a-1)==find(b+n)||find(a-1+n)==find(b)){
                ans=i-1;
                break;
            }else{
                merge(a-1,b);
                merge(a-1+n,b+n);
            }
        }else{
            if(find(a-1)==find(b)||find(a-1+n)==find(b+n)){
                ans=i-1;
                break;
            }else{
                merge(a-1,b+n);
                merge(a-1+n,b);
            }            
        }
    }
    cout<<ans<<'\n';
	return 0;
}