- 题目大意：给出网格图，求两点之间最短路，多组询问。
- (n*mleq10^5 qleq 10^5)
- 考虑(CDQ)分治。
- 首先把询问离线，对于一个矩阵中的最短路，如果(u,v)不在统一侧，那么一定会经过平分线。
- 所以对矩阵分治理，只考虑最短路经过矩阵中线的情况，枚举中线上的任意一点做最短路，用(Dis_u+Dis_v)更新这次询问的答案即可。
- 然后把询问划分到左右两边的矩阵中去，分别递归处理即可。
- 类似于整体二分的思想？
- 代码
// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
const int N=150001;
const int M=200001;
const int inf=2e9;
int n,m,tot,q,u,cnt,nt[M],w[M],to[M],hd[N],ans[N];
int X[M],Y[M],vis[M],Dis[M];
struct Qs{int id,s,t;}Q[N],tmp[N];
vector<int>idx[N];
void link(R f,R t,R d){nt[++cnt]=hd[f],to[cnt]=t,w[cnt]=d,hd[f]=cnt;}
int gi(){
R x=0,k=1;char c=getchar();
while((c<'0'||c>'9')&&c!='-')c=getchar();
if(c=='-')k=-1,c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*k;
}
struct nd{int i,v;};
int operator < (nd x,nd y){return x.v>y.v;}
priority_queue<nd>G;
void dij(R s,R lx,R ly,R rx,R ry){
while(!G.empty())G.pop();
for(R i=lx;i<=rx;++i)
for(R j=ly;j<=ry;++j)
Dis[idx[i][j]]=inf,vis[idx[i][j]]=0;
G.push((nd){s,0});
while(!G.empty()){
R i=G.top().i,D=G.top().v;G.pop();
if(vis[i])continue;vis[i]=1,Dis[i]=D;
for(R k=hd[i];k;k=nt[k])
if(!vis[to[k]]&&lx<=X[to[k]]&&rx>=X[to[k]]&&ly<=Y[to[k]]&&ry>=Y[to[k]])
if(Dis[to[k]]>Dis[i]+w[k]){
Dis[to[k]]=Dis[i]+w[k];
G.push((nd){to[k],Dis[to[k]]});
}
}
}
void Div(R lx,R rx,R ly,R ry,R Le,R Ri){
if(Le>Ri)return ;
if(rx-lx>ry-rx){
R mid=(lx+rx)>>1;
for(R i=ly;i<=ry;++i){
dij(idx[mid][i],lx,ly,rx,ry);
for(R j=Le;j<=Ri;++j)
ans[Q[j].id]=min(ans[Q[j].id],Dis[Q[j].s]+Dis[Q[j].t]);
}
R tp1=Le-1,tp2=Ri+1;
for(R i=Le;i<=Ri;++i){
R u=Q[i].s,v=Q[i].t;
if(X[u]<mid&&X[v]<mid)tmp[++tp1]=Q[i];
if(X[u]>mid&&X[v]>mid)tmp[--tp2]=Q[i];
}
for(R i=Le;i<=Ri;++i)Q[i]=tmp[i];
Div(lx,mid-1,ly,ry,Le,tp1);
Div(mid+1,rx,ly,ry,tp2,Ri);
}
else {
R mid=(ly+ry)>>1;
for(R i=lx;i<=rx;++i){
dij(idx[i][mid],lx,ly,rx,ry);
for(R j=Le;j<=Ri;++j)
ans[Q[j].id]=min(ans[Q[j].id],Dis[Q[j].s]+Dis[Q[j].t]);
}
R tp1=Le-1,tp2=Ri+1;
for(R i=Le;i<=Ri;++i){
R u=Q[i].s,v=Q[i].t;
if(Y[u]<mid&&Y[v]<mid)tmp[++tp1]=Q[i];
if(Y[u]>mid&&Y[v]>mid)tmp[--tp2]=Q[i];
}
for(R i=Le;i<=Ri;++i)Q[i]=tmp[i];
Div(lx,rx,ly,mid-1,Le,tp1);
Div(lx,rx,mid+1,ry,tp2,Ri);
}
}
int main(){
n=gi(),m=gi();
for(R i=1;i<=n;++i){
idx[i].push_back(0);
for(R j=1;j<=m;++j){
idx[i].push_back(++tot);
X[tot]=i,Y[tot]=j;
}
}
for(R i=1;i<=n;++i)
for(R j=1;j<m;++j){
u=gi();
link(idx[i][j],idx[i][j+1],u);
link(idx[i][j+1],idx[i][j],u);
}
for(R i=1;i<n;++i)
for(R j=1;j<=m;++j){
u=gi();
link(idx[i][j],idx[i+1][j],u);
link(idx[i+1][j],idx[i][j],u);
}
q=gi();
for(R i=1;i<=q;++i){
R u=gi(),v=gi(),x=gi(),y=gi();
Q[i]=(Qs){i,idx[u][v],idx[x][y]};
}
memset(ans,63,sizeof(ans));
Div(1,n,1,m,1,q);
for(R i=1;i<=q;++i)printf("%d
",ans[i]);
return 0;
}