P11810 商旅

用对偶图维护城镇是否仍连通

问题

P11810 [PA 2017] 商旅 / Osady i warownie
$n\times m$ 方格中有城镇、堡垒和空地。在线操作包括：尝试把一个空地变成堡垒，只有建完后所有城镇仍四连通才真正建立；以及把一个城镇移动到相邻空地。所有操作坐标都按此前成功建堡垒的次数异或加密。

数据规模：$1\le n,m\le10^3$，$0\le q\le10^6$，必须强制在线处理。

注意

本题超出我能力水平，仅作为学习记录，不完全代表我的思考。

在原方格图中动态删点维护多源连通性很难。代码改看网格边形成的对偶图：若新堡垒能让某条对偶闭环把城镇分割到两侧，就会破坏原图中的城镇连通。

每个城镇被赋予随机 uint64 权值，区域内城镇权值的异或和代表该区域。带势能并查集维护对偶点之间的异或差，于是一个闭环围住的区域权值可以由路径异或得到；它既不是零，也不是全体城镇异或和时，就说明环把城镇分成了两部分。

每次尝试建墙只会在其四条周边格点之间加入对偶边，并分别检查相邻边、对角边形成的环。城镇移动时无需重建并查集，只要沿着受影响的两条对偶边异或更新城镇的随机权值即可。

这里真正的转换是“原图删点是否断开指定点集”改为“对偶环是否切出一个非平凡城镇集合”。随机哈希承担集合相等判定，错误概率依赖 $64$ 位随机数而非完全确定性。

AC 代码

▶

AC 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128_t;

const int maxn = 1e3 + 5;
const int mod = 998244353;
const ll inf = 4e18;

ll read( ) {
    ll x = 0, f = 1;
    char ch = getchar( );
    for( ; !isdigit( ch ); ch = getchar( ) ) if( ch == '-' ) f = -1;
    for( ; isdigit( ch ); ch = getchar( ) ) x = x * 10 + ch - '0';
    return x * f;
}

struct WDSU {
/* ================================================== */
int fa[maxn * maxn], siz[maxn * maxn];
ull dis[maxn * maxn];
void init( int N ) {
    for( int i = 1; i <= N; ++ i ) fa[i] = i, siz[i] = 1, dis[i] = 0;
}
int find( int x ) {
    if( fa[x] == x ) return x;
    int f = fa[x];
    fa[x] = find( f );
    dis[x] ^= dis[f];
    return fa[x];
}
ull dist( int x, int y ) {
    find( x ), find( y );
    return dis[x] ^ dis[y];
}
void link( int x, int y, ull w ) {
    int rx = find( x ), ry = find( y );
    ull d = dis[x] ^ dis[y] ^ w;
    if( rx == ry ) return ;
    if( siz[rx] < siz[ry] ) swap( rx, ry );
    fa[ry] = rx;
    dis[ry] = d;
    siz[rx] += siz[ry];
}
bool same( int x, int y ) { return find( x ) == find( y ); }
int size( int x ) { return siz[find( x )]; }
/* ================================================== */
} wdsu;

int n, m;
int G[maxn][maxn];
ull ewr[maxn][maxn]; // 竖边 (r,c) -> (r+1,c);
ull ewc[maxn][maxn]; // 横边 (r,c) -> (r,c+1);
ull val[maxn][maxn];
ull all = 0;

int id( int x, int y ) { return ( x - 1 ) * ( m + 1 ) + y; } 

// link (r,c) -> (r+1,c);
void linkr( int r, int c ) {
    int u = id( r, c ), v = id( r + 1, c );
    wdsu.link( u, v, ewr[r][c] );
}

// link (r,c) -> (r,c+1);
void linkc( int r, int c ) {
    int u = id( r, c ), v = id( r, c + 1 );
    wdsu.link( u, v, ewc[r][c] );
}

void addwall( int r, int c ) {
    linkr( r, c ), linkr( r, c + 1 );
    linkc( r, c ), linkc( r + 1, c );
}

bool valid( int x, int y, ull w ) {
    if( !wdsu.same( x, y ) ) return 1;
    ull cir = wdsu.dist( x, y ) ^ w;
    return cir == 0 || cir == all;
}

bool check( int r, int c ) {
    int id1 = id( r, c ), id2 = id( r, c + 1 );
    int id3 = id( r + 1, c ), id4 = id( r + 1, c + 1 );

    ull top = ewc[r][c], bot = ewc[r+1][c];
    ull lef = ewr[r][c], rig = ewr[r][c+1];

    if( !valid( id1, id2, top ) ) return 0;
    if( !valid( id3, id4, bot ) ) return 0;
    if( !valid( id1, id3, lef ) ) return 0;
    if( !valid( id2, id4, rig ) ) return 0;

    if( !valid( id1, id4, lef ^ bot ) ) return 0;
    if( !valid( id2, id3, top ^ lef ) ) return 0;
    
    addwall( r, c );
    return 1;
}

void solve( ) {
    n = read( ), m = read( );
    mt19937_64 rng( 1145141919810ull );

    wdsu.init( ( n + 1 ) * ( m + 1 ) );
    for( int r = 1; r <= n; ++ r ) {
        string s; cin >> s;
        for( int c = 1; c <= m; ++ c ) {
            if( s[c-1] == '.' ) G[r][c] = 0; // 空地
            if( s[c-1] == 'W' ) G[r][c] = -1; // 堡垒
            if( s[c-1] == 'K' ) G[r][c] = 1; // 城镇
        }
    }

    for( int r = 1; r <= n; ++ r ) {
        for( int c = 1; c <= m; ++ c ) {
            if( G[r][c] == 1 ) {
                val[r][c] = rng( );
                all ^= val[r][c];
            }
        }
    } 

    // 初始化
    for( int r = 1; r <= n; ++ r ) {
        ull cur = 0;
        ewr[r][1] = 0;
        for( int c = 2; c <= m + 1; ++ c ) {
            cur ^= val[r][c-1];
            ewr[r][c] = cur;
        }
    }

    for( int r = 1; r <= n; ++ r ) {
        for( int c = 1; c <= m; ++ c ) {
            if( G[r][c] == -1 ) addwall( r, c );
        }
    }

    // 边界处理
    for( int r = 1; r <= n; ++ r ) {
        linkr( r, 1 ), linkr( r, m + 1 );
    } // 竖边
    for( int c = 1; c <= m; ++ c ) {
        linkc( 1, c ), linkc( n + 1, c );
    } // 横边

    int q = read( );
    string ans;
    ans.reserve( q );

    int k = 0;
    for( int i = 1; i <= q; ++ i ) {
        int opt = read( );
        if( opt == 1 ) {
            int r = read( ) ^ k, c = read( ) ^ k;
            if( check( r, c ) ) {
                k ++;
                ans += '1';
            }
            else {
                ans += '0';
            }
        }
        else {
            int r1 = read( ) ^ k, c1 = read( ) ^ k;
            int r2 = read( ) ^ k, c2 = read( ) ^ k;
            ull w = val[r1][c1];
            if( r1 == r2 ) {
                int c = max( c1, c2 );
                ewr[r1][c] ^= w;
            }
            else {
                int r = max( r1, r2 );
                ewc[r][c1] ^= w;
            }
            swap( val[r1][c1], val[r2][c2] );
        }
    }
    cout << ans << '\n';
}

int main( ) {
    int T = 1;
    // int T = read( );
    while( T -- ) solve( );
    return 0;
}

原始 AC 代码保持不改。随机哈希碰撞概率、对偶边编号和建墙时六条检查的几何含义，是人工确认时应重点复核的部分。