Luogu

LOJ

分析

将每个格点拆成四个点，分别表示从这个点往右走、往下走、往左走、往上走。

对每个点维护一个 $nxt$，表示按照题目中的方式下一步会走到哪个点上。可以发现 $nxt$ 构成了一些有向环，我们想办法对其进行维护。

考虑将环拆掉一条边变成一条有向链，并用 LCT 维护这条链。我们同时维护每一段墙是否存在，并修改连进某个点的链。在修改时，我们首先断掉连进来的边，然后再根据墙的情况修改连进来的点的 $nxt$ 并连边。这一段可以参考代码理解。

需要注意的是，在断边时需要把之前拆掉的那一条边连上，保证环只拆掉了一条边。

那么修改操作就只需要将那段墙的状态改变，然后修改两个点即可。

考虑如何询问，发现主要问题是 $s\to t$ 可能会经过拆掉的那条边。于是我们断掉 $t\to nxt_t$，再把之前拆掉的边连上，就变成了询问 $s$ 到 $t$ 的距离，在 LCT 上维护 $size$ 即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10,M=1004004+10;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n,m,Q;
int id[N][N][4],tot=0;
int f[N][N][4];

int ch[M][2],fa[M],sz[M],nxt[M];
bool nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; }
void pushup(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; }
void rotate(int x) {
    int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k];
    if (nroot(y)) ch[z][y==ch[z][1]]=x;
    ch[x][!k]=y,ch[y][k]=w;
    if (w) fa[w]=y; fa[y]=x,fa[x]=z;
    pushup(y);
}
void splay(int x) {
    while (nroot(x)) {
        int y=fa[x],z=fa[y];
        if (nroot(y)) rotate((x==ch[y][1])^(y==ch[z][1])?x:y);
        rotate(x);
    }
    pushup(x);
}
void access(int x) {
    for (int y=0;x;x=fa[y=x])
        splay(x),ch[x][1]=y,pushup(x);
}
int findroot(int x) {
    access(x),splay(x);
    while (ch[x][0]) x=ch[x][0];
    splay(x); return x;
}
void link(int x) { // link (x,nxt[x])
    if (!nxt[x]) return;
    if (findroot(x)!=findroot(nxt[x])) fa[x]=nxt[x];
}
void cut(int x) { // cut (x,nxt[x])
    if (!nxt[x]) return;
    int y=findroot(x);
    access(x),splay(x),ch[x][0]=fa[ch[x][0]]=nxt[x]=0,pushup(x);
    link(y);
}

void modify(int x,int y) {
    for (int d=0;d<4;++d) {
        int X=x+dx[d],Y=y+dy[d];
        if (X<0||X>n||Y<0||Y>m) continue;
        cut(id[X][Y][(d+2)%4]);
    }
    int p[5],s=0;
    for (int d=0;d<4;++d){ 
        int X=x+dx[d],Y=y+dy[d];
        if (X<0||X>n||Y<0||Y>m||!f[X][Y][(d+2)%4]) continue;
        p[++s]=d;
    }
    p[0]=p[s];
    for (int i=1;i<=s;++i) {
        int d=p[i],X=x+dx[d],Y=y+dy[d];
        nxt[id[X][Y][(d+2)%4]]=id[x][y][p[i-1]],link(id[X][Y][(d+2)%4]);
    }
}
int query(int s,int t) {
    int tmp=nxt[t]; cut(t),access(s),splay(s); int res=sz[s];
    nxt[t]=tmp; return res;
}

int get() {
    int a=read(),b=read(),c=read(),d=read(),e=read();
    if (a!=c) {
        if (a>c) swap(a,c),swap(b,d);
        if (!e) return id[a][b][1];
        else return id[c][d][3];
    } else {
        if (b>d) swap(a,c),swap(b,d);
        if (!e) return id[c][d][2];
        else return id[a][b][0];
    }
}

int main() {
    n=read(),m=read(),Q=read();
    for (int i=0;i<=n;++i)
        for (int j=0;j<=m;++j)
            for (int k=0;k<4;++k) id[i][j][k]=++tot;
    for (int i=0;i<=n;++i) f[i][0][1]=f[i][0][3]=f[i][m][1]=f[i][m][3]=1;
    for (int i=0;i<=m;++i) f[0][i][0]=f[0][i][2]=f[n][i][0]=f[n][i][2]=1;
    for (int i=1;i<=n;++i)
        for (int j=1;j<m;++j) f[i-1][j][1]=f[i][j][3]=read();
    for (int i=1;i<n;++i)
        for (int j=1;j<=m;++j) f[i][j-1][0]=f[i][j][2]=read();
    for (int i=0;i<=n;++i)
        for (int j=0;j<=m;++j) modify(i,j);
    while (Q--) {
        int op=read();
        if (op<=2) {
            int a=read(),b=read(),c=read(),d=read();
            for (int i=0;i<4;++i)
                if (a+dx[i]==c&&b+dy[i]==d) f[a][b][i]^=1,f[c][d][(i+2)%4]^=1;
            modify(a,b),modify(c,d);
        } else {
            int s=get(),t=get();
            printf("%d\n",query(s,t)-1);
        }
    }
    return 0;
}