Luogu7599 [APIO2021] 雨林跳跃

题意：给出一个长度为 的排列 。

当玩家在位置 ，当且仅当满足下列两个条件之一，能一步移动到 。

• 是 左侧第一个大于 的。

• 是 右侧第一个大于 的。

记 表示从 出发到达 所需的最小步数。若不能办到，则定义为 。

每次询问给出 ，求 。

，，，时限 。

---

先用单调栈求出每个位置的两条出边。

• 求单个

途中的权值必然单调增加，若到达 则不再能到达 。

若 则 必不能到达 ，反之则必然存在到达 的方案，证明略。

每一步只有两种决策，若目的地 则排除。

若两种决策都可选，则贪心地选择更大的一个。

• 证明：对于 左右两侧的目的地 ，它们的后继都不可能经过区间 ，于是可以缩成一个点考虑。

  命题等价于，在同一个位置 ，将 在不超过 的前提下尽量增大，是否更优。答案是肯定的。

观察我们的决策，先会不断选择两侧更大的一个，然后会不断向右跳。

用倍增加速求解即可。

• 时

若 中的某个 走起一步却仍然在 内，必不优。

于是也可以将 缩成一个点考虑。取有解（满足 ）的最大的起点即可。

可以 ST 表加二分求解出最长合法后缀，再取出其中的最大值。

• 时

有解的条件是 。

仍然用上一部分的方法确定 。

讨论结束的最后一步 。

若 ，则必然是 。

若 ，则答案为 ，判据为 。

若 ，则必然是 有解的最大值，同样二分求出。

复杂度 。