感谢$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 + 5; const int Lg = 20; const ll inf = 1LL << 60; const double eps = 1e-6; int n, qn, ga[N], gb[N], f[Lg][N][2]; ll a[N], la, lb, da[Lg][N][2], db[Lg][N][2]; set <pin> s; template <typename T> inline T abs(T x) { return x > 0 ? x : -x; } template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } inline void solve(int st, ll dis) { int p = st; for(int i = 18; i >= 0; i--) { if(f[i][p][0] != n + 1 && la + lb + da[i][p][0] + db[i][p][0] <= dis) { la += da[i][p][0], lb += db[i][p][0]; p = f[i][p][0]; } } } int main() { // freopen("drive5.in", "r", stdin); read(n); for(int i = 1; i <= n; i++) { read(a[i]); s.insert(pin(a[i], i)); } a[n + 1] = inf; for(int i = 1; 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 + 1), pre = pin(-inf, n + 1); 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 + 1); } else { gb[i] = nxt.id; if(itn != s.end()) ++itn; if(itn != s.end()) nxt = *itn; else nxt = pin(inf, n + 1); } 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(" "); for(int i = 1; i <= n; i++) printf("%d ", gb[i]); printf(" "); */ for(int i = 1; i <= n; i++) f[0][i][0] = ga[i], f[0][i][1] = gb[i]; for(int i = 1; i <= 18; i++) for(int j = 1; j <= n; j++) for(int k = 0; k <= 1; k++) { if(i == 1) f[i][j][k] = f[i - 1][f[i - 1][j][k]][1 - k]; else f[i][j][k] = f[i - 1][f[i - 1][j][k]][k]; } for(int i = 1; i <= n; i++) { da[0][i][0] = 1LL * abs(a[i] - a[ga[i]]); da[0][i][1] = 0LL; db[0][i][0] = 0LL; db[0][i][1] = 1LL * abs(a[i] - a[gb[i]]); } for(int i = 1; i <= 18; i++) { for(int j = 1; j <= n; j++) for(int k = 0; k <= 1; k++) { if(i == 1) { da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k]; db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k]; } else { da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k]; db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k]; } } } // printf("%lld %lld ", da[18][1][0], db[18][1][0]); ll x0; read(x0); int res = 0; double nowVal, resVal = 1.0 * inf; for(int i = 1; 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 ", res); for(read(qn); qn--; ) { int st; ll dis; read(st), read(dis); la = lb = 0LL; solve(st, dis); printf("%lld %lld ", la, lb); } return 0; }