感觉一个比较入门的题目是 P2619。你要求的是恰好有 \(need\) 条白色边的，这个很难表示，因为如果直接跑一遍 MST，你不能保证一定选了 \(need\) 条，有可能白色边“太好了”或者“太坏了”。
但是我们发现，如果白色边“越好”，就会尽可能选白色，反之亦然。也就是说如果我们增加一个费用：给所有白色边边权 \(+c\)，设 \(f(c)\) 为加 \(c\) 后的 MST 有多少白色边，这样如果我们算出 \(f(c)\) 和 \(c\) 的图像：\(f(c)\) 随着 \(c\) 增大减少。这样，就可以二分了！
感觉这个就是 wqs 二分的一个“感性理解”。遇到“恰好 \(k\)” 这种限制，可以采用带权二分。
但是上述不是真正的 wqs 二分（嘻嘻）。看看这题 P6821。
因为这一题是“至多 \(k\) 个”，所以我们 dp 时不仅要考虑能达到的最大值，还有达到最大值的最小段数。
在这题中，设 \(f(k)\) 为选恰到 \(k\) 个最大值，则我们可以发现 \(f(k)\) 是一个上凸包：感性理解，\(k\) 太小时，加一点更好，而我们贪心加最好的，所以一定越加越慢，而到达一定点，只能加负数了，就越减越快。理性证明可以用费用流。
这样我们就可以二分每一次分出一个子段的费用了！就变成了一个一维 dp。
总结一下，wqs 二分出现在段数/个数有 \(k,\le k,\ge k\) 这种限制时，并且他的功能是把一个二维 dp 优化成一个一维 dp。
有可能会有一个疑问，就是为什么“上凸”“下凸”这么重要？如果不是这种函数，还可以 wqs 二分吗？wqs 二分究竟是二分什么？
回到上一题，我们二分费用 \(c\) 的时候，求出来有费用的是 \(g(k)\)。真正的答案是 \(f(k)=g(k)+c\times k\)。那么我们发现 \(g(k)\) 就是过 \((k,f(k))\) 点斜率为 \(c\) 直线在 \(y\) 轴的截距。所以，我们二分的 \(c\) 其实是斜率，我们算出来的是被切点。
- 为什么“上凸”“下凸”这么重要？
因为如果不是这样的，斜率就不是单调的了。
再来看一道题：P6246。
和上一题差不多，我们发现是下凸函数。就省略 解法 了。但是会出现一个 wqs 二分经常遇到的问题，就是为啥是 -l*m 而不是 -l*cnt[n]，即为啥不是剪掉/加上最优方案实际选的次数来乘。
这篇博客里面解释了。有一个很直观的图。其实这种问题就是凸包上面点共线的情况。而我们算出来的是截距。如果要求在 \(m\) 处的点的值，必须要减去/加上 \(m\) 乘上二分出来的斜率。
标签：二分,一言两语,白色,wqs,斜率,我们,dp From： https://www.cnblogs.com/SFlyer/p/18412554