才知道 NOIP2018 考了一道原题……
# 题面
点击展开/折叠题面
给定数组 $a_i$ 以及一个最初全 0 的数组 $b_i$。可以进行操作——指定 $L,R$，给数组 $b_i$ 区间 $[L,R]$ 加 1。要使 $b_i$ 与 $a_i$ 完全相同，求最小需要操作多少次。
# 解析
（第一想法）这不是笛卡尔树吗？线段树/st表维护一下最小值然后把笛卡尔树建出来，再计算每个节点和父亲节点的深度差之和不久好了？
（第二想法）第一道题数据结构这就离谱 →_→
我们为什么要用笛卡尔树？因为有一个废话一样的贪心性质：每次肯定使 $[L,R]$ 尽可能长（尽可能往两边扩展）。
比如下面这样，把数组具象化为直方图：
同一个颜色意味着一次操作，然后考虑在 x 的位置计算代价，然后发现就是 $\sum \max\{0,a_i-a_{i-1}\}$
这样看起来就像 T1 了。（还需要放代码吗）
> Tab. 还有别的理解方法，反正我觉得这样理解最简单
THE END
Thanks for reading!
> Linked sonder-网易云