wqs二分 学习笔记

1. 前言

鸣谢 @\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 题解连接

2. 介绍

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

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

\tiny\text{图片来源于网络}

于是，我们可以二分这个斜率，然后快速算出它切这个凸包会切在哪里。

\tiny\text{图片来源于网络}

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

3. 感性理解

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

4. 具体实现

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

Part1. 凹凸性

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

Part2. 求被切点

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

Part3. 主体

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

Part4. 注意点

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

5. 应用

1. 可以用来优化一些特殊的费用流模型（下文
2. 降维打击有一些 dp 需要记录当前选了几个数，如果用 wqs二分 可以把数量维压缩

6. 和费用流的关系

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二分 来优化。

7. 例题

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

P5633最小度限制生成树

例题，顺便补充证明 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，题解连接

P2619【国家集训队2】Tree I

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

CF739E Gosha is hunting

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

8. 习题

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

CF802O April Fools' Problem (hard)

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

1. 跳过它，不使用它
2. 把它当作一个准备日
3. 把它和之前最小的 a 匹配，并打印

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

P4983 忘情

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

P4383 【八省联考2018】林克卡特树

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

8. 附录

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