题目描述

不赘述

样例

输入

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

输出

3

方法一 带权并查集

题目每提供一次l, r, s，就相当于提供了关于l - 1 和 r两个点之前的关系。
其中我们将前缀和是奇数还是偶数作为一个点的状态。因为它可以表示两点的奇偶性是否相同。

通过带权并查集维护每个点的父节点和权值
• 父节点：表示一个集合，共有一个父节点（在同一集合内）的任意两点之间的关系可确定
• 权值：表示当前点与父节点之间的关系。
在此题中，两点间关系有两种：奇偶性相同、奇偶性不同。分别用0和1表示

存储：
• f[maxn]，表示其父节点编号，初始化为 f[ j ] = j
• d[maxn]，表示该点与其父节点的边权。在本题中为0或1，体现当前点与父节点的奇偶性是否相同。

思路：
对于每次的输入
1. 首先查看他们是否位于一个集合中（其root是否相同），并根据字符串s确定该次输入中两点的关系 t (0或1）
2. 若位于同一集合中，则比较 t 和当前集合中确定的关系
相同，继续下一次输入；不同，跳出读入，输出答案
3. 若不位于同一集合中，合并两点集合（根据当前并查集状态和 t ）
继续下一次读入

函数：

• Get(int x)：获得x点与其root的关系

int Get(int x)
{
    if (f[x] != x)
    {
        // 得到其root，并更新其所有未更新的祖先结点
        int root = Get(f[x]);
        // 维护边权
        // 维护后的边权(now-root) = now-fa + fa-root
        d[x] ^= d[f[x]];
        // 更新father为root
        f[x] = root;
    }
    return f[x];
}

• Merge(int x, int y)：将x的root连接到y的root上

void Merge(int x, int y)
{
    // 分别获取x和y的root，并更新其关系
    int rooty = Get(y);
    int rootx = Get(x);
    // 将rootx连接到rooty
    f[rootx] = rooty;
    // 维护Weight(rootx-rooty)
    // rootx-rooty = x-rootx + y-rooty + x-y
    d[rootx] = d[x] ^ d[y] ^ t;
}