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 题解连接](https://www.luogu.com.cn/blog/daniu/solution-cf125e) ## 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最小度限制生成树](https://www.luogu.com.cn/problem/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))$ [代码](https://paste.ubuntu.com/p/rmkqqHfCth/) 加强版：[CF125E MST Company](https://www.luogu.com.cn/problem/CF125E)，[题解连接](https://www.luogu.com.cn/blog/daniu/solution-cf125e) ### [P2619【国家集训队2】Tree I](https://www.luogu.com.cn/problem/P2619) 这是 wqs二分 发明者在论文中举出的例题。 **题意简述**：一张分白边和黑边的图，求满足白边数量为 $K$ 生成树中最小的。 **题意分析**： 同样分黑白考虑。 如果两点之间没有黑边，我们假设连了一条权值为 $+\infty$ 的黑边。 然后找出黑边形成的最小生成树。 每次加入一条最小的白边，删除一条可以删的最大的黑边，所以也具有凸性质。 而根据 环路性质 以及 `Kruskal` 算法的证明，这样得到的生成树肯定是最优的。 所以此题具有凸性质。 **解题方式**： 和上题类似，二分权值，白边所有边权加上权值。 然后做 MST，求白边选了多少条，然后继续二分。 [代码](https://paste.ubuntu.com/p/6yfgn7MdKq/) ### [CF739E Gosha is hunting](https://www.luogu.com.cn/problem/CF739E) 二维 wqs 二分，~~虽然可以费用流。~~（官方题解还是类似模拟费用流？ 首先，这题可以费用流（具体见题解区），而它也刚好是选 $K$ 个的题目。 而费用流的凸性质在上文证明过了，在此不证。 不过，需要注意的是，是费用流模型具有凸性质，而不是费用流的每个部分都具有凸性质。 在此题中表现为是 $a$ 和 $b$ 两维综合起来后具有凸性质。 而不是 $a$ 和 $b$ 两维同时具有凸性质。 因为费用流模型具有凸性质，所以我们可以推出 $a$ 维具有凸性质。 那么我们在二分的时候需要 wqs二分 $a$ 维，然后暴力 dp $b$ 维。 这样才能证明正确性。 ~~不过两维都 wqs二分 好像也能正确，也能 AC 此题。~~ 代码不贴了，因为笔者写这题时 Too Naive，写的 wqs二分 套 wqs二分。 ## 8. 习题 无 wqs二分 正确性证明，请读者自证。 ### [CF802O April Fools' Problem (hard)](https://www.luogu.com.cn/problem/CF802O) ~~这题不是愚人节啊。。。~~ 首先，这题是取 K 个东西的问题，可以 wqs二分。 我们假设每次打印为物体。 对于当前一个物体，我们有三种选择。 1. 跳过它，不使用它 2. 把它当作一个准备日 3. 把它和之前最小的 a 匹配，并打印 我们可以用优先队列来维护这个过程。 [代码（有注释](https://paste.ubuntu.com/p/YfwcyWN2Gy/) ### [P4983 忘情](https://www.luogu.com.cn/problem/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二分 笔记，斜率优化就不展开了。 [代码（有注释](https://paste.ubuntu.com/p/kRGR24JJgh/) [附不斜率优化的代码](https://paste.ubuntu.com/p/cQrBBygqRW/) ### [P4383 【八省联考2018】林克卡特树](https://www.luogu.com.cn/problem/P4383) 首先，题目可以转化为在一棵树上取 $K+1$ 条互不相交链，最大化这些链之和。 ~~希望没有人和笔者一样义为题目意思是选 K 条边并把权置为 0 的吧（~~ 然后，根据 wqs二分 基本套路，我们考虑如果没有这个 $K$ 限制我们应该怎么做。 显然，我们可以记录 $f_{i,0/1/2}$ 表示当前在 $x$ 这个点，第 $x$ 这个点是没有用还是作为链中部还是作为链顶。 显然有 dp 转移方程，这里就不列了，具体看代码 ~~，毕竟这是 wqs二分 学习笔记嘛（~~ 然后，我们按照 wqs二分 的基本套路，枚举一个差量。 ~~然后这题就做完了？？？？~~ 抱歉好像还真做完了。。。 [代码（有注释](https://paste.ubuntu.com/p/rFRyKD93t2/) ## 8. 附录 参考资料： [浅析一类二分方法](http://www.doc88.com/p-949564862405.html) [wqs 二分详解](https://blog.csdn.net/a_forever_dream/article/details/105581221) [题解 P4383 【八省联考2018】林克卡特树](https://www.luogu.com.cn/blog/Marser/solution-p4383)