wqs二分 学习笔记

鸣谢 @$\color{black}\texttt{F}\color{red}\texttt{lying2018}$ 没有他笔者自己就不是很会 wqs二分。
感谢 @$\color{black}\texttt{y}\color{red}\texttt{urzhang}$ 和 @$\color{black}\texttt m\color{red}\texttt{yh}$ 指出日报存在的问题。
看洛谷日报从来没写过 wqs二分 的东西？那只能自力更生了啊。
如果有问题欢迎在评论区留言，应该能做到尽快 upd
如果有补充，欢迎在评论区告诉笔者，一起讨论哦
其实 wqs二分 本身并不难，但是能否想到 wqs二分 可能才是问题所在。
评论区好像有一群神仙要求输出方案，那就把这个链接放到更醒目的位置吧，CF125E MST Company 题解连接

wqs二分 是神仙 王钦石 在 2012 年论文中提出的一类二分方式。
基本是用来处理一类带有限制的问题的。
比较明显的标志就是 恰好选 K 个 等。
使用 wqs二分 有一个前题：原问题具有凹凸性。

举个例子，比如我们的函数是上凸的。
那么根据定义，它的斜率肯定单调递减。

$\tiny\text{图片来源于网络}$ 于是，我们可以二分这个斜率，然后快速算出它切这个凸包会切在哪里。

$\tiny\text{图片来源于网络}$ 注意这个切点 $(x,F(x))$ 的意义：它表示当选 $x$ 个时答案时 $F(x)$
根据凹凸性，这个 $x$ 的大小是随着函数的斜率单调递增/递减的。
因为具有单调性，所以肯定可以用二分。
而二分斜率这类二分就被人们称为 wqs二分。

感性理解就是有两类物品，二分差值（可以为负）。
如果差值大，那么其中一类物品会少，另一类会多。
然后根据物品数目来决定差值应该减少还是增大。

笔者刚开始提到的例子，要在一些物品中选择 $K$ 个物品，带有限制

这类题目基本都具有凹凸性。
如果你要选第一个物品，第一次肯定会选当前能选择的最大值。
证明：首先，因为选择之后，限制肯定更严。
如果第二次选择物品价值的比第一次大。
因为第一次限制比第二次小，所以在第一次选择的时候肯定也可以选择第二次的。
与第一次选择了最优价值矛盾。
所以我们证明了 $F(K)-F(K-1)\le F(K+1)-F(K)$。
所以函数 $y=F(K)$ 是凸函数。

当前，我们二分到了一个斜率。
我们考虑一下这个函数的意义。
它的横坐标（$x$）表示的是当前选了几个物体。
假设斜率为 $k$，那么 $y=kx+b$。
那么上面的式子中，$kx$ 就代表对每个目标物体会增加一定量的代价。
那么我们就直接对每个目标物体减去一定代价，再用贪心、dp等方式求出最优选择物体数量。
这里的 dp 不仅需要求出最小值，还需要求出取到最小值时所选物体数量。
然后就好了？

一个二分就好了，详见下面例题。

二分结束后，我们只知道最优的斜率。
我们得带入给定的 $K$ 来计算出最优的 $F(x)$。
比如在这个函数关系中，有 $(x_1,F(x_1)),(K,F(K))$ 两个点，它们的斜率等于最优斜率。
那我们拿直线去切函数时可能切到的不是 $(K,F(K))$ 而是 $(x_1,F(x_1))$。
所以直接输出二分到的位置是错误的，必须找到用二分斜率算出的 $F(K)$。

wqs二分 经常用来优化费用流模型，所以单独拿来讲一下。
下面的证明是基于费用流算法证明的，如果不会，可略过。
我们假设每次增广流量为 1 的流。
首先，我们思考一下每次增广会做什么。
我们会找到一条从 s 到 t 的最短路，然后增广它。
而增广过程中，只会使正向图的一些边容量减少。
所以如果一条路径在第 $k$ 次增广时存在，那它肯定在 $\forall i\in[1,k)$，这条路径肯定存在。
所以假设 $\exists i\le j$ 使第 $i$ 次增广时最短路的长度 $>$ 第 $j$ 次的最短路。
因上所述，第 $i$ 次增广使肯定存在第 $j$ 次时的最短路。
所以第 $i$ 次增广的肯定不是残量网络中的最短路，与假设矛盾。
于是我们说明了 $\forall i\le j$，第 $i$ 次增广的最短路 $\le$ 第 $j$ 增广的最短路。
而每次累加上的流量就是这条最短路的长度乘上流量，就等于最短路。
设我们增广 $x$ 次获得的流量是 $f(x)$。
那么 $f(x+1)-f(x)$ 就代表当前残量网络上的最短路。
而上面又说明了残量网络上最短路不减。
所以费用流增广的次数和增广总流量形成的关系肯定是下凸函数。
所以如果多次增广的费用流问题，我们可以用 wqs二分 来优化。

补上了几道 wqs二分 题目的证明。

