本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-24 19:33:07

有的题，横坐标和所切的斜率均不单调，比如 P4655 Building Bridges，这时候我们可以用 CDQ 分治来把朴素的 $O(n^2)$ 优化到 $O(n\log n)$。

具体方法比较简单。CDQ 分治所考虑的核心就是左区间对右区间的贡献。怎么转化成为朴素的斜率优化 DP 呢？左边区间的横坐标要单调，右边区间所切的斜率要单调。

这样，我们就先按照切的斜率排序，然后计算左边对右边的贡献，然后按照横坐标排序。