luogu P7599 [APIO2021] 雨林跳跃

题面传送门

我成功了，我不再是以前那个我了！

我们发现部分分里面有个单点跳到单点，尝试考虑这个部分分。

一个点有两个点可以跳，贪心地想，如果我先跳了比较矮的那个，那么再一步能跳到的点比较高的都能跳到。因此应该是先跳高的更优。

但是事情没有这么简单，你会发现有的时候，如果跳了一步高的，会导致高于目标点，就走不到了。

因此我们有一个贪心策略：先跳比较高的点，直到下一步比目标点高了，再一直往右跳，直到跳过头或者跳到。

然后再来考虑怎么从一个点跳到一个区间内。显然这个点和这个区间之间的最大值是要高过的。因此我们尽量往高跳先跳到一个位置，这个位置有两种跳法，但是这一步跳完之后一定是一直往右跳。因此可以对两种跳法的答案都算一遍。

那么怎么从一个区间跳到一个区间呢？考虑找到这个最优的点，转化成点跳区间的问题。显然一个点如果右边有高于终点区间最大值的点那么这个点不能作为起点，那么找最大的点开始跳一定最优。维护倍增即可。时间复杂度 (O(nlog n))。

submission