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

kkxacj · 2025-10-24 12:54:08 · 题解

前言

迷你赛考的，写的克鲁斯卡尔重构树然后被卡空间了，气笑了，主要原因是我开了个 vetcor，把它改了就可以了。

但是原题都是 1024MB 就不能开大点吗/fn/fn

思路

每次区间异或肯定不好搞，每次区间修改相信都能想到前缀异或和转为每次选单点异或吧（大概叫这个名字，反正就是原来的 s_i 新串所有 S_j 的异或和，1\le j\le i）。

因为前缀异或和对应的异或串是唯一的，所以肯定没问题。

然后题目转化成多一个可以同时异或 S_l,S_{r+1}，考虑认为这个是连边，那么看两个串是否相等，就是每一个联通块，x,y 的 1 出现次数的奇偶性每一个联通块都是一样的，注意这里有一个特殊的，如果联通块里有 m+1 即出现 r=n，那么这个联通块就可以不管（相当于单点异或）。

知道集合哈希的现在已经会完了，不过其实还有一个离线做法。

一个显然的，对于当前边集确定时，如果 x 和 y 不相等，那么减少边集中的一条边，x 和 y 一定也不相等。

这启发我们离线，我们可以先强行使得所有点都在一个联通块内，然后从后往前撤销操作，这里我们可以建克鲁斯卡尔重构树加并查集维护，然后撤销就容易了。

假设点 x 与 y 当前是一类点，然后将两个联通块分离时，如果两边的奇偶性还是一样的，那么这两个点还是一类点，注意到本质不同的点最多 n 个，我们直接搞一个数组，nxt_{i,0/1,0/1} 表示编号为 i 然后另外两个联通块奇偶性是 0/1 和 0/1 时对应的编号。

别忘了前面说的，我们对于克鲁斯卡尔重构树跑一遍然后就知道哪些点子树里面有 m+1 这个点，然后假设当前分离 a,b 两个联通块，如果 a 里面有 m+1 这个点（dfn 序显然可以看）那么 nxt_{i,0/1,z} 都要赋成一样的下标。

嗯，然后询问就看两个点是否是一个编号即可，具体实现见代码，但因为此代码是赛时卡空间代码上修改而来的，所以数组这些可能会循环使用请见谅。

code

#include<bits/stdc++.h>
using namespace std;
/*
read(a,b,...)读入若干变量。
write(x)输出一个变量，没有其他输出。
write(a,b...)输出若干变量，以空格分割，以换行结尾。
*/
namespace IO {
    constexpr auto maxn = 1 << 20;
    char in[maxn], out[maxn],*p1 = in,*p2 = in,*p3 = out;
    #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
    #define flush() (fwrite(out,1,p3-out,stdout))
    #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
    class Flush {
    public:
        ~Flush() {
            flush();
        }
    } _;

