[ZJOI2016]旅行者

今天也没有什么干劲，明天再努力吧。

传送门

考虑分治，当前问题是在$x\in[1,n],y\in[1,m]$的矩形中解决编号在$[1,q]$的询问，可以考虑把矩形的长边切开，变成两个相对均匀的小矩形（类似KD-tree）。

假设直线$x=mid$竖直切开了当前矩形，那么我们要处理的是所有经过这条直线的询问，枚举这条直线上的点，对每个点做一遍单源最短路更新答案。对于不经过直线的询问把它分到两个子问题中。

之后复杂度证明也类似KD-tree，其中跟KD-tree最相似的地方就是我都不会证复杂度。

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct que{
    int x1,x2,y1,y2,h;
}q[100010],tmp[100010];
struct sbfa{
    int x,y,z;
};
priority_queue<sbfa> tm;
bool operator < (sbfa c,sbfa d){return c.z>d.z;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0},ans[100010];
int o[20010],dis[20010];
int n,m,s,w[20010][4],d[20010],c[20010];
inline int id(int x,int y){return (x-1)*m+y;}
inline void dij(int x,int y,int x1,int y1,int x2,int y2,int l,int r){
    sbfa u;
    u.x=x,u.y=y,u.z=0;
    tm.push(u);
    for (int i=x1; i<=x2; i++)
        for (int j=y1; j<=y2; j++)
            dis[id(i,j)]=2e9;
    dis[id(x,y)]=0;
    while (!tm.empty()){
        u=tm.top(); tm.pop();
        x=u.x,y=u.y;
        int a=id(x,y),b;
        if (dis[a]!=u.z) continue;
        for (int i=0; i<4; i++){
            if (x+dx[i]<x1||x+dx[i]>x2) continue;
            if (y+dy[i]<y1||y+dy[i]>y2) continue;
            b=id(x+dx[i],y+dy[i]);
            if (dis[b]>dis[a]+w[a][i]){
                dis[b]=dis[a]+w[a][i];
                u.x=x+dx[i],u.y=y+dy[i],u.z=dis[b];
                tm.push(u);
            }
        }
    }
    for (int i=l; i<=r; i++)
        ans[q[i].h]=min(ans[q[i].h],dis[id(q[i].x1,q[i].y1)]+dis[id(q[i].x2,q[i].y2)]);
}
void solve(int x1,int x2,int y1,int y2,int l,int r){
    if (x2-x1>=y2-y1){
        int mid=(x1+x2)>>1;
        for (int i=y1; i<=y2; i++)
            dij(mid,i,x1,y1,x2,y2,l,r);
        int lp=l-1,rp=r+1;
        for (int i=l; i<=r; i++) tmp[i]=q[i];
        for (int i=l; i<=r; i++){
            if (tmp[i].x1<mid&&tmp[i].x2<mid)
                q[++lp]=tmp[i];
            if (tmp[i].x1>mid&&tmp[i].x2>mid)
                q[--rp]=tmp[i];
        }
        if (lp>=l) solve(x1,mid-1,y1,y2,l,lp);
        if (r>=rp) solve(mid+1,x2,y1,y2,rp,r);
    }
    else{
        int mid=(y1+y2)>>1;
        for (int i=x1; i<=x2; i++) dij(i,mid,x1,y1,x2,y2,l,r);
        int lp=l-1,rp=r+1;
        for (int i=l; i<=r; i++) tmp[i]=q[i];
        for (int i=l; i<=r; i++){
            if (tmp[i].y1<mid&&tmp[i].y2<mid)
                q[++lp]=tmp[i];
            if (tmp[i].y1>mid&&tmp[i].y2>mid)
                q[--rp]=tmp[i];
        }
        if (lp>=l) solve(x1,x2,y1,mid-1,l,lp);
        if (r>=rp) solve(x1,x2,mid+1,y2,rp,r);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        for (int j=1; j<m; j++)
            scanf("%d",&d[id(i,j)]);
    for (int i=1; i<n; i++)
        for (int j=1; j<=m; j++)
            scanf("%d",&c[id(i,j)]);
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++){
            int x=id(i,j);
            for (int k=0; k<4; k++){
                if (i+dx[k]<1||i+dx[k]>n) continue;
                if (j+dy[k]<1||j+dy[k]>m) continue;
                if (k==0) w[x][k]=d[id(i,j-1)];
                if (k==1) w[x][k]=c[id(i-1,j)];
                if (k==2) w[x][k]=d[id(i,j)];
                if (k==3) w[x][k]=c[id(i,j)];
            }
        }
    scanf("%d",&s);
    for (int i=1; i<=s; i++){
        scanf("%d%d%d%d",&q[i].x1,&q[i].y1,&q[i].x2,&q[i].y2);
        q[i].h=i;
    }
    memset(ans,10,sizeof(ans));
    solve(1,n,1,m,1,s);
    for (int i=1; i<=s; i++) printf("%d\n",ans[i]);
    return 0;
}