题解：P11065 【MX-X4-T5】「Jason-1」占领高地

是青白呀 · 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;
}