题解：P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？

· · 题解

这题应该有紫了吧，但是不错的一道题。

因为只有 01 状态，所以这题大概率和奇偶性有关，于是将两串异或，得到对于每一个位置最终的奇偶性要求。题意转化为给定若干个区间，对于一个初始全为 0 的序列，能否通过区间加操作使得最后每一个位置为奇数或者偶数。

还是不好做，区间操作显然可以转成差分，由于只和奇偶性有关，所以对于 a_l + 1 再对于 a_{r + 1} - 1 就是对于两者都 +1。对于异或序列也去差分一下，问题转化为双点加以及给定目标序列奇偶性。

接下来这一步有点困难，需要一些直觉。由于这道题只和奇偶性有关，所以我们将上述得到的若干组 [l, r + 1] 连边。对于一个连通块内，如果想要改变此连通块内偶数个节点的奇偶性，那么是可行的，否则不可行，证明可行可以构造一种万能的方案。

也就是说异或序列的一位如果为 1 代表需要改变奇偶性，为 0 代表不需要。那么所有连通块内需要改变奇偶性的节点个数必须都是偶数。换而言之，我们用来异或的两个串如果在每个连通块内需要改变奇偶性的节点的个数的奇偶性相同，那么答案是 Yes，而先异或后差分与先差分后异或是等价的，于是这步转化显然正确。并且解决了将两个串异或起来会超时的问题。

于是我们发现本题需要用到并查集来合并连通块，最后一步的难点在于如果维护上面的那个东西。

通过 P8026 的套路，我们可以给每一个连通块赋一个随机的权值，一个串的权值就是连通块权值的和，连通块需满足在这个连通块内需要改变奇偶性的节点个数为奇数。如果两个串的权值和相同，那么这两个串大概率可以互相转化。

还有一些细节，在询问那里，看代码：

#include <bits/stdc++.h>
#define int long long
#define For(i, a, b) for (int i = (a); i <= (b); i ++)
#define foR(i, a, b) for (int i = (a); i >= (b); i --)
using namespace std;
int n, m, q;
char s[10000005];
int fa[10000005], val[10000005], vall[10000005];
bool f[10000005], ff[10000005];
mt19937 mr (20090426);
int find (int x) {
    if (fa[x] == x) return x;
    return fa[x] = find (fa[x]);
}
void solve () {
    For (i, 1, 10000001) fa[i] = i;
    For (i, 1, 10000001) val[i] = mr () % 1000000000;
    scanf ("%lld%lld%lld%s", &n, &m, &q, s + 1);
    For (i, 1, n) {
        int k = (i - 1) * m;
        if (s[k + 1] == '1') {
            f[k + 1] = 1;
            vall[i] += val[1];
        }
        foR (j, m, 2) if (s[k + j] != s[k + j - 1]) {
            f[k + j] = 1;
            vall[i] += val[j];
        }
    }/*11010   10101   01111*/
    while (q --) {
        int op, x, y;
        scanf ("%lld%lld%lld", &op, &x, &y);
        if (op == 1) {
            ++ y;
            int fx = find (x), fy = find (y), tt = mr () % 1000000000;
            if (fx != fy) {
                For (i, 1, n) {
                    bool f1, f2;
                    if (fx != m + 1) f1 = f[(i - 1) * m + fx];
                    else f1 = ff[i];
                    if (fy != m + 1) f2 = f[(i - 1) * m + fy];
                    else f2 = ff[i];
                    vall[i] -= f1 * val[fx] + f2 * val[fy];
                    f2 ^= f1;
                    if (f2) vall[i] += tt;
                    if (fy != m + 1) f[(i - 1) * m + fy] = f2;
                    else ff[i] = f2;
                }
                fa[fx] = fy;
                val[fy] = tt;
            }
        } else {
            if (vall[x] == vall[y] || abs (vall[x] - vall[y]) == val[find (m + 1)]) printf ("Masuko\n");
            else printf ("Haru\n");
        }
    }
}
signed main () {
    int _ = 1;
//  cin >> _;
    while (_ --) {
        solve ();
        cout << '\n';
    }
    return 0;
}