纪念模拟考考挂。
思路
首先二分查找出当前点往后走最远能去哪个点，当前点为 \(i\)，记最远能去的那个点为 \(nt_i\)。
考虑建一棵树，将 \(nt_i\) 设为 \(i\) 点的父节点。
暴力的话直接从当前点往上找，找到目标节点看几次就好了。
但显然是过不了的。
考虑使用倍增优化。
设 \(g_{i,j}\) 为从 \(i\) 往上跳 \(2^j\) 次能到达哪个点，这个可以预处理。每次往上跳时，如果当前节点为 \(nw\)，则跳到 \(g_{nw,j}\)，\(j\) 为当前指数，再将答案加上 \(2^j\)，然后能跳则跳，如果到了目标节点就可以退出了。整体类似求最近公共祖先。
注意
- 请记住，如果查找结束后并没有到目标节点，一定要将答案加上 \(1\)。不然会和我一样。
AC CODE
希望这篇题解可以帮助到你。
#include<bits/stdc++.h>
using namespace std;
int n,f,a[100005],nt[100005],q,g[100005][22],dep[100005];
vector<int>e[100005];
void dfs(int u,int fa){
dep[u]=dep[fa]+1;
g[u][0]=fa;
for(int j=1;(1<<j)<=dep[u];j++){
g[u][j]=g[g[u][j-1]][j-1];
}
for(auto v:e[u]){
if(v!=fa)dfs(v,u);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",a+i);
}
scanf("%d",&f);
for(int i=1;i<=n-1;i++){
int l=i,r=n,pos=0;
while(l<=r){
int mid=l+r>>1;
if(a[mid]<=a[i]+f){
pos=mid;
l=mid+1;
}
else {
r=mid-1;
}
}
nt[i]=pos;
}
for(int i=1;i<=n;i++){
if(nt[i]!=i){
e[nt[i]].push_back(i);
e[i].push_back(nt[i]);
}
}
dep[n+1]=-2;
memset(g,0x3f,sizeof g);
dfs(0,n+1);
scanf("%d",&q);
while(q--){
int a,b;
scanf("%d%d",&a,&b);
if(a>b)swap(a,b);
long long cnt=0;
int now=a;
for(int j=20;j>=0;j--){
if((1<<j)<=dep[now]&&g[now][j]<=b){
now=g[now][j];
cnt+=(1<<j);
if(now==b)break;
}
}
if(now!=b)cnt++;//一定要加这句话，如果当前节点还没到，那么就要再多一天。
printf("%lld\n",cnt);
}
return 0;
}