[JOIST 2025 Day1] 比太郎之旅 2 题解
FFTotoro
·
·
题解
有结论：一次跳高只可能使得可以到达的点增加，不会使原来可以到达的点无法到达。
于是考虑在查询时如何快速得知从起点到终点需要经过的最高的山的最低高度 h（也就是说，只要在跳跃过程中跳到了这个高度即可）。这是一个经典问题（类似 ABC394G 的思路），可以使用 Kruskal 重构树简单地求解。
接下来处理每次最多跳 L 的限制。根据上面的结论，除了最后一次跳跃，每次贪心地跳到当前能跳到的最高的山是正确的。对于每个坐标 (x,y) 处理出 \mathrm{nx}_{x,y} 表示 (x,y) 跳一次可以到达的最高的山的坐标，发现这个东西可以倍增；于是对于每个询问就能求出最少跳几次可以到达高度 h。将这个答案 +1 即为最终答案。
放代码（赛时代码，写得比较乱）：
```cpp
#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;
}
```