不难发现我们直接走过去就行了

考虑到第\(i\)行的构造方法就是把\(b\)数组作为模板，每个数和\(a_i\)异或一下就可以了

于是不难发现对于一段连续相等的\(a\)，它们在矩阵上就形成了完全相同的好几行

同时这个矩阵上只有两种本质不同的行，一种是\(b\)和\(1\)异或得到的，一种是和\(0\)异或得到的

显然我们从\((x_s,y_s)\)走到\((x_e,y_e)\)从中间的任意一行切换过去都是等价的，因为从\(y_s\)走到\(y_e\)在任何一行的代价都是一样的

于是我们把问题转化成了两个一维的问题，即从\(x_s\)走到\(x_e\)的代价加上从\(y_s\)走到\(y_e\)

把连续相同的一段缩成一个点，就是求一下环上的距离

代码

#include
    
     #define re register#define min(a,b) ((a)<(b)?(a):(b))const int maxn=1e5+5;inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}int col[2][maxn],a[maxn],b[maxn],x[2],y[2],n,m,Q,L[2];inline int dis(int o,int x,int y) {    if(x>y) std::swap(x,y);    return min(y-x,L[o]-y+x);}int main() {    n=read(),m=read();    for(re int i=1;i<=n;i++) a[i]=read();    for(re int j=1;j<=m;j++) b[j]=read();    int tot=1;col[0][1]=1;    for(re int i=2;i<=n;i++)        tot+=(a[i]!=a[i-1]),col[0][i]=tot;    if(a[n]==a[1]) {        for(re int i=n;i&&col[0][i]==tot;--i) col[0][i]=1;        --tot;    }    L[0]=tot;tot=1;col[1][1]=1;    for(re int i=2;i<=m;i++)        tot+=(b[i]!=b[i-1]),col[1][i]=tot;    if(b[m]==b[1]) {        for(re int i=m;i&&col[1][i]==tot;--i) col[1][i]=1;        --tot;    }    L[1]=tot;Q=read();    while(Q--) {        x[0]=read(),y[0]=read(),x[1]=read(),y[1]=read();        printf("%d\n",dis(0,col[0][x[0]],col[0][x[1]])+dis(1,col[1][y[0]],col[1][y[1]]));    }    return 0;}