时间复杂度$O(nlogX)$

int ga[N],gb[N];
//ga表示a可以走到的点,gb表示b可以走到的点
int f[2][N][M];
//f[0][i][j] 表示从i城市出发,小A先走，走了2^j步可以达到的城市的编号
//f[0][i][j] 表示从i城市出发,小B先走, 走了2^j步可以达到的城市的编号
LL da[2][N][M],db[2][N][M];
//da[0][i][j] 表示从i城市出发,小A先走，走了2^j步小A一共的距离
//da[1][i][j] 表示从i城市出发,小B先走，走了2^j步小A一共的距离
//db[0][i][j] 表示从i城市出发,小A先走，走了2^j步小B一共的距离
//db[1][i][j] 表示从i城市出发,小B先走，走了2^j步小B一共的距离

对于第一个问题，我们枚举所有点去更新距离即可

对于第二个问题,我们直接继续距离即可。

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long LL;
typedef pair<LL,int> PLI;
const int N=100010,M=17;
const LL INF=1e12;
int n;
int h[N];
int ga[N],gb[N];
int f[2][N][M];
//f[0][i][j] 表示从i城市出发,小A先走，走了2^j步可以达到的城市的编号
//f[0][i][j] 表示从i城市出发,小B先走, 走了2^j步可以达到的城市的编号
LL da[2][N][M],db[2][N][M];
//da[0][i][j] 表示从i城市出发,小A先走，走了2^j步小A一共的距离
//da[1][i][j] 表示从i城市出发,小B先走，走了2^j步小A一共的距离
//db[0][i][j] 表示从i城市出发,小A先走，走了2^j步小B一共的距离
//db[1][i][j] 表示从i城市出发,小B先走，走了2^j步小B一共的距离
void init_g()
{
    set<PLI> S;
    S.insert({INF,0}),S.insert({INF+1,0});
    S.insert({-INF,0}),S.insert({-INF-1,0}); //初始化
    PLI cand[4];
    for(int i=n;i;i--) //从后往前遍历
    {
        PLI t(h[i],i);
        auto j=S.upper_bound(t); //找到大于t的最小值
        j++; //往上一个
        for(int k=0;k<4;k++) //将上下两个点加入到候选点之中
        {
            cand[k]=*j;
            j--;
        }
        LL d1=INF,d2=INF;
        int p1=0,p2=0; //最短距离和次短距离
        for(int k=3;k>=0;k--)
        {
            LL d=abs(h[i]-cand[k].x);
            if(d<d1)
            {
                d2=d1,d1=d;
                p2=p1,p1=cand[k].y;
            }
            else if(d<d2)
            {
                d2=d;
                p2=cand[k].y;
            }
        }
        ga[i]=p2,gb[i]=p1; //记录位置
        S.insert(t); //将当前点插入集合之中
    }
}
void init_f()
{
    for(int i=1;i<=n;i++) //只有一步
    {
        f[0][i][0]=ga[i];
        f[1][i][0]=gb[i];
    }
    for(int j=1;j<M;j++) //长度从小到大
    {
        for(int i=1;i<=n;i++) //从前往后遍历
        {
            for(int k=0;k<2;k++) //枚举不同的司机
            {
                if(j==1) //当走两步的时候，驾驶员会发生变化
                {
                    f[k][i][j]=f[1-k][f[k][i][0]][0];
                }
                else //>=4步的时候，驾驶员不会发生变化
                {
                    f[k][i][j]=f[k][f[k][i][j-1]][j-1];
                }
            }
        }
    }
}
int get_dist(int a,int b) //计算距离
{
    return abs(h[a]-h[b]);
}
void init_d()
{
    for(int i=1;i<=n;i++) //只有一步
    {
        da[0][i][0]=get_dist(i,ga[i]);
        db[1][i][0]=get_dist(i,gb[i]);
    }
    for(int j=1;j<M;j++) //同理于计算到达点
    {
        for(int i=1;i<=n;i++)
        {
            for(int k=0;k<2;k++)
            {
                if(j==1)
                {
                    da[k][i][j]=da[k][i][j-1]+da[1-k][f[k][i][j-1]][j-1];
                    db[k][i][j]=db[k][i][j-1]+db[1-k][f[k][i][j-1]][j-1];
                }
                else
                {
                    da[k][i][j]=da[k][i][j-1]+da[k][f[k][i][j-1]][j-1];
                    db[k][i][j]=db[k][i][j-1]+db[k][f[k][i][j-1]][j-1];
                }
            }
        }
    }
}
void calc(int s,int x,int &la,int &lb)
{
    la=0,lb=0;
    for(int i=M-1;i>=0;i--)
    {
        if(f[0][s][i]&&la+lb+da[0][s][i]+db[0][s][i]<=x) //从A开始走，距离没有超过S
        {
            la+=da[0][s][i],lb+=db[0][s][i];
            s=f[0][s][i]; //更新到新的地方
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    init_g();
    init_f();
    init_d();
    int x;
    cin>>x;
    int res=0,max_h=0;
    double min_ratio=INF;
    for(int i=1;i<=n;i++)
    {
        int la,lb;
        calc(i,x,la,lb);
        double ratio=lb?double(la)/lb:INF;
        if(ratio<min_ratio||ratio==min_ratio&&h[i]>max_h)
        {
            min_ratio=ratio;
            max_h=h[i];
            res=i;
        }
    }
    cout<<res<<endl;
    int m;
    cin>>m;
    while(m--)
    {
        int s,x,la,lb;
        cin>>s>>x;
        calc(s,x,la,lb);
        cout<<la<<" "<<lb<<endl;
    }
    return 0;
}