自动搬运

查看原文

来自洛谷，原作者为

	是青白呀 咕咕咕？咕咕咕！

搬运于2025-08-24 23:03:57，当前版本为作者最后更新于2024-09-21 09:16:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个暴力的想法是对于每一个补给站 $(i,j)$，将其运输范围内的点用边权为 $h_{i,j}$ 的边连通起来。此时需要最大化路径上的最小权值，套路化地跑最大生成树，然后建立 Kruskal 重构树，对每次询问求解 LCA 即可。

考虑去除不优的边，减少边的数量。首先不难观察到一个结论：若点 $(x,y)$ 能被补给站 $(i,j)$ 覆盖，则 $(x,j)$ 和 $(i,y)$ 一定都能被补给站 $(i,j)$ 覆盖到。其原因是任意两个四连通相邻的位置高度差的绝对值不超过 $1$，因此 $h$ 的减少量一定不大于曼哈顿距离的减少量。也因此，任意补给站的覆盖范围都是一个连通块，且均可以通过先向左右方向走、再向上下方向走的方式抵达每一个覆盖位置。

于是不难想到将该图简化为相邻方格内连边，需要对于每一个相邻的方格，求得覆盖他们两个的补给站的 $h$ 最大值。

观察满足被补给站 $(i,j)$ 覆盖的式子：$h_{i,j}−h_{x,y}+p_{i,j}-|i−x|-|j−y|\geq 0$。你发现从 $(x,y)$ 走到距离 $(i,j)$ 更远的格子时，左式的新值与 $(i,j)$ 的具体位置无关，仅与 $(x,y)$ 处左式的原值有关。而根据 $h$ 的变化量不大于曼哈顿距离的变化量，合法时左式仅有 $[0,p_{i,j}]$ 几种取值，在题目 $p$ 的限制下只能为 $[0,9]$。于是不妨维护 $f_{i,j,k}$ 表示覆盖 $(i,j)$、且左式值为 $k$ 的所有补给站中 $h$ 的最大值。根据上文得到的结论，按照任意顺序在四个方向上分别将所有点进行一次转移，即可得到正确的取值。

对于相邻两个格子 $(i,j)$ 和 $(x,y)$，同时覆盖这两个格子意味着一定存在某个格子在另一个格子的远端。因此我们枚举 $k$，分别判断 $f_{i,j,k}$ 能否转移到 $f_{x,y,k}$ 以及 $f_{x,y,k}$ 能否转移到 $f_{i,j,k}$ 即可。则两点间的边权为所有可行转移的最大 $h$。

对建出来的新图跑最大生成树，然后建立 Kruskal 重构树即可。复杂度 $O(nm(p+\log nm)+q\log nm)$。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long
#define qingbai 666
using namespace std;
typedef long long ll;
const int N=305,M=2e5+5,S=(1<<15)+5,inf=(ll)1e18+7,mo=998244353;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int n,m,q;
int h[N][N],p[N][N],f[N][N][10];
int maxh[N][N],maxl[N][N];
int fa[N*N*2][20],dep[N*N*2];
struct edge{
    int x,y,val;
    friend bool operator<(edge x,edge y){
        return x.val>y.val;
    }
}e[N*N*2];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},cnte;
void update(int x,int y,int op){
    int lx=x+dx[op],ly=y+dy[op];
    repp(k,9,0){
        int nwk=k+h[lx][ly]-h[x][y]-1;
        if(nwk<0)break;
        f[x][y][nwk]=max(f[x][y][nwk],f[lx][ly][k]);
    }
}
void getedge(int k){
    rep(i,1,n-1){
        rep(j,1,m){
            if(k+h[i][j]-h[i+1][j]-1>=0)maxl[i][j]=max(maxl[i][j],f[i][j][k]);
            if(k+h[i+1][j]-h[i][j]-1>=0)maxl[i][j]=max(maxl[i][j],f[i+1][j][k]);
        }
    }
    rep(i,1,n){
        rep(j,1,m-1){
            if(k+h[i][j]-h[i][j+1]-1>=0)maxh[i][j]=max(maxh[i][j],f[i][j][k]);
            if(k+h[i][j+1]-h[i][j]-1>=0)maxh[i][j]=max(maxh[i][j],f[i][j+1][k]);
        }
    }
}
int getid(int x,int y){
    return (x-1)*m+y;
}
struct bcj{
    int fa[N*N*2];
    void init(){
        rep(i,1,n*m*2)
            fa[i]=i;
    }
    int find(int x){
        if(x==fa[x])return x;
        return fa[x]=find(fa[x]);
    }
    bool merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return 0;
        fa[x]=y;
        return 1;
    }
}B;
int val[N*N*2],cntn;
vector<int>et[N*N*2];
void dfs(int x,int f){
    dep[x]=dep[f]+1,fa[x][0]=f;
    rep(i,1,18)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(auto j:et[x])
        dfs(j,x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    repp(i,18,0)
        if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
    if(x==y)return x;
    repp(i,18,0)
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int nrt[N*N*2];
signed main(){
    read(n),read(m),read(q);
    rep(i,1,n){
        rep(j,1,m)
            read(h[i][j]);
    }
    rep(i,1,n){
        rep(j,1,m)
            read(p[i][j]);
    }
    rep(i,1,n){
        rep(j,1,m){
            rep(k,0,9)
                f[i][j][k]=-inf;
            maxh[i][j]=maxl[i][j]=-inf;
        }
    }
    rep(i,1,n){
        rep(j,1,m)
            f[i][j][p[i][j]]=h[i][j];
    }
    rep(i,2,n){
        rep(j,1,m)
            update(i,j,0);
    }
    repp(i,n-1,1){
        rep(j,1,m)
            update(i,j,1);
    }
    rep(i,1,n){
        rep(j,2,m)
            update(i,j,2);
    }
    rep(i,1,n){
        repp(j,m-1,1)
            update(i,j,3);
    }
    rep(k,0,9)
        getedge(k);
    rep(i,1,n){
        rep(j,1,m){
            if(j!=m)e[++cnte]=(edge){getid(i,j),getid(i,j+1),maxh[i][j]};
            if(i!=n)e[++cnte]=(edge){getid(i,j),getid(i+1,j),maxl[i][j]};
        }
    }
    sort(e+1,e+cnte+1);
    B.init();
    cntn=n*m;
    rep(i,1,cnte){
        int x=e[i].x,y=e[i].y;
        x=B.find(x),y=B.find(y);
        if(x==y)continue;
        val[++cntn]=e[i].val;
        B.merge(x,cntn);
        B.merge(y,cntn);
        et[cntn].push_back(x),et[cntn].push_back(y);
    }
    dfs(cntn,0);
    while(q--){
        int a,b,x,y;
        read(a),read(b),read(x),read(y);
        y=getid(x,y),x=getid(a,b);
        printf("%lld\n",max(-1ll,val[lca(x,y)]));
    }
    return 0;
}