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

dream10 · 2025-04-06 18:41:38 · 题解

Hint 1

将 01 序列做差分，长度变为 m+1，区间修改变为两个单点修改。

Hint 2

如果位置视为点，将一对单点修改视为一条边，那么一个联通块里任意两个点都可以同时异或（找到路径，每条边异或）。

Solution

对于修改，使用数据结构维护联通性。

对于询问，将两个串的差分序列异或起来，发现就是每个联通块里面的异或和是 0。

然而这不好做，但是发现联通性最多改变 m 次，每次可以对每个串进行维护。具体的维护方式就是找一个代表员记录联通块的异或和，然后询问比较哈希值。

#include<bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &a){
    #define gc getchar()
    char c;a=0;int f=1;
    while(!isdigit(c=gc))if(c=='-')f=-1;
    do a=a*10+c-'0';
    while(isdigit(c=gc));
    a*=f;
}
template<typename T>
void write(T a){
    if(a<0)putchar('-'),a=-a;
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
char GC(){
    char c=getchar();
    while(c<=32)c=getchar();
    return c;
}
template<typename T>
void chmin(T &x,T y){if(x>y)x=y;}
template<typename T>
void chmax(T &x,T y){if(x<y)x=y;}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef pair<ll,int> PLI;
typedef __int128 lll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,q;
const int MAXN=5000010;
const int MAXS=15000010;
char _s[MAXS];
char& s(const int &i,const int &j){return _s[(i-1)*m+j];}
int ufa[MAXS];
int gf(const int &x){return ufa[x]==x?x:ufa[x]=gf(ufa[x]);}
ull hsh[MAXN],pw[MAXN];
void merge(int id,int x,int y){
    if(s(id,x)=='1'){
        hsh[id]-=pw[x];
        s(id,x)='0';
        if(y<=m){
            if(s(id,y)=='0'){
                s(id,y)='1';
                hsh[id]+=pw[y];
            }else{
                s(id,y)='0';
                hsh[id]-=pw[y];
            }
        }
    }
}
signed main(){
    pw[0]=1;pw[1]=97;
    for(int i=2;i<=5000000;++i)pw[i]=pw[i-1]*pw[1];
    cin>>n>>m>>q;
    scanf("%s",_s+1);
    for(int i=1;i<=m+1;++i)ufa[i]=i;
    for(int i=1;i<=n;++i){
        for(int j=m;j>=2;--j)
            s(i,j)='0'+(s(i,j)!=s(i,j-1));
        for(int j=1;j<=m;++j)
            if(s(i,j)=='1')
                hsh[i]+=pw[j];
    }
    int op,x,y;
    while(q--){ 
        read(op);read(x),read(y);
        if(op==1){
            y++;
            x=gf(x),y=gf(y);
            if(x>y)swap(x,y);
            if(x!=y){
                for(int i=1;i<=n;++i)
                    merge(i,x,y);
                ufa[x]=y;
            }
        }else{
            if(hsh[x]==hsh[y])puts("Masuko");
            else puts("Haru");
        }
    }
    return 0;
}