step1

设两个数组 \(A\) ， \(B\) ，
\(A_i\) ， \(B_i\) 表示在 \(i\) 城市时，小 \(A\) 和小 \(B\) 分别会选择去哪个点。
考虑如何预处理这两个数组。
观察到两个城市之间的距离就是两个城市海拔之差的绝对值，所以可以先根据每个城市的海拔进行排序。
排完序后， \(A_i\) ， \(B_i\) 其实就是从以 \(i-1\) ， \(i+1\) ， \(i-2\) ， \(i+2\) 这四个数为下标的海拔中找出离当前点第二近的和最近的点。
但是，由于编号较小的城市在编号较大的城市的西边，所以为了让车不往回开还需要把已经处理好的点从数列中删除。
故可以用双向链表实现。
这块的复杂度为 \(O(n \log n)\) 。

step2

设数组 \(f\) ， \(f_{i,j}\) 表示两人从 \(i\) 城市出发轮流开 \(2^j\) 天会到哪个点。
设数组 \(FA\) ， \(FB\) ，分别表示小 \(A\) 和小 \(B\)从 \(i\) 城市出发轮流开 \(2^j\) 天各会走多少路程。
先预处理 \(f\) 。
初值
\(f_{i,0}\) 就是从 \(i\) 城市出发，两人各走一步所到的城市。
即 \(f_{i,0}=B_{A_i}\) 。
转移
因为两个人在每个点所会去的城市都是固定的，所以可以直接转移。
\(f_{i,j}=f_{f_{i,j-1} \ \ ,j-1}\) 。
接下来，预处理 \(FA\) ， \(FB\) 。
为了方便，用 \(dis(i,j)\) 表示 \(i\) 城市到 \(j\) 城市的距离。
初值
比较显然。
\(FA_{i,0}=dis(i,A_i)\) ，
\(FB_{i,0}=dis(A_i,B_{A_i})\) 。
转移
和 \(f\) 类似，也可以直接转移。
\(FA_{i,j}=FA_{i,j-1}+FA_{f_{i,j-1} \ \ ,j-1}\) ，
\(FB_{i,j}=FB_{i,j-1}+FB_{f_{i,j-1} \ \ ,j-1}\) 。
这块的复杂度也是 \(O(n \log n)\) 。

step3

处理询问。
第一问其实是和第二问类似的，只要枚举出发点即可。故下面只考虑第二问。
可以把小 \(A\) 和小 \(B\) 并在一起处理，和普通的倍增处理类似。
但是，由于小 \(A\) 是先走的，所以最后还要判断一下小 \(A\) 能不能再走一步。
第一问的复杂度为 \(O(n \log n)\) ，第二问的复杂度为 \(O(m \log n)\) 。
总复杂度为 \(O(n \log n+m \log n)\) ，可以通过此题。

code

我的代码写的有亿点丑陋，但还是放一下吧。

#include<algorithm>
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
const int N=1e5+10;
const double inf=1e18;
int n,a[N];
int A[N],B[N];
int f[N][20]; 
int FA[N][20],FB[N][20];
int X,Y;
struct node
{
	int id,num;
	int pre,nxt;
}b[N];
bool cmp(node x,node y)
{
	return x.num<y.num;
}
bool CMP(node x,node y)
{
	return x.id<y.id;
}
int ABS(int x)
{
	return x>0?x:-x;
}
int get(int x,int y)
{
	return ABS(b[x].num-b[y].num);
}
void GET(int x,int y)
{
	X=0,Y=0;
	for(int i=19;i>=0;i--)
		if(f[x][i]&&X+Y+FA[x][i]+FB[x][i]<=y)
			X+=FA[x][i],Y+=FB[x][i],x=f[x][i];
	if(A[x]&&X+Y+FA[x][0]<=y) X+=FA[x][0];
} 
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	b[0].num=inf;
	for(int i=1;i<=n;i++)
		b[i].id=i,b[i].num=a[i];
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)
		b[i].pre=b[i-1].id,b[i].nxt=b[i+1].id;
	b[1].pre=0,b[n].nxt=0;
	sort(b+1,b+n+1,CMP);
	for(int i=1;i<=n;i++)
	{
		if(!b[i].pre)
		{
			B[i]=b[i].nxt;
			A[i]=b[b[i].nxt].nxt;
			b[b[i].nxt].pre=b[i].pre;
			continue;
		}
		if(!b[i].nxt)
		{
			B[i]=b[i].pre;
			A[i]=b[b[i].pre].pre;
			b[b[i].pre].nxt=b[i].nxt;
			continue;
		}
		if(get(i,b[i].pre)<=get(i,b[i].nxt))
		{
			B[i]=b[i].pre;
			if(get(i,b[b[i].pre].pre)<=get(i,b[i].nxt)) A[i]=b[b[i].pre].pre;
			else A[i]=b[i].nxt;
		}
		else
		{
			B[i]=b[i].nxt;
			if(get(i,b[i].pre)<=get(i,b[b[i].nxt].nxt)) A[i]=b[i].pre;
			else A[i]=b[b[i].nxt].nxt;
		}
		b[b[i].nxt].pre=b[i].pre;
		b[b[i].pre].nxt=b[i].nxt;
	}
	for(int i=1;i<=n;i++) f[i][0]=B[A[i]];
	for(int j=1;j<20;j++)
		for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
	for(int i=1;i<=n;i++)
	{
		FA[i][0]=get(i,A[i]);
		FB[i][0]=get(A[i],B[A[i]]);
	}
	for(int j=1;j<20;j++)
		for(int i=1;i<=n;i++)
		{
			FA[i][j]=FA[i][j-1]+FA[f[i][j-1]][j-1];
			FB[i][j]=FB[i][j-1]+FB[f[i][j-1]][j-1];
		}
	int x,s=0;
	double ans=inf;
	scanf("%lld",&x);
	for(int i=1;i<=n;i++)
	{
		GET(i,x);
		if(Y==0)
		{
			if(ans==inf&&a[i]>a[s]) s=i;
		}
		else
		{
			if(ans>(double)(X)/(double)(Y)) ans=(double)(X)/(double)(Y),s=i;
			else if(ans==(double)(X)/(double)(Y)&&a[i]>a[s]) s=i;
		}
	}
	printf("%lld\n",s);
	int m;
	scanf("%lld",&m);
	while(m--)
	{
		scanf("%lld%lld",&s,&x);
		GET(s,x);
		printf("%lld %lld\n",X,Y);
	}
	return 0;
}