思路

注意到第二个条件和第三个条件本质相似，可以用相同的维护方式处理，因此这个只讨论第二个条件的维护方式。

定义 \(dp_i\) 表示走到 \(i\) 的最少步数。第一个条件的转移显然为 \(dp_i \leftarrow dp_{i - 1}\)。

对于第二个条件，\(i\) 能向 \(j\) 转移，当且仅当 \(h_{i + 1 \sim j - 1}\) 都比 \(h_i,h_j\) 高。不妨将 \(i,j\) 的限制分开，对于 \(j\) 而言，一个合法的 \(i\) 必须满足 \(\max_{p = i + 1}^{j - 1}\{h_p\} < h_j\)。不难发现合法的 \(i\) 一定是对于 \(j\) 的一个后缀，可以二分 + ST 表 \(\Theta(\log n)\) 求出这个后缀。

对于 \(i\) 同样得满足这个条件，用一个 set 维护所有可能合法的位置。每一次插入一个 \(j\)，需要将所有 \(\geq h_j\) 的位置全部删掉，因为对于 \(j + 1\) 合法的 \(i\) 必须满足 \(h_i < h_j\)。

现在问题变成查询一个后缀中在 set 中的元素的 \(dp\) 值的 \(\min\)。可以在线段树上维护，将所有不在 set 中的位置赋为 inf 即可。因为每一个时间复杂度 \(\Theta(n \log n)\)。