这道题有两种做法，一种是 扩展域（种类并查集），一种是 边带权（带权并查集）。种类并查集貌似应该都比带权并查集简单，所以先讲种类并查集的做法，再讲带权并查集
种类并查集
若 sum[ l ~ r ] 表示 l到r 之间1的个数，sum是一个前缀和数组，那么有 sum [ l ~ r ] = sum[ r ] - sum[ l - 1 ] 。如果有sum[ l ~ r]为奇数个，那么 sum[ r ]和sum[ l - 1 ]肯定奇偶性不同；如果有sum[ l ~ r]为偶数个，那么 sum[ r ]和sum[ l - 1 ]肯定奇偶性相同（这个很简单吧，同奇（偶）-同奇（偶）= =偶，偶-奇= =奇），知道这些之后，我们就可以吧区间[ l ~ r ] 转换为 [ l - 1 ] 和 [ r ] 两个区间，继续往后看
对于一个集合x，我们把它扩展成两个东西，x和x+n，分别表示奇数域和偶数域（不知道为什么这样做的可以去看看我并查集的那篇博客 无耻宣传），那么x表示sum[x]为奇数，x+n表示sum[x]为偶数
因为这道题n的数据范围很大，但是m个操作其实不大，那我们需要对所有数据离散化（离散化教程看另外一篇博客 再次无耻）。对于每个问题 我们设x为l-1的离散化之后的数，y为r离散化之后的数，ans表示当前的回答
①ans=0，表示x和y，x+n和y+n 可以相互推出来，合并
②ans=1，表示x和y+n，x+n和y 可以相互推出来，合并
这样的合并其实可以维护元素之间关系的传递性，即“敌人的敌人就是朋友”这种关系（种类并查集入门）。那么如果x与y在同一集合中，那么奇偶性相同；如果x和y+n在同一集合中，那么奇偶性不同。那么这道题的程序就出来了
#include<bits/stdc++.h>
using namespace std;
struct node {
int l,r,ans;
} ask[40005]; //l，r，ans的意义见上面的文字
int n,m;
int f[40005],a[40005];
int find(int x) {
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
void merge(int x,int y) {
f[find(x)]=find(y);
} //基本操作
int main() {
scanf("%d%d",&n,&m);
int tot=0;
for(register int i=1; i<=m; i++) {
char op[5];
scanf("%d%d",&ask[i].l,&ask[i].r);
cin>>op;
if(op[0]=='o') ask[i].ans=1;
else ask[i].ans=0;
a[++tot]=ask[i].l;
a[++tot]=ask[i].r;
}
sort(a+1,a+1+tot);
n=unique(a+1,a+1+tot)-a-1;
for(register int i=1; i<=2*n; i++) f[i]=i;
for(register int i=1; i<=m; i++) {
ask[i].l=lower_bound(a+1,a+1+n,ask[i].l-1)-a;
ask[i].r=lower_bound(a+1,a+1+n,ask[i].r)-a;
} //以上全部都为离散化
for(register int i=1; i<=m; i++) {
if(ask[i].ans==0) {
if(find(ask[i].l)==find(ask[i].r+n)) {
cout<<i-1;
return 0;
}
merge(ask[i].l,ask[i].r);
merge(ask[i].l+n,ask[i].r+n);
}else{
if(find(ask[i].l)==find(ask[i].r)){
cout<<i-1;
return 0;
}
merge(ask[i].l,ask[i].r+n);
merge(ask[i].l+n,ask[i].r);
}
}
cout<<m;
return 0;
}
带权并查集
带权并查集，真的很麻烦！！！（看这个之前先去了解上面种类并查集的做法，有相同的地方）
用带权并查集，那么我们应该怎么维护这个边权呢？这个边权应该是什么呢？
不难想到，这道题的边权就是 子节点与父节点的奇偶关系。对于边权 d[ x ]表示 x 与 f[ x ] 之间的奇偶关系，0表示相同，1表示不同
那么在路径压缩的时候，怎么维护与根节点之间的奇偶性呢？我们对x到根节点路径上的所有边权进行异或运算，就可以维护这个奇偶性了
若x和y两个节点在一个集合中，对x维护之后，y也维护之后，那么d[x]和d[y]异或之后就是x和y的奇偶关系了，我们画图理解（这辈子都想不清楚图为什么这么小，）
如果要合并x和y两个集合，若p为x的根节点，q为y的根节点，我们把p，q合并，那么x与y的奇偶性应该是 d[ x ] ^ d[ y ] ^ d[ p ]，这里的 d[ p ]应该是d[ x ] ^ d[ y ] ^ ans，继续画图理解（貌似清晰一点了）
这样看来，程序也该出来了吧
#include<bits/stdc++.h>
using namespace std;
struct node{
int l,r,ans;
}ask[20005];
int n,m;
int f[20005],d[20005],a[20005];
int find(int x){
if(x==f[x]) return x;
int root=find(f[x]);
d[x]^=d[f[x]];
return f[x]=root; //继续维护啊
}
void merge(int x,int y,int i){
int fx=find(x),fy=find(y);
f[fx]=fy;
d[fx]=d[x]^d[y]^ask[i].ans; //维护啊
}
int main(){
scanf("%d%d",&n,&m);
int tot=0;
for(register int i=1;i<=m;i++){
char op[5];
scanf("%d%d",&ask[i].l,&ask[i].r);
cin>>op;
if(op[0]=='o') ask[i].ans=1;
else ask[i].ans=0;
a[++tot]=ask[i].l;
a[++tot]=ask[i].r;
}
sort(a+1,a+1+tot);
n=unique(a+1,a+1+tot)-a-1; //离散化这里一定要-1哦
for(register int i=1;i<=n;i++) f[i]=i;
for(register int i=1;i<=m;i++){
ask[i].l=lower_bound(a+1,a+1+n,ask[i].l-1)-a;
ask[i].r=lower_bound(a+1,a+1+n,ask[i].r)-a;
}
for(register int i=1;i<=m;i++){
if(find(ask[i].l)==find(ask[i].r)){
if((d[ask[i].l]^d[ask[i].r])!=ask[i].ans){
cout<<i-1;
return 0;
}
}else merge(ask[i].l,ask[i].r,i);
}
cout<<m;
return 0;
}