例题，顺便补充证明 wqs二分 凸性质。
题意简叙：求最小的生成树使点 s 度为 $K$。
题意分析：
第一类物品是 s 的度，第二类物品是其他未和 s 连边的边。
随着和 s 度增加，我们需要在第一类物品中找到一条最短的边和 s 相连。
根据树的环路性质，我们需要把新加入边的两端点形成的路径中最长边断掉。
每次增加/减少的贡献就是第二类物品中的最大值减去第一类物品中的最小值。
因为每次会删去最小值/最大值，所以最小值单调递增，最大值单调递减。
所以每次增加/减少的贡献单调递减。
也就是说原函数的斜率单调递减，我们就证明了此题具有凸性质。
解题方式：
凸性质得到了，那么直接上 wqs二分。
每次判定对于和 s 相连的边跑一遍最小生成树。
由上文，我们每次直接对和 s 有关的边权值加上当前二分的 mid。
然后在按照权值排序之后的边序列上选边，做 Kruskal。
判断有几条边和 s 相连，直接根据这个数量继续二分就好了。
小 tips：每次二分需要求一个 Kruskal，但是我们并不需要对于每次二分重新排序边。
我们只需要刚开始排序一遍，对于每次二分直接归并一下就好了。
于是，成功把复杂度从 $O(n\log n\log V)$ 降至 $O(n(\log n+\log V))$
代码
加强版：CF125E MST Company，题解连接

这是 wqs二分 发明者在论文中举出的例题。
题意简述：一张分白边和黑边的图，求满足白边数量为 $K$ 生成树中最小的。
题意分析：
同样分黑白考虑。
如果两点之间没有黑边，我们假设连了一条权值为 $+\infty$ 的黑边。
然后找出黑边形成的最小生成树。
每次加入一条最小的白边，删除一条可以删的最大的黑边，所以也具有凸性质。
而根据 环路性质 以及 Kruskal 算法的证明，这样得到的生成树肯定是最优的。
所以此题具有凸性质。
解题方式：
和上题类似，二分权值，白边所有边权加上权值。
然后做 MST，求白边选了多少条，然后继续二分。
代码

二维 wqs 二分，虽然可以费用流。（官方题解还是类似模拟费用流？
首先，这题可以费用流（具体见题解区），而它也刚好是选 $K$ 个的题目。
而费用流的凸性质在上文证明过了，在此不证。
不过，需要注意的是，是费用流模型具有凸性质，而不是费用流的每个部分都具有凸性质。
在此题中表现为是 $a$ 和 $b$ 两维综合起来后具有凸性质。
而不是 $a$ 和 $b$ 两维同时具有凸性质。
因为费用流模型具有凸性质，所以我们可以推出 $a$ 维具有凸性质。
那么我们在二分的时候需要 wqs二分 $a$ 维，然后暴力 dp $b$ 维。
这样才能证明正确性。
不过两维都 wqs二分 好像也能正确，也能 AC 此题。
代码不贴了，因为笔者写这题时 Too Naive，写的 wqs二分 套 wqs二分。

无 wqs二分 正确性证明，请读者自证。

这题不是愚人节啊。。。
首先，这题是取 K 个东西的问题，可以 wqs二分。
我们假设每次打印为物体。
对于当前一个物体，我们有三种选择。

我们可以用优先队列来维护这个过程。
代码（有注释

首先，分子分母同时除以 $\overline{x}$，然后式子就变成了 $\left(\sum_{i=1}^nx_i\right)+1$。
显然可以前缀和，得到 $S_i-S_{j-1}+1$。
此时我们可以斜率优化，而仅斜率优化也无法完成这个问题。
毕竟状态至少要两位，复杂度直接变成 $O(n\times m)$
这时候，我们就可以使用 wqs二分 的降维打击优化状态数功能。
也就是我们对于所选每段值强行加上一个权值，然后把选择数量去掉。
在我们 dp 时，我们还需要记录最优决策选择的区间数量，方便我们二分。
直接斜率优化一下这个东西就好了qwq，毕竟这是 wqs二分 笔记，斜率优化就不展开了。
代码（有注释
附不斜率优化的代码

首先，题目可以转化为在一棵树上取 $K+1$ 条互不相交链，最大化这些链之和。
希望没有人和笔者一样义为题目意思是选 K 条边并把权置为 0 的吧（
然后，根据 wqs二分 基本套路，我们考虑如果没有这个 $K$ 限制我们应该怎么做。
显然，我们可以记录 $f_{i,0/1/2}$ 表示当前在 $x$ 这个点，第 $x$ 这个点是没有用还是作为链中部还是作为链顶。
显然有 dp 转移方程，这里就不列了，具体看代码 ，毕竟这是 wqs二分 学习笔记嘛（
然后，我们按照 wqs二分 的基本套路，枚举一个差量。
然后这题就做完了？？？？ 抱歉好像还真做完了。。。
代码（有注释

参考资料：
浅析一类二分方法
wqs 二分详解
题解 P4383 【八省联考2018】林克卡特树