感谢$LOJ$的数据让我调掉此题。
这道题的难点真的是预处理啊……
首先我们预处理出小$A$和小$B$在每一个城市的时候会走向哪一个城市$ga_i$和$gb_i$，我们有链表和平衡树可以解决这个问题（当然是$set$啦）。
我们设$f_{i, j, k}$表示当前轮到$k$开车（$0$为小$A$，$1$为小$B$），从城市$j$出发走$2^i$天能走到的城市，$da_{i, j, k}$和$db_{i, j, k}$分表示$k$先开车，从城市$j$出发走$2^i$天小$A$和小$B$分别行驶的路程。
然后转移就很显然了，唯一要注意的是当$i == 1$的时候$2^{i - 1}$是一个奇数，开车的人要调换一下。
对于每一个询问给定了$s$和$X$，我们只要倒序循环二进制拼凑一下行驶的里程数看看是否会超过$X$就可以计算出小$A$和小$B$分别行驶的里程数了。
第一问可以每一个城市都代进去算一下。
时间复杂度$O((n + m)logn)$。
Code：
#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair <ll, int> pin; const int N = 1e5 + ;
const int Lg = ;
const ll inf = 1LL << ;
const double eps = 1e-; int n, qn, ga[N], gb[N], f[Lg][N][];
ll a[N], la, lb, da[Lg][N][], db[Lg][N][];
set <pin> s; template <typename T>
inline T abs(T x) {
return x > ? x : -x;
} template <typename T>
inline void read(T &X) {
X = ; char ch = ; T op = ;
for(; ch > ''|| ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} inline void solve(int st, ll dis) {
int p = st;
for(int i = ; i >= ; i--) {
if(f[i][p][] != n + && la + lb + da[i][p][] + db[i][p][] <= dis) {
la += da[i][p][], lb += db[i][p][];
p = f[i][p][];
}
}
} int main() {
// freopen("drive5.in", "r", stdin); read(n);
for(int i = ; i <= n; i++) {
read(a[i]);
s.insert(pin(a[i], i));
}
a[n + ] = inf; for(int i = ; i <= n; i++) {
#define h first
#define id second set <pin> :: iterator it = s.find(pin(a[i], i)), itp, itn;
pin nxt = pin(inf, n + ), pre = pin(-inf, n + ); itp = itn = it; ++itn;
if(itn != s.end()) nxt = *itn;
if(itp != s.begin()) {
--itp;
pre = *itp;
} if(a[i] - pre.h <= nxt.h - a[i]) {
gb[i] = pre.id;
if(itp != s.begin()) {
--itp;
pre = *itp;
} else pre = pin(-inf, n + );
} else {
gb[i] = nxt.id;
if(itn != s.end()) ++itn;
if(itn != s.end()) nxt = *itn;
else nxt = pin(inf, n + );
} if(a[i] - pre.h <= nxt.h - a[i]) ga[i] = pre.id;
else ga[i] = nxt.id; s.erase(it); #undef h
#undef id
} /* for(int i = 1; i <= n; i++)
printf("%d ", ga[i]);
printf("\n");
for(int i = 1; i <= n; i++)
printf("%d ", gb[i]);
printf("\n"); */ for(int i = ; i <= n; i++)
f[][i][] = ga[i], f[][i][] = gb[i];
for(int i = ; i <= ; i++)
for(int j = ; j <= n; j++)
for(int k = ; k <= ; k++) {
if(i == )
f[i][j][k] = f[i - ][f[i - ][j][k]][ - k];
else
f[i][j][k] = f[i - ][f[i - ][j][k]][k];
} for(int i = ; i <= n; i++) {
da[][i][] = 1LL * abs(a[i] - a[ga[i]]);
da[][i][] = 0LL;
db[][i][] = 0LL;
db[][i][] = 1LL * abs(a[i] - a[gb[i]]);
} for(int i = ; i <= ; i++) {
for(int j = ; j <= n; j++)
for(int k = ; k <= ; k++) {
if(i == ) {
da[][j][k] = da[][j][k] + da[][f[][j][k]][ - k];
db[][j][k] = db[][j][k] + db[][f[][j][k]][ - k];
} else {
da[i][j][k] = da[i - ][j][k] + da[i - ][f[i - ][j][k]][k];
db[i][j][k] = db[i - ][j][k] + db[i - ][f[i - ][j][k]][k];
}
}
} // printf("%lld %lld\n", da[18][1][0], db[18][1][0]); ll x0; read(x0);
int res = ; double nowVal, resVal = 1.0 * inf;
for(int i = ; i <= n; i++) {
la = lb = 0LL;
solve(i, x0); if(lb == 0LL) nowVal = 1.0 * inf;
else nowVal = 1.0 * la / lb;
if(nowVal < resVal && abs(nowVal - resVal) > eps)
res = i, resVal = nowVal;
else if(abs(nowVal - resVal) < eps) {
if(a[res] < a[i]) res = i;
}
} printf("%d\n", res);
for(read(qn); qn--; ) {
int st; ll dis;
read(st), read(dis); la = lb = 0LL;
solve(st, dis); printf("%lld %lld\n", la, lb);
} return ;
}