题目链接
https://www.acwing.com/activity/content/problem/content/474/1/
扩展域并查集
之前有道带权并查集，这里补一道扩展域并查集

#include <bits/stdc++.h>
using namespace std;
int n,m,t = 0;
const int N = 2*21000;
struct Query{
    int l,r,ans;
}Q[N];
int a[N],par[N];     
int Find(int x){
    if(par[x] == x) return x;
    return par[x] = Find(par[x]);
}
int main(){
    char str[10];
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        scanf("%d%d%s",&Q[i].l,&Q[i].r,str);
        Q[i].ans = str[0] == 'o'?1:0;
        a[++t] = Q[i].l-1;
        a[++t] = Q[i].r;
    }
    sort(a+1,a+1+t);
    n = unique(a+1,a+1+t) - a- 1;
    for(int i = 1;i <= 2*n;i++) par[i] = i;
     for(int i = 1;i <= m;i++){
        int x = lower_bound(a+1,a+1+n,Q[i].l-1)-a;
        int y = lower_bound(a+1,a+1+n,Q[i].r)-a;
        int x_odd = x,x_even = x+n;
        int y_odd = y,y_even = y+n;
        if(Q[i].ans == 0){      
            if(Find(x_odd) == Find(y_even)){     
                printf("%d\n",i-1);
                return 0;
            } 
            par[Find(x_odd)] = Find(y_odd);
            par[Find(x_even)] = Find(y_even);
        }else{
            if(Find(x_odd) == Find(y_odd)){      
                printf("%d\n",i-1); 
                return 0;
            }
            par[Find(x_odd)] = Find(y_even);     
            par[Find(x_even)] = Find(y_odd);     
        }
    }
    printf("%d\n",m);
    return 0;
}