wqs二分学习笔记中，有哪些可以优化我的学习效果？

wqs 二分 适用条件 对于一些满足以下要求的题目： 1.其有形似恰好 \(k\) 个的形式。 2.如果没有恰好 \(k\) 的形式是十分可做的。 3.设恰好选 \(k\) 个的答案为 \(f(k)\)，那么由 \((k, f(k))\) 构成的图像为一个凸包。 ps：第三条一般打表找规律。 那么我们就可以使用 wqs 二分。 思路 对于这样一个上凸包（下凸包是同理的）： 我们假设要求 \(f(k)\)。 如果我们忽略掉选 \(k\) 个的限制，我们发现我们肯定选到 \(y\) 坐标即 \(f(x)\) 最高的点 \((x, f(x))\)，这时候的 \(x\) 不一定等于 \(k\)。但是我们只会把选 \(k\) 个的条件忽略掉做啊，那我们想想可以怎么样加一些限制使选到的点恰好是 \((k, f(k))\)。 那我们可以对每个 \((x, f(x))\) 变成 \((x, f(x) + x * val)\) (\(val \in R\)，即 \(val\) 可正可负可为零)。我们发现新图仍然是一个凸包，但是凸包最高点的位置变化了。以图中的上凸包为例，如果 \(val\) 过小，凸包最高点会左移，过大会右移，如果刚刚好的话新凸包的最高点就恰好是 \((k, f(k) + k * val)\)。我们发现这个是具有单调性的。 于是我们可以对 \(val\) 进行二分。 check() 就是忽略掉限制直接最优的选。但是对于每一个要选的物品（即规定要选 \(k\) 个的那个东西）的贡献都加上 \(val\)，那么我们选 \(x\) 的贡献就刚好被加上了 \(x * val\)。 最后返回最高的 \((x, f(x) + x * val)\) 即可。