【题解】P5979 [PA2014]Druzyny
考场上想出,挺有成就感
说一个 $O(n\log^2 n)$ 的 cdq 分治做法,常数不大,不用分类讨论,较为好写。
一些符号
记 $\operatorname{mxl}(l,r)$ 表示下标在 $l$ 到 $r$ 之间的所有区间的左端点最大值,$\operatorname{mnr}(l,r)$ 意义类似。
记 $\operatorname{rng}(l,r)=[\operatorname{mxl}(l,r),\operatorname{mnr}(l,r)]$。
暴戾
首先是一个简单的 $O(n^2)$ dp:
\[dp_i=1+\max_{[j<i]\land [(i-j)\in...