    namespace usr {
        template<typename type>
        inline type read(type &x) {
            x = 0;
            bool flag(0);
            char ch = getchar();
            while (!isdigit(ch)) flag ^= ch == '-', ch = getchar();
            while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
            return flag ? x = -x : x;
        }
        template<typename type>
        inline void write(type x) {
            x < 0 ? x = -x, putchar('-') : 0;
            static short Stack[50], top(0);
            do Stack[++top] = x % 10, x /= 10;
            while (x);
            while (top) putchar(Stack[top--] | 48);
        }
        inline char read(char &x) {
            do x = getchar();
            while (isspace(x));
            return x;
        }
        inline char write(const char &x) {
            return putchar(x);
        }
        inline void read(char *x) {
            static char ch;
            read(ch);
            do *(x++) = ch;
            while (!isspace(ch = getchar()) && ~ch);
        }
        template<typename type>inline void write(type *x) {
            while (*x)putchar(*(x++));
        }
        inline void read(string &x) {
            static char ch;
            read(ch), x.clear();
            do x += ch;
            while (!isspace(ch = getchar()) && ~ch);
        }
        inline void write(const string &x) {
            for (int i = 0, len = x.length(); i < len; ++i)putchar(x[i]);
        }
        template<typename type, typename...T>inline void read(type &x, T&...y) {
            read(x), read(y...);
        }
        template<typename type, typename...T>
        inline void write(const type &x, const T&...y) {
            write(x), putchar(' '), write(y...), sizeof...(y) ^ 1 ? 0 : putchar('\n');
        }
        template<typename type>
        inline void put(const type &x, bool flag = 1) {
            write(x), flag ? putchar('\n') : putchar(' ');
        }
    }
#undef getchar
#undef flush
#undef putchar
} using namespace IO::usr;
bool st; 
const int N = 5e6+10;
int op,n,m,q,f[N<<1],cnt,cnt1,x,y,L[N<<1],R[N<<1],o,v2[N][2][2],cnt3,cnt4,cnt5,len3,A[N],D[N];
bool ans[N<<1],bj[N<<1],siz[N<<4];
string s;
struct w
{
    int x,y;
    bool z,op;
}Q[N<<1];
int find(int x)
{
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}
bool ed;
void dfs(int x)//dfn序 
{
    if(x == m+1) bj[x] = 1;//bj_i=1那么就是有m+1这个点 
    if(L[x]) dfs(L[x]),bj[x] |= bj[L[x]];
    if(R[x]) dfs(R[x]),bj[x] |= bj[R[x]];
}
int ly;
signed main()
{
//  cerr<<(&st-&ed)*1.0/1024/1024<<'\n';
//  freopen("nousporism.in","r",stdin);
//  freopen("nousporism.out","w",stdout);
    read(n,m,q); len3 = 1; read(s); 
    cnt = m+1;
    for(int i = 1;i <= m+1;i++) f[i] = i;
    for(int i = 1;i <= n;i++) 
    {A[i] = D[i] = len3;
        for(int j = 0;j < m;j++)
            if(s[j+ly] == '0') siz[D[i]] = 0,D[i]++,len3++;
            else siz[D[i]] = 1,D[i]++,len3++; o = 0; 
        for(int j = 1;j <= m+20;j++) D[i]++,len3++; len3++;
        o = siz[A[i]]; ly += m;
        for(int j = 2;j <= m;j++)
        {
            if(o == siz[A[i]+j-1]) siz[A[i]+j-1] = 0;
            else siz[A[i]+j-1] = 1,o ^= 1; //,cout<<i<<" % "<<siz[i][j]<<'\n';
        }
    }
    for(int i = 1;i <= q;i++)
    {
        read(op,Q[i].x,Q[i].y);
        if(op == 2) Q[i].op = 0; 
        else Q[i].op = 1;
        if(Q[i].op == 1)
        { Q[i].y++;
            x = find(Q[i].x),y = find(Q[i].y);
            if(x != y)
            { Q[i].z = 1;
                cnt++,f[cnt] = f[x] = f[y] = cnt; L[cnt] = x,R[cnt] = y;
                for(int j = 1;j <= n;j++)
                {
                    if(siz[A[j]-1+x] && siz[A[j]-1+y]) siz[A[j]+cnt-1] = 0;
                    else siz[A[j]+cnt-1] = siz[A[j]-1+x]|siz[A[j]-1+y];
                }
            }
        }
    }
    for(int i = 2;i <= m+1;i++)
        if(find(1) != find(i))//没有合并 
        {
            Q[++q].op = 1,Q[q].x = 1,Q[q].y = i;
            x = find(Q[q].x),y = find(Q[q].y);
            if(x != y)
            { Q[q].z = 1;
                cnt++,f[cnt] = f[x] = f[y] = cnt; L[cnt] = x,R[cnt] = y;
                for(int j = 1;j <= n;j++) 
                {
                    if(siz[A[j]-1+x] && siz[A[j]-1+y]) siz[A[j]+cnt-1] = 0;
                    else siz[A[j]+cnt-1] = siz[A[j]-1+x]|siz[A[j]-1+y];
                }
            }
        } cnt1 = 1;
    dfs(cnt);
    for(int i = 1;i <= n;i++) f[i] = 1;
    for(int i = q;i >= 1;i--)
    {
        if(Q[i].op == 1)
        {
            if(Q[i].z == 1)//有用的边 
            {
                for(int j = 1;j <= n;j++)
                {
                    x = siz[A[j]-1+L[cnt]],y = siz[A[j]-1+R[cnt]];
                    v2[f[j]][x][y] = 0;
                } cnt4 = 0;
                for(int j = 1;j <= n;j++)
                {
                    x = siz[A[j]-1+L[cnt]],y = siz[A[j]-1+R[cnt]];
                    if(!v2[f[j]][x][y])
                    {
                        v2[f[j]][x][y] = ++cnt4;
                        if(bj[L[cnt]]) v2[f[j]][!x][y] = cnt4;
                        if(bj[R[cnt]]) v2[f[j]][x][!y] = cnt4;
                    }//重新赋空间 
                    f[j] = v2[f[j]][x][y];
                }
                //  cout<<i<<" ^^ "<<j<<" ** "<<v1[j]<<" "<<x<<" "<<y<<" "<<'\n';
                //节省空间捏 
                cnt--;
            }
        }
        else 
        {
        //  cout<<cnt1<<" "<<v1[Q[i].x]<<" "<<v1[Q[i].y]<<'\n';
            if(f[Q[i].x] != f[Q[i].y]) ans[i] = 0;//一类点 
            else ans[i] = 1;
        }
    }
    for(int i = 1;i <= q;i++)
        if(Q[i].op == 0)
        {
            if(ans[i] == 0) putchar('H'),putchar('a'),putchar('r'),putchar('u');
            else putchar('M'),putchar('a'),putchar('s'),putchar('u'),putchar('k'),putchar('o');
            putchar('\n');
        }
    return 0;
}