【题解】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\operatorname{rng}(i+1,j)]}dp_j\] 因为这个转移的条件比较复杂，合法的 $j$ 都是不连续的，考虑用 cdq 分治来做。 cdq 假设我们目前已经知道 $dp_{[l, mid]}$，考虑这些 dp 值对 $dp_{[mid+1, r]}$ 的贡献。 $dp_i(i\le mid)$ 可以更新 $dp_j(j>mid)$ 当且仅当： $j-i\in\operatorname{rng}(i,...

Submit