奇偶游戏（带权并查集）

题目：

小A和小B在玩一个游戏。

首先，小A写了一个由0和1组成的序列S，长度为N。

然后，小B向小A提出了M个问题。

在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。

机智的小B发现小A有可能在撒谎。

例如，小A曾经回答过 S[1~3] 中有奇数个1， S[4~6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。

请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。

即求出一个最小的k，使得01序列S满足第1~k个回答，但不满足第1~k+1个回答。

输入格式

第一行包含一个整数N，表示01序列长度。

第二行包含一个整数M，表示问题数量。

接下来M行，每行包含一组问答：两个整数l和r，以及回答“even”或“odd”，用以描述S[l~r] 中有奇数个1还是偶数个1。

输出格式

输出一个整数k，表示01序列满足第1~k个回答，但不满足第1~k+1个回答，如果01序列满足所有回答，则输出问题总数量。

数据范围

输入样例：

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

输出样例：

3

解题报告：咱们得到的是某段区间内的奇偶性，所以咱们可以转换一下思想，每个点x的存储就是从1-x的奇偶性，那么给出的区间[l,r]的
奇偶性其实就是[1,l-1],[1,r]的奇偶性的异或，因为第二个区间总是包含前者的，题目给出的l,r,even/odd都是可以去证明的，咱们
一开始根据题目给的信息，维护n个独立的集合，当给定信息后，实现各个集合的连接，在这个过程中判断有没有矛盾。
中间涉及矛盾的判断，咱们维护一个d数组即可，d[x]存放的是x和其节点的奇偶性，当进行路径压缩的时候，d[x]需要异或所有父节点。实现
两棵树的合并的时候，维护的是x以n为根节点的树，和y以m为根节点的树进行合并，d[n]^d[x]^d[y]==result(题目给出的)
因为给定的数的范围比较大，所以要提前进行一下离散化处理。


ac代码：

 1 //from:Onion
 2 //239 奇偶游戏 带权并查集 
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<algorithm>
 7 #include<cmath>
 8 using namespace std;
 9 typedef long long ll;
10 
11 const int maxn=1e5+100;
12 int far[maxn];
13 int d[maxn];
14 int mp[maxn<<1];
15 int n,m;
16 struct node{
17     int l,r,result;
18 }qs[maxn];
19 
20 void init()
21 {
22     for(int i=0;i<maxn;i++)
23     {
24         far[i]=i;
25         d[i]=0;
26     }
27 }
28 
29 int find(int x)
30 {
31     if(far[x]==x)
32     {
33         return far[x];
34     }
35     int root=find(far[x]);
36     d[x]=d[x]^d[far[x]];
37     return far[x]=root;
38 }
39 
40 
41 int main()
42 {
43     int n,m;
44     init();
45     scanf("%d%d",&n,&m);
46     char op[10];
47     int x,y;
48     int cnt=0;
49     for(int i=1;i<=m;i++)
50     {
51         scanf("%d%d%s",&x,&y,op);
52         x--;
53         if(op[0]=='e')
54         {
55             qs[i].l=x;
56             qs[i].r=y;
57             qs[i].result=0;
58         }
59         else
60         {
61             qs[i].l=x;
62             qs[i].r=y;
63             qs[i].result=1;
64         }
65         mp[cnt++]=x;
66         mp[cnt++]=y;
67     }    
68     int flag=0;
69     sort(mp,mp+cnt);
70     n=unique(mp,mp+cnt)-mp;
71     for(int i=1;i<=m;i++)
72     {
73         x=lower_bound(mp,mp+n,qs[i].l)-mp;
74         y=lower_bound(mp,mp+n,qs[i].r)-mp;
75         int res=qs[i].result;
76         int a=find(x);
77         int b=find(y);
78         if(a==b)
79         {
80             if(d[x]^d[y]==res)
81                 continue;
82             else
83             {
84                 printf("%d
",i-1);
85                 flag=1;
86                 break;
87             }
88         }
89         else
90         {
91             far[a]=b;
92             d[a]=d[x]^d[y]^res;
93         }
94     }
95     if(!flag)
96         printf("%d
",m);
97 }