题解

思路

令 $f_i$ 表示以第 $i$ 根柱子结尾的最长合法序列长度，$pre_i$ 记录该最优状态的前驱下标。若前一根所选柱子为 $j$，则必须有 $j<i$，并且满足

$$h_j\le h_i-d\quad\text{或}\quad h_j\ge h_i+d.$$

因此

$$f_i=1+\max\left(\max_{j<i,\ h_j\le h_i-d} f_j,\ \max_{j<i,\ h_j\ge h_i+d} f_j\right).$$

转移只需要按高度查询两个区间中的最大二元组 $(f_j,j)$。高度上界达到 $10^{15}$，先将所有 $h_i$ 排序去重，再用线段树维护每个离散高度上已经出现的最佳状态。

做法

1. 将所有高度排序去重，得到离散坐标数组。
2. 从左到右扫描柱子。在线段树上分别查询不大于 $h_i-d$ 的前缀，以及不小于 $h_i+d$ 的后缀。
3. 取两个查询结果中长度较大的下标作为 $pre_i$，令其长度加一得到 $f_i$。
4. 用 $(f_i,i)$ 更新高度 $h_i$ 对应的位置。由于扫描顺序从左到右，树中只含下标小于 $i$ 的状态。
5. 从全局最大状态沿 $pre$ 倒推，再反转得到一条最长序列。

子任务 1 中 $d=0$，所有下标依次选取即为最优。子任务 2 的高度非降，反复选择当前已选柱子之后第一个高度至少增加 $d$ 的柱子是最优贪心。子任务 3 可直接枚举所有 $j<i$ 做二次动态规划。

证明

先证明动态规划转移正确。任取一条以 $i$ 结尾、长度大于一的合法序列，设其倒数第二个下标为 $j$。由合法性，$j<i$ 且 $|h_j-h_i|\ge d$，所以 $h_j\le h_i-d$ 或 $h_j\ge h_i+d$。删去末尾的 $i$ 后，剩余部分长度不超过 $f_j$，故该序列长度不超过转移式右侧。

反过来，转移查询得到的任一状态都来自某个 $j<i$，并且其高度位于上述两个合法区间之一。把 $i$ 接在一条达到 $f_j$ 的序列之后，所得序列下标递增且最后一次跳跃合法，因此转移式给出的长度一定可以达到。两边结合，$f_i$ 恰为以 $i$ 结尾的最优长度。

线段树在处理 $i$ 前只保存 $1,2,\ldots,i-1$ 的状态，并对每个高度位置保留最大的 $(f_j,j)$，所以两次区间查询恰好返回转移式所需的最大值。由归纳法，所有 $f_i$ 与 $pre_i$ 均正确。最后取最大的 $f_i$ 并沿前驱恢复，得到的就是一条全局最长合法序列。

对于高度非降子任务，贪心每次选取最早能到达的下一根柱子。若某个最优解在同一步选择了更晚的柱子，将它替换为贪心选择不会增大高度，也不会晚于原下标；后续原本可达的每根柱子仍然可达。逐步交换即可得到同长度的贪心解，故贪心最优。

复杂度

• 时间复杂度：$O(n\log n)$。
• 空间复杂度：$O(n)$。