用链表求出ga,gb,稍微有一点复杂,需要比较前驱的前驱,后继的后继。

for(int i=1;i<=n;i++)ys[h[i].id]=i,nxt[i]=i+1,prv[i]=i-1;int l=1,r=n;
    nxt[n]=0;
    for(int i=1;i<n;i++)
    {
        int now=ys[i],p=prv[now],q=nxt[now];
        if(l==now){l=nxt[l];ga[i]=h[nxt[q]].id;gb[i]=h[q].id;}
        else if(r==now){r=prv[r];ga[i]=h[prv[p]].id;gb[i]=h[p].id;}
        else
        {
            if(h[now].d-h[p].d<=h[q].d-h[now].d)
            {
                gb[i]=h[p].id;
                if(!prv[p])ga[i]=h[q].id;
                else if(h[q].d-h[now].d>=h[now].d-h[prv[p]].d)ga[i]=h[prv[p]].id;
                else ga[i]=h[q].id;
            }
            else
            {
                gb[i]=h[q].id;
                if(!nxt[q])ga[i]=h[p].id;
                else if(h[now].d-h[p].d>h[nxt[q]].d-h[now].d)ga[i]=h[nxt[q]].id;
                else ga[i]=h[p].id;
            }
        }
        prv[q]=p;nxt[p]=q;
    }

之后预处理出从每个地方出发$2^i$天到达的地点。
需要确定谁先开车,因此都计算开多一维记录第一天谁先开车。
再求一求这$2^i$天中小A开车的距离,以及小B开车的距离。
设$f_{i,j,k}$表示$2^i$次天从$j$城市出发,$k$先开车,其他定义是类似的。
那么有

for(int i=1;i<=n;i++)da[0][i][0]=abs(a[i]-a[ga[i]]),db[0][i][1]=abs(a[i]-a[gb[i]]),da[0][i][1]=db[0][i][0]=0;
    for(int i=1;i<=n;i++)
    {
        da[1][i][0]=da[0][i][0];
        da[1][i][1]=da[0][f[0][i][1]][0];
        db[1][i][0]=db[0][f[0][i][0]][1];
        db[1][i][1]=db[0][i][1];
    }
    for(int i=2;i<t;i++)
        for(int j=1;j<=n;j++)
        {
            da[i][j][0]=da[i-1][j][0]+da[i-1][f[i-1][j][0]][0];
            da[i][j][1]=da[i-1][j][1]+da[i-1][f[i-1][j][1]][1];
            db[i][j][0]=db[i-1][j][0]+db[i-1][f[i-1][j][0]][0];
            db[i][j][1]=db[i-1][j][1]+db[i-1][f[i-1][j][1]][1];
        }

预处理好后,对于提问1,分别求一下从每一个城市出发的$la,lb$,比较一下。
提问2,就相当于从一个城市出发,类似拼凑地从大到小枚举$2^i$,如果路程不超过,则累加上,并转移到那个城市上。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
using namespace std;
const int N=1e5+10;
const double inf=1e9;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar(x%10+48);
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{int d,id;bool operator <(const node a)const{return d<a.d;}}h[N];
struct Ans{int id;double d;};
int a[N],ys[N],n,m,nxt[N],prv[N],ga[N],gb[N];
void prepare()
{
    qr(n);
    for(int i=1;i<=n;i++)qr(a[i]),h[i]=(node){a[i],i};sort(h+1,h+n+1);
    for(int i=1;i<=n;i++)ys[h[i].id]=i,nxt[i]=i+1,prv[i]=i-1;int l=1,r=n;
    nxt[n]=0;
    for(int i=1;i<n;i++)
    {
        int now=ys[i],p=prv[now],q=nxt[now];
        if(l==now){l=nxt[l];ga[i]=h[nxt[q]].id;gb[i]=h[q].id;}
        else if(r==now){r=prv[r];ga[i]=h[prv[p]].id;gb[i]=h[p].id;}
        else
        {
            if(h[now].d-h[p].d<=h[q].d-h[now].d)
            {
                gb[i]=h[p].id;
                if(!prv[p])ga[i]=h[q].id;
                else if(h[q].d-h[now].d>=h[now].d-h[prv[p]].d)ga[i]=h[prv[p]].id;
                else ga[i]=h[q].id;
            }
            else
            {
                gb[i]=h[q].id;
                if(!nxt[q])ga[i]=h[p].id;
                else if(h[now].d-h[p].d>h[nxt[q]].d-h[now].d)ga[i]=h[nxt[q]].id;
                else ga[i]=h[p].id;
            }
        }
        prv[q]=p;nxt[p]=q;
    }
}
int f[18][N][2],da[18][N][2],db[18][N][2],la,lb,t;
void calc(int s,int x)
{
    la=0;lb=0;int p=s;
    for(int i=t-1;~i;i--)
        if(f[i][p][0]&&la+da[i][p][0]+lb+db[i][p][0]<=x)
        {
            la+=da[i][p][0],lb+=db[i][p][0];
            p=f[i][p][0];
        }
}
int main()
{
    prepare();t=log(n)/log(2);
    for(int i=1;i<=n;i++)f[0][i][0]=ga[i],f[0][i][1]=gb[i];
    for(int i=1;i<=n;i++)
    {
        f[1][i][0]=f[0][f[0][i][0]][1];
        f[1][i][1]=f[0][f[0][i][1]][0];
    }
    for(int i=2;i<t;i++)
        for(int j=1;j<=n;j++)
        {
            f[i][j][0]=f[i-1][f[i-1][j][0]][0];
            f[i][j][1]=f[i-1][f[i-1][j][1]][1];
        }
    for(int i=1;i<=n;i++)da[0][i][0]=abs(a[i]-a[ga[i]]),db[0][i][1]=abs(a[i]-a[gb[i]]),da[0][i][1]=db[0][i][0]=0;
    for(int i=1;i<=n;i++)
    {
        da[1][i][0]=da[0][i][0];
        da[1][i][1]=da[0][f[0][i][1]][0];
        db[1][i][0]=db[0][f[0][i][0]][1];
        db[1][i][1]=db[0][i][1];
    }
    for(int i=2;i<t;i++)
        for(int j=1;j<=n;j++)
        {
            da[i][j][0]=da[i-1][j][0]+da[i-1][f[i-1][j][0]][0];
            da[i][j][1]=da[i-1][j][1]+da[i-1][f[i-1][j][1]][1];
            db[i][j][0]=db[i-1][j][0]+db[i-1][f[i-1][j][0]][0];
            db[i][j][1]=db[i-1][j][1]+db[i-1][f[i-1][j][1]][1];
        }
    int x0;qr(x0);
    calc(1,x0);
    Ans ans=(Ans){1,lb?1.0*la/lb:0x3f3f3f3f};
    for(int i=2;i<=n;i++)
    {
        calc(i,x0);
        if(1.0*la/lb<ans.d||(1.0*la/lb==ans.d&&a[ans.id]<a[i]))
        {
            ans.d=1.0*la/lb;
            ans.id=i;
        }
    }
    qw(ans.id);puts("");
    qr(m);
    for(int i=1,s,x;i<=m;i++)
    {
        qr(s),qr(x);
        calc(s,x);
        qw(la),putchar(' '),qw(lb);puts("");
    }
    return 0;
}