题解：P13691 [CEOI 2025] highest

wzj33300 · 2025-09-08 09:08:07 · 题解

一道倍增好题。

我们把一个答案序列定义成把每一步的代价（1 或 2）拼起来的序列。

考虑把倍增的过程刻画成：判断答案能否超过下一个 2^n 的倍数。由于 n 是从大到小枚举的，所以我们其实只需要判断答案能否超过一个数就可以了。

设我们当前答案是 x，正在判断能不能跨过下一个 2^y 的倍数（x+2^y）。由于我们可能从 x+2^y-1\to x+2^y+1，所以我们只能知道新的答案一定有一个前缀代价和是 x+2^y 或 x+2^y+1，注意也有可能 x+2^y\to x+2^y+1，但是这里我们不要求答案不重复，所以没关系。

于是我们只需要维护每个点往后面跳的代价为 2^n,2^n-1 时最远能跳到哪个点，很明显的倍增。

倍增的转移：

这里的转移也会有重复的，但我们一样不关心。

注意我们需要知道 [l,r] 的点跳 x 步最远能跳到哪。设最优方案是从点 p 开始跳，那么我们可以证明 p 为 [l,r] 中 v 最大的点或者 w 最大的点，这里的 v 和 w 是用 1 或者 2 的代价最远能跳到哪，证明不难。

时间复杂度 O((n+q)\log n)。

代码。