Wqs old
之前刚学二分的时候做过一道叫 Tree I 的题目，感觉很有意思，不过当时也没怎么深究。
昨天在 uoj 群回答问题的时候得到了清芷姐姐的教导，知道了这玩意儿就是 wqs 二分，因为之前就对这个精妙的套路很感兴趣了，于是决定学习一下。
泛化ψ(｀∇´)ψ
假定你有一个限制参数 \(k\)，你要求 \(ans(k)\)，但是 \(ans(k)\) 求起来是 hard 的。
但是可以快速的对于每一个 \(x\) 求出 \(\max/\min\{ans(i)-ix\}\)，且 \(ans\) 是凸的，那么二分这个 \(x\) 就可以了，因为如果 \(ans\) 是凸的，能取到的最优的 \(i\) 就是关于 \(x\) 单调的，这个就可以二分了。
这是 _rqy 姐姐说的，好像对我这种笨蛋来说不是很直观。
例题ψ(｀∇´)ψ
给定 \(m\) 条边，\(n\) 个点，每条边可能是可爱边或者不可爱边。
求恰好有 \(Need\) 条可爱边的最小生成树。
这个直接写一个 \(dp\) 来做是可以的，但是复杂度上天。
于是我们考虑一个类似之前某道 ds 优化 dp 的题目的思路，设 \(f(i)\) 表示恰好选了 \(i\) 条可爱边的最小生成树的权值和。
然后注意到 \(f\) 是下凸的，所以每一个斜率能够映射到一个切点。
所以我们可以尝试拿一条直线去切 \(f\) 的图像，尝试找到 \(f(Need)\)，但是这不是能一步到位的事情，因为我们只是知道 \(f\) 一定下凸，我们不知道它具体是什么样的。
发现根据下凸函数的性质，当 \(i\) 增加的时候，对应切线的斜率是单调不降的。
也就是说斜率单调，切点也单调，而我们随便给一个 \(k\) 切出来的切点横坐标不一定是 \(Need\)，于是我们想 check，也就想对于一个 \(k\) 求出 \(x\)，顺便求 \(f(x)\)。
所以我们需要建立映射关系。
我们发现固定的斜率对 \(f(x)\) 的切点是固定的（使得截距最大的那个点），那么切线就固定，换句话说截距就固定。
我们就建立了一个从 \(k \to x \to b\) 的映射，也就是说我们可以在固定 \(k\) 的情况下，求出这个切点，并求出截距。
反过来就是说我们可以通过截距求出切点，进一步求出 \(f(x)\)，具体解释如下：
尝试化一下柿子：\(f(x) = kx + b \iff b = f(x) - kx\)。
注意到 \(b\) 最优的时候，我们按柿子求出的这个 \(f(x)\) 一定是最优的（也就是实际的 \(f\) 值）（这个显然，我们是建立了映射关系的）。
所以求出 \(\min\{b\}\) 等价于求出 \(f(x)\)，为什么要做这一步转化呢？
注意到，其实 \(\min\{b\}\) 等价于考虑给每条边都减去一个 \(k\)，求恰好选了 \(x\) 条可爱边的最小生成树。
我们刚才说了，斜率固定，\(\min\{b\}\) 也是固定的，也就是说对于一个 \(k\)，不管他的限制如何，我们求 mst 求出来的权值和也就是固定的！
那么这个选 \(x\) 个的限制就被直接去除，求 \(f(x)\) 就可以转化为没有限制的情况。
所以我们可以二分 \(k\)，对于每个 \(k\) 算一下 \(b \to f(x) \to x\)。
然后 check 一下 \(x\) 和 \(Need\) 的大小关系，调整 \(k\) 就可以二分到 \(Need\) 了！
但是注意到，其实斜率和切点并不一定能建立函数关系，因为一个斜率可以对应多个切点，比如下图的情况，有可能出现一个点两边的斜率相等的情况。
图源 https://www.cnblogs.com/TianMeng-hyl/p/14972355.html。
请读者把它们都当成整点，这里是感性的，本题 \(f(i)\) 显然是 > 0 的。
那么现在要做的就是解决这个一对多的问题，一种常见的解决策略是，我们把这多个点融合成一个点考虑。
具体做法是求 mst 的时候如果有相同 weight，让可爱边更靠前。
现在我们直接对着这种情况莽，当一个斜率对应多个切点的时候，我们求出来的 \(x\) 应该是所有满足条件的 \(x\) 里面最大的一个，因为排序的时候已经贪心地让可爱边选的尽可能多。
于是同一条线上的所有点的影响都被考虑到这条线上最靠后的一个切点上了！
也就是说，我们可以只考虑“拐点”即两边斜率不等的点了。
那么就可以直接做，二分满足 \(x > Need\) 的所有 \(k\) 里最小的那一个。
很显然 \(Need\) 对应的切点一定在这条线上，这个可以反证，然后算 \(f(Need)\) 就比较简单了。
假设我们求出来的点的横坐标为 \(x\)，显然 \(b = f(x) - kx = f(Need) - kNeed\)
所以 \(f(Need) = f(x) - kx + kNeed\)，也就是说只需要求出来 \(x\) 处的截距然后加上 \(kNeed\) 即可。
ref: - https://www.cnblogs.com/CreeperLKF/p/9045491.html - https://www.cnblogs.com/TianMeng-hyl/p/14972355.html
想要去理解那个自然的思考过程有点难，但是值得。
之前的不知道有没有做到，不过回顾的时候也可以理解一下。