本题主要分为两步

• 求出每个点的最近和次近编号
• 倍增加速开车过程

第一部分无需改变。第二部分可以更精简一些。

我们发现题目已经规定了就是 $A$ 先开车去次近点， $B$ 后开车去最近点。首先考虑倍增处理每个点走了 $2^j$ 次后去了哪里。

设 $f_{i,j}$ 为从城市 $i$ 出发走了 $2^j$ 步所到的位置。

显然初始化 $f_{i,0}=ga_i$ 第一步就是由 $A$ 走向次近点，接下来下一步就要由 $B$ 走到 最近点。

走两步就相当于 $f_{i,1}$, 因此实际我们需要初始化 $f_{i,1}=gb_{f_{i,0}}$ 这个也是比较好理解的，先由 $A$ 开车走到第一个位置后，然后下一个 $B$ 要去的位置就是此时 $f_{i,0}$ 这个位置下的最近点，即 gb[f[i][0]]

对于其余的 $j\geq 2$ 的情况，倍增处理即可。

for (int i = 1; i <= n; i++) f[i][0] = ga[i];
for (int j = 1; (1 << j) <= n; j++)
{
    for (int i = 1; i <= n; i++)
    {
        if (j == 1) f[i][1] = gb[f[i][0]];
        else f[i][j] = f[f[i][j - 1]][j - 1];
    }
}

然后考虑倍增预处理走了 $2^j$ 步的距离情况。

设 $da_{i,j}$ 为 $A$ 走了 $2^j$ 步的距离， $db_{i,j}$ 同理。

首先考虑初始化问题。

$da_{i,0}=dist(i,ga_i)$ 第一步就是由 $A$ 走，所以直接初始化两点距离即可。

$db_{i,0}=0$, 第一步根本就不是由 $B$ 走的，所以走的距离是 $0$

$da_{i,1} = da_{i,0}$ 走了两步的情况下， $A$ 只参与了第一步，所以就是 $da_{i,0}$

db[i][1]=dist(f[i][0], gb[f[i][0]]) 第二步由 $B$ 参与，他走的距离是 $A$ 第一步到的城市位置，和自己接下来要去的最近点的距离。

对于其余的 $j\geq 2$ 的情况，倍增处理即可。

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

完整代码

#include <bits/stdc++.h>
#define ll long long
#define inf 1e12
#define x first
#define y second
using namespace std;
const int N = 1e5 + 5;
typedef pair<ll, int> p;
int n, ga[N], gb[N], f[N][17];
ll h[N], da[N][17], db[N][17];
void init_g()
{
    set<p> s;
    s.insert({inf, 0}), s.insert({inf + 1, 0});
    s.insert({-inf, 0}), s.insert({-inf - 1, 0});
    for (int i = n; i >= 1; i--)
    {
        auto it = s.upper_bound({h[i], i});
        it++;
        vector<p> a;
        for (int k = 0; k < 4; k++) a.push_back(*it), it--;
        ll d1 = inf, d2 = inf;
        int id1 = 0, id2 = 0;
        for (int k = 3; k >= 0; k--)
        {
            if (abs(h[i] - a[k].x) < d1)
            {
                d2 = d1, d1 = abs(h[i] - a[k].x);
                id2 = id1, id1 = a[k].y;
            }
            else if (abs(h[i] - a[k].x) < d2)
            {
                d2 = abs(h[i] - a[k].x);
                id2 = a[k].y;
            }
        }
        ga[i] = id2, gb[i] = id1;
        s.insert({h[i], i});
    }
}
ll dist(int a, int b)
{
    return abs(h[a] - h[b]);
}
void st()
{
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = ga[i];
        f[i][1] = gb[f[i][0]];
        da[i][0] = dist(i, ga[i]), db[i][0] = 0;
        da[i][1] = da[i][0], db[i][1] = dist(f[i][0], gb[f[i][0]]);
    }
    for (int j = 2; (1 << j) <= n; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            f[i][j] = f[f[i][j - 1]][j - 1];
            da[i][j] = da[i][j - 1] + da[f[i][j - 1]][j - 1];
            db[i][j] = db[i][j - 1] + db[f[i][j - 1]][j - 1];
        }
    }
}
void calc(int s, int x, int &la, int &lb)
{
    la = lb = 0;
    for (int i = 16; i >= 0; i--)
    {
        if (f[s][i] && la + lb + da[s][i] + db[s][i] <= x)
        {
            la += da[s][i], lb += db[s][i];
            s = f[s][i];
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    init_g(), st();
    int x0;
    cin >> x0;
    int res = 0, maxh = 0;
    double ans = inf;
    for (int i = 1; i <= n; i++)
    {
        int la, lb;
        calc(i, x0, la, lb);
        double k = lb ? (double) la / lb : inf;
        if (k < ans || k == ans && h[i] > maxh)
        {
            ans = k;
            maxh = h[i];
            res = i;
        }
    }
    cout << res << "\n";
    int m;
    cin >> m;
    while (m--)
    {
        int si, x0;
        cin >> si >> x0;
        int la, lb;
        calc(si, x0, la, lb);
        cout << la << " " << lb << "\n";
    }
    return 0;
}