P4093 [HEOI2016/TJOI2016] 序列 & CDQ 分治

· · 个人记录

本题的转移方程显然

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