本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-10 17:50:00

本题的转移方程显然

$$f(i) = \max\limits_{0 \le j \lt i} f(j) + 1, \space \text{s.t.} \space \max a_j \le \min a_i$$

如果没有后面的限制，这玩意儿就根本不是个动态规划，因为我们可以证明此时 $f(i) = f(i-1) + 1$。但是有了后面的限制之后，问题棘手了一些，因为转移变成了 $O(n)$ 的，难以接受。

我们可以考虑 CDQ 分治：先对左区间进行处理，然后考虑对右边的影响。只考虑影响的时候，由于本题显然有单调性，我们可以将左右区间排序，左区间依据 $\max a_i$，右区间依照 $a_i$。

这样，我们用双指针（CDQ 分治标配）扫描一边，利用单调性，可以做到 $O(n\lg n)$（$\lg n$ 来自树状树组）。加上排序 $o(n\lg n)$，整体复杂度是 $O(n \lg^2 n)$，不错。

总体上看，CDQ 分治首先利用分治的思想，让我们只需要考虑左区间对右边的影响（因为左边与右边单独的两个区间，是另外的两个问题）。这个时候，我们就可以利用问题的单调性，加上双指针与一些数据结构（常见树状树组）就能解决问题。