WQS 二分

一个参考

WQS 二分用来处理一些答案构成凸函数的问题。

最经典、最常见的形式，就是 "从若干个物品中恰好选给定个数的最优" 型问题。

适用要求：如果不考虑选的物品的个数限制，可以很快求出答案。

例题：P2619 Tree I

从所有白边中选 \(need\) 条，然后加上若干条黑边形成生成树，最优是多少。

为什么这是一个凸函数？记选 \(x\) 条白边的最优为 \(f(x)\)，则 \(f(x)\) 会逐步趋向于最大值，再逐渐减小。

有没有可能最优是在 \(w\) 条白边时取到，但 \(i_1<i_2<w\) 时，反而 \(f(i_1)>f(i_2)\)？

考虑最优解，是由若干条白边连接若干个只有黑边的连通块。这是最优解说明任意两个用白边相连的连通块之间不存在边权更小的黑边。也就是只要换成黑边，代价不会下降。

\(i_1\) 的最优方案，可以看作是从 \(w\) 的最优解里面选取 \(w-i_1\) 条白边改成黑边。有没有可能是把 \(w\) 的某条黑边改成白边，某条白边改成黑边，反而比只把白边改成黑边严格更优？不可能，否则在 \(w\) 的最优解里面应用这个替换，与最优解矛盾。

所以 \(i_1\) 是选 \(w-i_1\) 条白边改成黑边，\(i_2\) 是选 \(w-i_2\) 条白边改成黑边。上面说了任何白边改成黑边，代价都单调不降。因为 \(w-i_1>w-i_2\)，所以 \(i_1\) 改后会更加单调不降。因此不可能。

同理可以证明 \(w<i_1<i_2\) 时，\(f(i_1)>f(i_2)\)。因此得到 \(f\) 是一个凸函数。（而且是上凸函数，因为选一条边后总代价不可能减少）

证明是凸函数，然后怎么做？

上凸函数有一个性质：考虑一条斜率为 \(k\) 的直线与 \(f\) 的切点横坐标 \(X\)，满足 \(f\) 随着 \(k\) 的减小而增大。（在图上画一下就能看出来）

如果我们能求出切点横坐标 \(X\)，将其与 \(need\) 比较，就可以得到我们二分的 \(k\) 是多少。我们的目标是找到一个 \(k\) 使它与 \(f\) 的切点横坐标为 \(need\)（为什么后面会说）。

那么如何求出切点横坐标 \(X\)？已知信息只有一个 \(k\)。而且注意我们必须快速求出 \(X\)，如果是平方级别的，算法根本没有优化反而还慢了。

性质：令 \(g(x)=f(x)-k\times x\)，则 \(g(X)\) 为 \(g\) 的最大值。

很好理解，因为 \(g\) 相当于求一条斜率为 \(k\) 的直线过一个点的截距。而上凸函数切点处的截距一定是最大的。

结论：\(g(X)\) 为所有物品价值减去 \(k\) 后，不限制物品个数的最大价值。

为什么？发现此时的 \(f(i)\) 会变成 \(f(i)-k\times i\)，而不限制物品个数就是求 \(\max(f(i)-k\times i)=\max(g(i))\)，根据上面的性质 \(g(X)\) 就是最大值。

因为我们可以快速求出不限制物品个数的最大值，所以自然也可以快速求出 \(g(X)\)。在求 \(g(X)\) 的时候顺便统计一下，可以得到 \(X\)（上面的理论保证了在最优情况下的统计结果一定是 \(X\)）。

怎么求 \(X\) 结束了。于是我们可以通过二分找到一个斜率 \(K\)，使每个物品价值减去 \(K\) 后不限制个数的最优解恰好是选择 \(need\) 个物品。

使每个物品价值减去 \(K\)，然后跑一次不限制物品个数的算法得到答案为 \(ans\)，最终答案为 \(ans+K\times need\)。（这里要特别注意记得把减去的加回来）

这道题还预留有一个问题：有可能我们根本二分不到 \(need\)！

这是一个例子，当切点有很多个且 \(need\) 在中间，怎么找到 \(need\) ？

答案是我们不需要找到 \(need\)，因为都被同一个斜率切的顶点，对应的截距都是相同的。只要找到的截距是被这个斜率切的，加上 \(k\times need\) 后一定会得到 \(need\) 的最优。