题解：P10181 龙逐千灯幻
wanxinlian
·
·
题解
题意为给个染色了的序列问前 x 个位置，划分成 k 段，最大化每一段的颜色数之和。
首先显然有 dp_{i,j} 表示前 i 个位置划分成 j 段的最大权值和。对此有转移：dp_{i,j}=\max\limits_{k=1}^{i}dp_{k-1,j-1}+w(k,i)
观察一下可发现其满足四边形不等式 w(i,j)+w(i+1,j+1)\geq w(i+1,j)+w(i,j+1)。所以可以套用决策单调性。不难发现这个问题还有凸性，随着划分数增多，每次的收获越来越少，最后到零，套用wqs二分，问题被优化到 O(n\log^2{n}+m)。
观察一下，这个问题也可以放到数据结构上做，当做到第 $j$ 轮第 $i$ 个元素，第 $k$ 个点维护 $dp_{k-1,j-1}+f(k,i)$，每次取一个后缀加一，全局取最大值即可。发现这个问题可以用并查集做，用并查集维护一个单调栈，如果不满足单调性就通过merge删元素，后缀加可以通过维护差值，find加的位置来做。只需维护栈顶和栈底元素的值，合并最多 $n$ 次，所以单次 $dp$ 复杂度 $O(n\alpha(n))$，总复杂度 $O(n\sqrt{n}+m)$。
可以再用严格线性并查集去掉 $\alpha(n)$，按 $w$ 分块，用一个数维护块内第 $i$ 个数是否向左合并，查询时从后往前找第一个未被合并的点，用链表合并之后均摊是 $O(1)