题目链接：https://ac.nowcoder.com/acm/problem/51097

知识点：

并查集，维护每个节点到根节点的距离

题目描述：

一段长为n的由0和1组成的序列，依次给出q个回答，每个回答包括该序列的一个片段子序列的起点位置x，终点位置y，和该子序列【x，y】内有奇数个1还是偶数个1。问一段序列最多能满足前几个回答。

输入描述：

第一行输入n表示序列长度，第二行输入q表示有q个回答。接下来q行，每行包括2个数字（表示子序列的起点和终点）和一个字符串，表示该子序列有奇数个1还是偶数个1，even表示有偶数个1，odd表示有奇数个1

输出描述：

输出一个数字，表示一段序列最多能满足前几个回答

输入样例：

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

输出样例

3

分析：

如果知道【2，4】内有奇数个1，【4，7】内有偶数个1，那么可以知道【2，7】内有（奇数+偶数）=奇数个1。即如果知道小的相邻片段内1的奇偶个数，就可以知道组合起来的大的片段内1的奇偶个数。把2，4，7节点放入一个集合，2节点为根节点，维护集合内其他节点x到根节点2的距离d[x]，若距离为奇数，则该节点与根节点组成的片段内1的个数为奇数，若距离为偶数，则该节点与根节点组成的片段内1的个数为偶数。因此可以通过d[i]的奇偶性确定集合内i节点与根节点组成的片段中1的个数的奇偶性。同时不难发现，同一集合内任意两个节点x，y组成的片段【x，y】中1的个数的奇偶性与(d[x]+d[y])的奇偶性相同。综上所述，一个集合内任意两点x，y组成的片段【x，y】中1的个数的奇偶性是可以确定的。以此来判断每次的回答是否会与前面的回答相矛盾。

代码思路

1、find(int x)函数：返回x的祖宗节点，同时更新路径上所有节点的d[x]

2、main()函数：依次遍历每个回答(片段序列起点x,终点y,和奇偶性t)，如果回答的两个数x,y在同一个集合内，判断d[x]+d[y]的奇偶性与回答的奇偶性t是否相同，不同则输出已经满足的回答数并return 0结束程序。

3、如果x,y不在同一个集合内，将两个集合合并，将x的祖宗阶段指向y的祖宗节点，p[find(x)]=find(y),并更新d[find(x)]=？。更新逻辑是：保证x,y两节点组成的片段【x，y】内1的奇偶个数与此次回答的奇偶性t相同。即更新后(d[x]/+d[y])的奇偶性与回答的奇偶性t相同。而更新后的d[x]/=d[x]+d[find(x)]。不难发现当d[find(x)]=d[x]+d[y]+t时，d[x]/更新后d[x]/=d[x]+d[x]+d[y]+t。d[x]/+d[y]=2d[x]+2d[y]+t。其奇偶性与t的奇偶性相同

注意

1、n的范围是1e9，所以不能开一个p[N]的数组将所有节点初始化，只需要用map将需要用到的节点存储并初始化。
2、由于所有节点都是整数，所以相邻的两个节点是默认应该在同一个集合里的，例如样例中的【1，2】和【3，4】这四个节点应该在同一个集合中，如何保证这一点呢？只需要遍历每个回答时，把回答的两个数x,y中的x减去1，由【x,y】片段内1的个数的奇偶性变为（x-1,y】片段内1的个数的奇偶性。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
unordered_map<int,int>p,d;//d[x]表示从（根节点）到（x节点）（这段子序列内）有奇数个1还是偶数个1
                          //d[x]为偶数则有偶数个1,d[x]为奇数则有奇数个1


signed find(int x)//返回x的祖宗节点并更新这条路径上的d[x]
{
    if(p[x]!=x)
    {
        int t=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=t;
    }
    return p[x];
}


signed main()
{
    cin>>n>>q;
    
    for(int i=0;i<q;i++)//遍历这q个回答
    {
        int x,y,t;
        string s;
        cin>>x>>y>>s;
        x--;//使得相邻的两段会被加入同一个集合
        
        if(p.count(x)==0) p[x]=x;//第一次出现的节点进行初始化
        if(p.count(y)==0) p[y]=y;//每个节点自己就是一个集合
        
        if(s=="even") t=0;//该序列有偶数个1
        else t=1;//该序列有奇数个1
        
        int px=find(x),py=find(y);
        
        if(px==py)//x和y在同一个集合内，一个集合内所有节点的d[x]都是已知值
        {
            if((d[y]+d[x])%2!=t)//子列(x,y]中1的奇偶个数与(d[y]+d[x])的奇偶性等价,
                                //以此来判断此回答是否会与前面的回答相矛盾
            {
                cout<<i<<endl;
                return 0;
            }
        }
        
        else//x,y不在同一个集合内
        {
            p[px]=py;
            d[px]=(t+d[x]+d[y])%2; //更新d[p[x]]
        }
    }
    
    cout<<q<<endl;//没有经过return语句，说明q个回答全都满足
}