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
",s);
int m;
scanf("%lld",&m);
while(m--)
{
scanf("%lld%lld",&s,&x);
GET(s,x);
printf("%lld %lld
",X,Y);
}
return 0;
}