题解：「JOISC 2023 Day4」Bitaro 之旅

问题分析

Bitaro 从起点出发，每次选择最近的未游览景点（距离相同时选坐标更小的），直到游览完所有景点。要求计算从多个起点出发的总路线长度。

核心难点：

• 直接模拟会超时（$N, Q$ 达 $2 \times 10^5$）。
• 需找到贪心选择的规律，用预处理和快速查询优化。

算法思路

1. 贪心选择的规律：
   观察发现，游览顺序本质是从起点开始，逐步向左右扩展区间（类似“左右夹逼”）。例如，若当前已游览区间为 $[l, r]$，下一步会选择 $l-1$ 或 $r+1$ 中更近的点（距离相同时选左）。

2. 预处理关键区间：
   用 ST 表（稀疏表）预处理两个数组：

   • $mn[i][j]$：区间 $[j, j+2^i-1]$ 中，满足“优先向左扩展”的左边界范围。
   • $mx[i][j]$：区间 $[j, j+2^i-1]$ 中，满足“优先向右扩展”的右边界范围。
     用于快速查询区间内的扩展优先级。

3. 快速查询总长度：
   对每个起点 $S_j$：

   • 用二分查找定位其左右最近的景点 $l, r$。
   • 选择更近的起点（$l$ 或 $r$）作为初始游览点。
   • 模拟区间 $[l, r]$ 向左右扩展的过程，用预处理的 ST 表加速扩展决策，计算总长度。

代码解析

1. 二分查找：
   find(x) 和 findl(x) 分别找到大于等于 $x$ 的第一个景点和小于等于 $x$ 的最后一个景点，用于定位起点附近的初始景点。

2. ST 表预处理：

   • lg[i] 存储 $\log_2(i)$ 的整数部分，用于 ST 表的区间划分。
   • mn[0][i] 和 mx[0][i] 是基础区间（长度为 1）的预处理值，分别对应向左、向右扩展的临界范围。
   • 高阶区间值通过合并低阶区间得到，支持 $O(1)$ 区间查询。

3. 查询总长度：
   query(x) 函数模拟从初始点 $x$ 开始，通过左右扩展区间 $[l, r]$ 计算总长度：

   • 每次扩展时，用 ST 表的 RMQ 函数快速判断向左还是向右扩展更优。
   • 累加扩展过程中的距离，直到覆盖所有景点（$l=1$ 且 $r=N$）。

4. 主函数逻辑：
   对每个查询起点 $S_j$，确定初始景点后调用 query 计算总长度，累加起点到初始景点的距离。

复杂度分析

• 预处理：$O(N \log N)$（ST 表构建）。
• 单次查询：$O(\log N)$（二分查找 + 扩展过程中的 ST 表查询）。
• 总复杂度：$O(N \log N + Q \log N)$，满足 $2 \times 10^5$ 规模的需求。

关键结论

通过分析贪心选择的“左右扩展”规律，结合 ST 表预处理区间决策信息，可高效计算每个起点的总路线长度，避免暴力模拟的超时问题。