逆天贪心
设对于一个点 \(x\) 花费 \(d\) 步能走到的最左边为 \(L_{x,d}\)，最右边为 \(R_{x,d}\)。
主要证明一个东西：若 \((a,b)\) 这个询问中区间 \([L_{a,x},R_{a,x}]\) 与 \([L_{b,y},R_{b,y}]\) 有交，那么必然存在一条步数为 \(x+y\) 的路径。
证明：
分类讨论
-
当 \(val_{R_{a,x}} < val_{L_{b,y}}\)，此时显然可以到 \(L_{b,y}\)。
-
当 \(val_{R_{a,x}} > val_{L_{b,y}}\)，此时显然可以到 \(R_{a,x}\)，并且一定能在 \(y\) 步之内到 \(b\)。
\(Q.E.D\)
然后倍增即可，至于为何可以像代码中写的那样将两个端点分开考虑，仔细思考一下就容易发现这样得到的路径必定不劣。
点击查看代码
#include<bits/stdc++.h>
#define fir first
#define sec second
#define int long long
#define mkp(a,b) make_pair(a,b)
using namespace std;
typedef pair<int,int> pir;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=998244353,inf=1e18,N=1e5+5;
int n,k,q;
int a[N];
int l[N][20],r[N][20],st[N],top;
signed main(){
n=read(),k=read(),q=read();
for(int i=1;i<=n;i++) a[i]=read();
top=0;
for(int i=1;i<=n;i++){
while(top&&a[st[top]]<a[i]) top--;
if(top) l[i][0]=st[top];
else l[i][0]=i;
st[++top]=i;
}
top=0;
for(int i=n;i>=1;i--){
while(top&&a[st[top]]<a[i]) top--;
if(top) r[i][0]=st[top];
else r[i][0]=i;
st[++top]=i;
}
for(int j=1;j<=19;j++) for(int i=1;i<=n;i++)
l[i][j]=min(l[l[i][j-1]][j-1],l[r[i][j-1]][j-1]),
r[i][j]=max(r[r[i][j-1]][j-1],r[l[i][j-1]][j-1]);
while(q--){
int L=read(),R=read();
if(L>R) swap(L,R);
int ans=0;
int x,y;
x=y=L;
for(int i=19;i>=0;i--){
int pre=min(l[x][i],l[y][i]),nxt=max(r[x][i],r[y][i]);
if(nxt<R){
x=pre,y=nxt;
ans+=(1<<i);
}
}
L=y;
x=y=R;
for(int i=19;i>=0;i--){
int pre=min(l[x][i],l[y][i]),nxt=max(r[x][i],r[y][i]);
if(pre>L){
x=pre,y=nxt;
ans+=(1<<i);
}
}
cout<<ans<<'\n';
}
}