题解：P13691 [CEOI 2025] highest

一道倍增好题。

我们把一个答案序列定义成把每一步的代价（$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)$。

代码。