wqs二分

直奔主题

直接举例子吧，考虑这样一个问题：给定一个长为 \(n\) 的数列，要选恰好 \(k\) 个不交的子段使得选择的子段总和最大。

朴素 DP

朴素 DP 是设 \(f_{i,j,0/1}\) 表示考虑前 \(i\) 个选择 \(j\) 段最后一个有没有选的最大收益，时间复杂度 \(O(n^2)\) ，必须有一维 \(j\) 处理“恰好”这个限制。

有没有更优秀的复杂度呢？

带权二分

设 \(F(x) = \max \{ f_{n,x,0}, f_{n,x,1} \}\) ，也就是选择恰好 \(x\) 个不交子段的最大收益。注意到虽然不能直接求出 \(F(k)\) ，但是求出 \(\max\{F(x)|1 \le x \le n\}\) ，也就是函数的最值（以及函数取最值的位置）是不难的（可以直接去掉上述 DP 的第二维）。如果取最值的位置恰为 \(k\) 就能得到答案。

可惜最值并不一定取在 \(x = k\) ，但是可以考虑做一个调整，如果魔改问题，钦定每选一个子段就可以得到 \(p\) 的额外收益，那么此时恰好选 \(x\) 个子段的最大收益就是 \(F(x) + px\) ，如果 \(p\) 选取合适，就能让 \(G(x) = F(x) + px\) 的最值恰好取在 \(x = k\) ，此时 \(F(k) = G(k) - pk\) 就是答案。

如何选择这样一个 \(p\) 呢？把这个问题抽象到二维平面，可以发现 \((x, F(x))\) 构成了一个凸包，而 \(F(x) + px\) 的意义就是斜率为 \(-p\) 的直线在该点上的截距。这样以来不难发现这个 \(p\) 是可二分的，这个二分过程就是 wqs 二分。

懒得画图，不配图了。

扩展

wqs 二分也可以嵌套，比如 CF739E 一题中，有两个不同的数列，要分别选取 \(a, b\) 个元素并最大化收益，其中如果有一个位置在两个数列中同时被选会有一定的代价。

朴素 DP 是设 \(f_{i,j,k}\) 表示考虑前 \(i\) 个位置在两个部分分别选 \(j, k\) 个元素的最大收益，复杂度 \(O(n^3)\) 。

设 \(F(j,k) = f_{n,j,k}\) ，抽象到三维空间上就是点 \((j, k, F(j, k))\) 构成的三维凸包！于是可以拿一个平面去截这个三维凸包。也就是确定两个附加代价 \(p, q\) ，使得 \(G(j,k) = F(j,k) - jp - kq\) ，那就可以求出也就是平面 \(z = px + qy + K\) 截出来的截距 \(K\) 。二分套二分即可求解，复杂度 \(O(n log^2 n)\) 。

三维空间可能有点抽象，也不一定要从这个角度理解，从二分套二分（也就是先来个 wqs 二分，然后对于新的问题继续 wqs 二分）的角度可能更容易理解，也更接近实现。