题解

思路

对每座城市 $i$，记东方城市中最近者为 $B_i$，第二近者为 $A_i$。一旦这两个后继确定，从任意起点出发的路线就是确定的。

距离的比较关键字为

第二项体现“距离相同则海拔较低者更近”。

做法

子任务 1：逐步扫描

每到一座城市，都扫描全部东方城市并排序，现场选出最近或第二近城市。对所有起点和询问直接模拟即可。

子任务 2：平方预处理

对每个 $i$ 枚举所有 $j>i$，预处理 $A_i,B_i$，耗时 $O(n^2)$。之后每组旅行至多经过 $n$ 座城市，直接模拟；寻找第一问最优起点也逐个模拟。

总时间 $O(n^2+mn)$，在 $n\le1000,m\le10000$ 时可行。

满分算法：有序结构与倍增

从东向西处理城市。用离散化海拔上的 Fenwick 树保存所有已经处理的东方城市。通过顺序统计找出当前海拔左侧两个、右侧两个已出现排名；最近和第二近城市一定在这至多四个候选中。按上述关键字排序即可得到 $B_i,A_i$。独立 Oracle 使用按海拔排序的平衡树完成同一候选提取。

把连续的“A 开一次、B 开一次”视为一段。定义：

• jump[k][i]：从 $i$ 出发完成 $2^k$ 段后到达的城市；
• distA[k][i]、distB[k][i]：这 $2^k$ 段内 A、B 的里程。

第 $0$ 层由 $i\to A_i\to B_{A_i}$ 得到，高层由两个低一层区间拼接。

回答一次旅行时，从大到小枚举 $k$，只要整块存在且加入后总里程不超过 $x$ 就跳转。所有完整两步段结束后，再尝试走最后一个 A 的单步；这覆盖“B 无路可走”或剩余预算只够 A 的情况。

第一问对每个起点执行一次同样的查询。比较 $a/b$ 时不用浮点数：当两个分母均非零时比较 $a_1b_2$ 与 $a_2b_1$；分母为零按无穷大处理。比值相等时选择海拔更高者。

复杂度

• 子任务 1：最坏时间 $O((n+m)n^2)$，空间 $O(n)$；
• 子任务 2：时间 $O(n^2+mn)$，空间 $O(n)$；
• 满分算法：时间 $O((n+m)\log n)$，空间 $O(n\log n)$。

易错点

1. 距离相同时，海拔较低者排序在前，而不是城市编号较小者。
2. 倍增块包含 A、B 各一次；完成若干整块后还要尝试最后一次 A 驾驶。
3. 预算恰好用完是允许的，条件应为“总路程不超过 $x$”。
4. 比值相同按起点海拔选择，不按城市编号选择。
5. 两段距离的乘积可能接近 $10^{18}$，必须使用 64 位整数。