题意

给定一个 $n\times m$ 的网格，有若干 K 和 W，剩余为空地。$q$ 次操作，要求支持将某个 K 移动到相邻空地上，以及给定空地 $(x,y)$，判断若将 $(x,y)$ 变为 W，所有 K 是否可在不经过 W 的前提下连通，若是则将 $(x,y)$ 变为 W。强制在线，$n,m\le 10^3,q\le 10^6$。

题解

网格图是平面图，连通性可考虑其对偶图。从《Trick：平面图转对偶图》偷了一张图来，黑色点边为原图，红色点边为对偶图。最外圈点实际均为无限面，其间的边初始均存在。对于每个 W，将对应黑点四周的红边均加入，表示原图中这些黑边被割开了。在四个角处也补上红点和红边，之后原图连通块即新图某个环内部的黑点。

有了上述结论，合法条件变为所有 K 在红边围出的同一区域内，也就是对偶图每个环内要么没有 K，要么有全部的 K。考虑刻画环内 K 的集合，对于每个 K，其在环内当且仅当其右侧有奇数条环上的边。使用异或哈希，给每个 K 一个哈希值，定义竖边的权值为其左侧所有 K 的哈希值异或和，则环内所有 K 的哈希值异或和与竖边权值异或和相同。

注意到 K 向空地移动经过的边必然不存在，可直接修改权值。左右移动只需要单边修改，然而上下移动就爆炸了。考虑将上下移动带来的变化量放到横边上，当 K 上下移动时，就将经过的横边权值异或上该 K 的哈希值。这样环内的值即为所有边权异或和，且每次移动只会更改一条边的权值。

此时问题转化为每次加四条边，若会产生权值异或和非 $0,V$ 的环则不加，其中 $V$ 为所有 K 的哈希值异或和。考虑在对偶图上维护每个点到连通块根节点的路径异或和。对于每个环，在最后一条边 $(u,v,w)$ 加入时 $u,v$ 在同一连通块，此时查询两者到根路径异或和 $d_u,d_v$，并检查 $d_u\oplus d_v\oplus w$ 是否为 $0,V$ 即可。$u,v$ 到根的路径有交没问题，因为这部分会被异或掉；新边将某个环分成两半也没问题，因为任意一半合法可推出另一半必然也合法。

于是使用带权并查集维护即可，若加边导致非法需要将本轮已加的边撤销掉，或许不太能路径压缩，复杂度是 $\mathcal O(nm+q\log (nm))$ 的。

参考实现

#include<bits/stdc++.h>
#define ll unsigned long long
#define id(x,y) (((x)-1)*(m+1)+(y))
using namespace std;
const int N=1010;
const int M=N*N;
mt19937_64 rnd(time(0));
int read()
{
	int s=0; char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s;
}
char gc() {char c=getchar(); while(c!='.'&&c!='W'&&c!='K') c=getchar(); return c;}
int n,m,q,C,tp,f[M],s[M],st[M]; ll V,v[N][N],h[N][N],w[N][N],d[M]; char a[N][N];
int finds(int x,ll &w)
{
    if(f[x]==x) return x;
    w^=d[x]; return finds(f[x],w);
}
bool mg(int x,int y,ll w)
{
    ll wx=0,wy=0; x=finds(x,wx),y=finds(y,wy);
    if(x==y) return (wx^wy^w)==V||!(wx^wy^w);
    if(s[x]>s[y]) swap(x,y);
    f[x]=y,s[y]+=s[x],d[x]=(wx^wy^w),st[++tp]=x; return 1;
}
bool ins(int x,int y)
{
    tp=0;
    if(!mg(id(x,y),id(x+1,y),h[x][y])) return 0;
    if(!mg(id(x,y),id(x,y+1),w[x][y])) return 0;
    if(!mg(id(x+1,y),id(x+1,y+1),w[x+1][y])) return 0;
    if(!mg(id(x,y+1),id(x+1,y+1),h[x][y+1])) return 0;
    return 1;
}
int main()
{
    freopen("connectivty.in","r",stdin);
    freopen("connectivty.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
    {
        a[i][j]=gc();
        if(a[i][j]=='K') v[i][j]=rnd(),V^=v[i][j];
    }
    for(int i=1;i<=(n+1)*(m+1);i++) f[i]=i,s[i]=1;
    for(int i=1;i<=n+1;i++) for(int j=1;j<=m+1;j++)
    {
        h[i][j]=h[i][j-1]^v[i][j-1];
        if((i==1||i==n+1)&&j<=m) mg(id(i,j),id(i,j+1),0);
        if((j==1||j==m+1)&&i<=n) mg(id(i,j),id(i+1,j),h[i][j]);
    }
    q=read();
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]=='W'&&!ins(i,j))
    {
        while(q--)
        {
            int o=read(),x=read(),y=read();
            if(o==1) putchar('0');
            else x=read(),y=read();
        }
        return 0;
    }
    while(q--)
    {
        int o=read(),x=read()^C,y=read()^C;
        if(o==1)
        {
            if(!ins(x,y))
            {
                while(tp)
                {
                    int x=st[tp--];
                    d[x]=0,s[f[x]]-=s[x],f[x]=x;
                }
                putchar('0');
            }
            else C++,putchar('1');
        }
        else
        {
            int X=read()^C,Y=read()^C;
            if(X==x) h[x][y+(Y==y+1)]^=v[x][y];
            else w[x+(X==x+1)][y]^=v[x][y];
            swap(v[x][y],v[X][Y]);
        }
    }
    return 0;
}