题解：P15130 [ROIR 2026] 超级跳跃

· · 题解

这是 AI 翻译的官方题解

首先把题意更正式地表述一下：对每个锯齿区间，需要确定一个“严格向上凸”的路线：它从区间起点走到区间终点，只使用该区间内的点作为折点，并且区间内所有点都位于这条路线的下方。可以看出，这样的路线总是存在且唯一。

子任务 1：n, q \le 300

在这里，对每个询问区间都可以直接“老老实实”地恢复跳跃序列：每一步都选择一个合适的下一跳。注意，所谓“合适”的跳跃是指：跳跃角度尽可能大（若角度并列，则选择长度尽可能大的跳跃）。这样得到的解法复杂度为 O(q n^2)。

子任务 2：n, q \le 5000

这里可以发现：每个询问的答案都能用栈在与区间长度线性相关的时间内算出。方法如下：

维护一个栈，用来保存“猜测的”彼佳路线的锯齿点。如果把下一个锯齿点压入栈后，发现彼佳最后一次跳跃的角度不小于倒数第二次跳跃的角度，那么就把栈顶锯齿点弹出，并再次检查。容易验证，这个算法会构造出所需的凸路线。于是得到一个 O(q n) 的解法。

子任务 3：h_i \le 10

令 h 表示锯齿的最大高度。考虑回答询问 [l, r]。

先找出从 l 出发后路线上的第二个点。注意：在所有同高度的点中，最优选择总是“离 l 最近的”或“离 l 最远的”。我们可以对每一种高度，在其所有最优候选点中找出第二个点（对每个点，某个高度在其左右两侧最近的点可以用总计 O(nh) 预处理出来）。同时注意路线上的点数为 O(h)，因此总时间为 O(nh + q h^2)。

为了得到完整解法，还需要下面这个想法：假设我们已经知道彼佳在从锯齿 i 到锯齿 k 的路线所经过的锯齿点集合，也知道从锯齿 k 到锯齿 j 的路线所经过的锯齿点集合。我们希望快速得到从 i 到 j 的路线锯齿点集合。容易看出，所求集合由两部分组成：从 i 到 k 路径的一个前缀，以及从 k 到 j 路径的一个后缀。

我们可以按前缀长度从小到大枚举；对每个前缀，再按后缀长度从小到大枚举，并检查由该前缀与后缀构成的折线是否凸。这样“合并”两个凸包的过程需要 O(n^2)。若进一步注意到这两个枚举都能用二分搜索替代，则可做到 O(\log^2 n)。

子任务 4：区间一端在数组左半，另一端在数组右半

在这个子任务里，每个询问区间本质上需要把它相对数组中点的“左半部分”和“右半部分”按上面的思路合并。但要做到这一点，我们需要能够在这两部分上高效地进行二分搜索。

使用如下构造：从数组中点出发向右扫描，并像子任务 2 一样维护一条路径栈。这样在第 i 步时，栈中保存的是彼佳从中点元素跳到第 i 个元素的路线。定义第 i 个元素的“父亲”为此时栈中紧邻它之前的元素（即从中点到 i 的路径上倒数第二个锯齿点）。于是我们得到一棵树，其中从根到第 i 个元素的路径，恰好与彼佳从中点到它的路径一致。

在这棵树上预处理倍增，并对左半部分也构造同样的树，那么就可以做我们需要的二分搜索。预处理开销为 O(n \log n)，所有询问总复杂度为 O(q \log^2 n)。

子任务 5：n, q \le 5 \cdot 10^4

这一组允许提交完整解法的不高效版本（包括对路径做二分时不够高效的变体，例如不使用树结构的做法）。

子任务 6：完整解法

使用分治（divide and conquer）：从整个数组开始递归。对于完全落在左半或右半的询问，递归处理；对于跨越中点的询问，则像上一子任务那样处理。该解法的复杂度为 O(n \log^2 n + q \log^2 n)。