ACM模版

描述

题解

这个问题我想半天也没想到怎么和并查集挂上钩了，看来是我并查集太弱了，找了找题解才搞懂了，但是感觉网上的题解前篇一律，开头讲的很容易懂，但是后边到为什么要开两倍大小的数组讲的却不是那么容易理解，所以我就按照我自己的理解再写一下吧，权当补充吧，如果我的理解错了，烦请众神拍砖~~~

首先，我们知道如果 [left, right] 为even，那么说明这里有偶数个1，所以可以判定，[1, left - 1] 和 [1, right] 的奇偶性相同，可以划分到一个集合内；
其次，如果 [left, right] 为odd，那么说明这里有奇数个1，所以可以判定，[1, left - 1] 和 [1, right] 的奇偶性不同，同样可以放到一个集合内；
但是问题来了，如果不做任何处理就同样放在一个集合，那么肯定是毫无意义的，我们需要第一种情况的集合为相同奇偶性的集合，第二种情况的放在不同奇偶性的集合，那么问题来了，我们如何搞这个集合呢？

网上很多网友都是说将数组开大两倍，用 [n + 1, 2 * n] 来表示不同的集合（[1, n] 自然就表示相同了），实际上这样解释并不合适，根据我对代码的理解，我感觉可以这样定义，同样是开两倍大的数组，不过 [1, n] 用来表示该区间（前缀区间，希望我妄下定义大家可以理解我的意思）为奇（偶），然后偏移 n 对应表示区间为偶（奇）。

所以，第一种情况有分为两种，
都是奇（偶），join(left - 1, right);，
都是偶（奇），join(left - 1 + N, right + N);；
同理，第二种情况也可以分为两种，
前奇（偶）后偶（奇），join(left - 1, right + N);，
前偶（奇）后奇（偶），join(left - 1 + N, right);。

希望我的理解没有毛病，如果有的话，记住拍砖啊~~~

代码

#include <iostream>
#include <cstdio>

const int MAXN = 1e5 + 10;

int pre[MAXN * 2];

int find(int x)
{
    if (pre[x] != x)
    {
        pre[x] = find(pre[x]);
    }
    return pre[x];
}

void join(int x, int y)
{
    x = find(x);
    y = find(y);

    pre[y] = x;
}

void init()
{
    for (int i = 0; i <= MAXN * 2; i++)
    {
        pre[i] = i;
    }
}

int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    init();

    int N, Q;
    std::cin >> N >> Q;

    int left, right;
    int cnt = 0, flag = -1;
    char s[5];
    while (++cnt)
    {
        if (cnt > Q)
        {
            break;
        }
        scanf("%d%d%s", &left, &right, s);
        if (s[0] == 'e')
        {
            if (find(left - 1 + N) == find(right) && find(left - 1) == find(right + N))
            {
                flag = cnt;
                break;
            }
            else
            {
                join(left - 1, right);
                join(left - 1 + N, right + N);
            }
        }
        else
        {
            if (find(left - 1) == find(right) && find(left - 1 + N) == find(right + N))
            {
                flag = cnt;
                break;
            }
            else
            {
                join(left - 1, right + N);
                join(left - 1 + N, right);
            }
        }
    }

    std::cout << flag << '\n';

    return 0;
}