自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

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

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

以下是正文

有结论：一次跳高只可能使得可以到达的点增加，不会使原来可以到达的点无法到达。

于是考虑在查询时如何快速得知从起点到终点需要经过的最高的山的最低高度 $h$（也就是说，只要在跳跃过程中跳到了这个高度即可）。这是一个经典问题（类似 ABC394G 的思路），可以使用 Kruskal 重构树简单地求解。

接下来处理每次最多跳 $L$ 的限制。根据上面的结论，除了最后一次跳跃，每次贪心地跳到当前能跳到的最高的山是正确的。对于每个坐标 $(x,y)$ 处理出 $\mathrm{nx}_{x,y}$ 表示 $(x,y)$ 跳一次可以到达的最高的山的坐标，发现这个东西可以倍增；于是对于每个询问就能求出最少跳几次可以到达高度 $h$。将这个答案 $+1$ 即为最终答案。

$\mathrm{nx}_{x,y}$ 可以用扫描线的技巧处理。把所有山按照高度排序，从低到高扫描所有的高度 $h'$：对于高度 $<h'-L$ 的山找出当前加入过的山中与它连通的高度最大的山（可以使用并查集维护），作为其 $\mathrm{nx}$ 的值；接着把 $\le h'$ 且未加入的山加入，并与四联通且已加入的其他山合并。这个过程可以与 Kruskal 重构树的建树过程一起做，代码量可能会小一点。

放代码（赛时代码，写得比较乱）：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
const vector<int> dx={1,-1,0,0},dy={0,0,1,-1};
template<typename T> class dsu{
  private:
    vector<T> a;
    vector<int> s;
  public:
    dsu(int n=2e5){
      a.resize(n),s.resize(n,1);
      iota(a.begin(),a.end(),0);
    }
    T leader(T x){
      return a[x]==x?x:a[x]=leader(a[x]);
    }
    inline int size(T x){
      return s[leader(x)];
    }
    inline void merge(T x,T y){
      x=leader(x),y=leader(y);
      if(x!=y)a[x]=y;
    }
    inline bool same(T x,T y){
      return leader(x)==leader(y);
    }
};
// 该并查集相较于平时使用的模板进行了一些修改
// merge(x,y) 表示令 y 为 x 的父亲
// 即合并是有顺序的，而不是启发式合并
// 目的是方便后续的 Kruskal 重构树建立
// 以及扫描线的过程中方便找集合中高度最大的点
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int h,w,l; cin>>h>>w>>l;
  vector a(h,vector<int>(w));
  for(auto &i:a)for(auto &j:i)cin>>j;
  vector<pii> p;
  vector<tpi> e;
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++){
      p.emplace_back(a[i][j],i*w+j);
      for(int d=0;d<4;d++){
        int x=i+dx[d],y=j+dy[d];
        if(min(x,y)>=0&&x<h&&y<w)
          e.emplace_back(max(a[i][j],a[x][y]),i*w+j,x*w+y);
      }
    } // 存储边
  sort(p.begin(),p.end());
  sort(e.begin(),e.end());
  int o=h*w,pt=0;
  vector<vector<int> > g(h*w<<1);
  vector<int> wt(h*w<<1,1e9);
  dsu<int> d(h*w<<1),d2(h*w);
  vector nx(h*w,vector<int>(__lg(h*w)+1));
  for(auto [q,u,v]:e){
    while(pt<h*w&&p[pt].first<q-l){
      int u=p[pt].second;
      nx[u][0]=d2.leader(u),pt++;
    } // 扫描线处理 nx
    if(d.same(u,v))continue;
    int x=d2.leader(u),y=d2.leader(v);
    if(a[x/w][x%w]<a[y/w][y%w])d2.merge(x,y);
    else d2.merge(y,x);
    u=d.leader(u),v=d.leader(v);
    d.merge(u,o),d.merge(v,o);
    g[o].emplace_back(u);
    g[o].emplace_back(v);
    wt[o++]=q;
  } // 建立 Kruskal 重构树
  while(pt<h*w){
    int u=p[pt].second;
    nx[u][0]=d2.leader(u),pt++;
  }
  for(int i=1;i<=__lg(h*w);i++)
    for(int u=0;u<h*w;u++)
      nx[u][i]=nx[nx[u][i-1]][i-1];
  // 倍增处理
  int k=__lg(o);
  vector f(o,vector<int>(k+1));
  vector<int> lv(o);
  function<void(int)> dfs=[&](int u){
    for(int i=1;i<=k;i++)
      f[u][i]=f[f[u][i-1]][i-1];
    for(int i:g[u])
      lv[i]=lv[u]+1,f[i][0]=u,dfs(i);
  };
  f[o-1][0]=o-1,dfs(o-1);
  auto mn=[&](int u,int v)->int{
    if(u==v)return 1e9;
    if(lv[u]<lv[v])swap(u,v);
    for(int i=k;~i;i--)
      if(lv[f[u][i]]>=lv[v])u=f[u][i];
    if(u==v)return wt[u];
    for(int i=k;~i;i--)
      if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    return wt[f[u][0]];
  }; // 求 u 到 v 需要经过的最高的山的最低高度
  int q; cin>>q;
  while(q--){
    int xa,ya,xb,yb; cin>>xa>>ya>>xb>>yb,xa--,ya--,xb--,yb--;
    int u=xa*w+ya,v=xb*w+yb,rs=mn(u,v),c=0;
    if(rs==a[xa][ya]){cout<<"1\n"; continue;}
    for(int i=__lg(h*w);~i;i--)
      if(a[nx[u][i]/w][nx[u][i]%w]<rs)
        u=nx[u][i],c|=1<<i; // 倍增过程
    if(u=nx[u][0];a[u/w][u%w]<rs)cout<<"-1\n";
    else cout<<c+1<<'\n';
  }
  return 0;
}