加了倍增，似乎跟 $O(n^2)$ 跑的一样快。

#include <bits/stdc++.h>
using namespace std;

const int kMaxN = 100000 + 5;
const int kMaxLog = 20 + 1;

int n, m;
long long h[kMaxN];
int ga[kMaxN], gb[kMaxN];
int lg[kMaxN];

void Pre() {
	set<pair<long long, int> > s;
	s.clear();
	for (int i = n; i >= 1; i--) {
		int cnt = 0;
		pair<long long, int> dis[5]; 
		set<pair<long long, int> >::iterator it = lower_bound(s.begin(), s.end(), make_pair(h[i], i));
		set<pair<long long, int> >::iterator it1 = it, it2 = it;
		while (it1 != s.end() && cnt < 2) {
			dis[++cnt] = make_pair(abs((*it1).first - h[i]), (*it1).second);
			it1++;
		}
		if (it2 != s.begin()) {
			while (cnt < 4) {
				it2--;
				dis[++cnt] = make_pair(abs((*it2).first - h[i]), (*it2).second);
				if (it2 == s.begin()) {
					break;
				}
			}
		} 
		s.insert(make_pair(h[i], i));
		sort(dis + 1, dis + cnt + 1);
		if (cnt == 0) {
			continue;
		}
		if (cnt == 1) {
			gb[i] = dis[1].second;
			continue;
		}
		if (dis[1].first == dis[2].first) {
			if (h[dis[1].second] < h[dis[2].second]) {
				gb[i] = dis[1].second;
				ga[i] = dis[2].second;
			}
			else {
				gb[i] = dis[2].second;
				ga[i] = dis[1].second;
			}
			continue;
		}
		gb[i] = dis[1].second;
		ga[i] = dis[2].second;
	}
	lg[0] = -1;
	for (int i = 1; i <= n; i++) {
		lg[i] = lg[i / 2] + 1;
	}
}

int f[kMaxN][kMaxLog][2];
/*
f[i][j][k]
从 i 城市开始，k先开车，二者共行驶 2^j 天，现在的位置 
0 代表小 A
1 代表小 B 
*/ 
long long da[kMaxN][kMaxLog][2], db[kMaxN][kMaxLog][2];
long long x0;

pair<long long, long long> Calc(long long x, int s) {
	int p = s;
	long long la = 0, lb = 0;
	for (int i = lg[n - p + 1]; i >= 0; i--) {
		if (f[s][i][0] == 0) {
			continue;
		}
		if (la + lb + da[s][i][0] + db[s][i][0] <= x) {
			la = la + da[s][i][0];
			lb = lb + db[s][i][0];
			s = f[s][i][0];
		}
	}
	return make_pair(la, lb);
}

int main() {
	freopen("P1081_7.in", "r", stdin);
	freopen("P1081_7.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &h[i]);
	}
	Pre();
	for (int i = n; i >= 1; i--) {
		f[i][0][0] = ga[i], f[i][0][1] = gb[i];
		f[i][1][0] = f[ga[i]][0][1], f[i][1][1] = f[gb[i]][0][0];
		for (int j = 2; j <= lg[n - i + 1]; j++) {
			for (int k = 0; k <= 1; k++) {
				f[i][j][k] = f[f[i][j - 1][k]][j - 1][k]; 
			}
		}
	}
	for (int i = n; i >= 1; i--) {
		da[i][0][0] = abs(h[i] - h[ga[i]]), da[i][0][1] = 0;
		da[i][1][0] = da[ga[i]][0][1] + abs(h[i] - h[ga[i]]);
		da[i][1][1] = da[gb[i]][0][0];
		for (int j = 2; j <= lg[n - i + 1]; j++) {
			for (int k = 0; k <= 1; k++) {
				da[i][j][k] = da[i][j - 1][k] + da[f[i][j - 1][k]][j - 1][k];
			}
		} 
	}
	for (int i = n; i >= 1; i--) {
		db[i][0][1] = abs(h[i] - h[gb[i]]), db[i][0][0] = 0;
		db[i][1][1] = db[gb[i]][0][0] + abs(h[i] - h[gb[i]]);
		db[i][1][0] = db[ga[i]][0][1];
		for (int j = 2; j <= lg[n - i + 1]; j++) {
			for (int k = 0; k <= 1; k++) {
				db[i][j][k] = db[i][j - 1][k] + db[f[i][j - 1][k]][j - 1][k];
			}
		} 
	}
	scanf("%lld", &x0);
	double ans = 1e15;
	long long ans_h = -1e15;
	int ans_s;
	for (int i = 1; i <= n; i++) {
		long long x = Calc(x0, i).first;
		long long y = Calc(x0, i).second;
		if (y == 0) {
			if (ans == 1e15 && h[i] > ans_h) {
				ans_h = h[i];
				ans_s = i;
			}
			continue;
		}
		if (ans > 1.0 * x / y) {
			ans = 1.0 * x / y;
			ans_h = h[i];
			ans_s = i;
		}
		else if (fabs(ans - 1.0 * x / y) <= 1e-6 && h[i] > ans_h) {
			ans = 1.0 * x / y;
			ans_h = h[i];
			ans_s = i;
		}
	}
	printf("%d\n", ans_s);
	scanf("%d", &m);
	while (m--) {
		long long x;
		int s;
		scanf("%d%lld", &s, &x);
		pair<long long, long long> r = Calc(x, s);
		printf("%lld %lld\n", r.first, r.second);
	}
	return 0;
}