牛客练习赛85 C

题目要求对一个区间分成最少段，使得每段的最大值都是开头的数。

一看到没有修改就想分块暴力预处理乱搞，后来发现没有这么复杂。

首先我们肯定从 开始找到下一个离它最近的一个比它大的数，然后这中间分成一个段后再以这个数为新的 开始往后面分是最优的，比较简单的贪心就不细证明了。

接着我们考虑每个数往后面挪动到的数是固定的，把它看成一个连边的话那么就是弹飞绵羊了，接着剩下的东西可以分块可以 LCT 可以森林上倍增，这里就讲一下分块的做法吧。

对于每个数预处理出来它的连边，这个预处理可以 做，时限比较宽，比赛时比较急躁就用一个线段树维护区间 然后二分找位置就好了，值得注意的是对于没有连边的数要连一条边到 去不然需要打特判，不是很方便。

接着我们分块，对于每个数维护一下它跳出这个块时跳到了哪里以及跳出这个块要用几步就好了。

查询时如果没跳到 那个块就直接暴力把整块跳出去就好了，跳到那个块了后就直接暴力跳。

时间复杂度 比较屑，正解就是把这个跳跃换成了倍增跳，就像今年省选 Day2T1 正解是 倍增，但是大家第一反应就这个玩意儿好像不是很好维护于是根号分治树分块就来了，事实上没有这么复杂。