天才算法！
国外叫 Aliens trick （外星人 trick） ，真的太强了。
其实是因为 IOI2016 Aliens 这道题考了这个算法才开始普及。
解决问题
wqs 二分一般用来解决如下问题。
给定 \(n\) 个数，求强制选 \(m\) 个的价值最大。
如果不是强制选 \(m\) 个，这类问题很好做。
现在问题就是怎么取消掉强制取 \(m\) 个这个限制。
这就是 wqs 二分的用途，它能在一定条件下优化 dp ，\(O(nm)\to O(n\log m)\)。
模型引入
wqs 二分有一个重要条件。
令 \(g(i)\) 表示当强制选 \(i\) 个时的最大价值,把所有 \((i,g(i))\) 在坐标轴上画出来，最终形成一个凸包。这就是算法实施的必要条件。
还有一个必要条件就是，每个价值计算是独立的，也就是说，\(w(\{x_1,x_2,x_3...\})=w(x_1)+w(x_2)+w(x_3)...\)
算法分析
我们假设当前凸包是上凸的。
明显，像斜率优化那样，如果我们拿一条直线去切这个凸包（也就是把这条直线从上往下移，碰到的第一个点），那么，很容易的发现，斜率越大，切到的点越往左。
我们想，如果拿一条斜率为 \(k\) 的直线去切，切到的是哪个点。
明显，如果对于每个点都划一条斜率为 \(k\) 的直线，那么与 \(y\) 轴交点最上的的那个点，就是被切的点。
根据小学的知识，我们知道交点的计算公式是 \(f(x)=b=g(x)-kx\)
想想这是什么。
这不就是等价于，把每个物品价值减 \(k\) ，就是 \(w(x)\to w(x)-k\)
然后，你要求 \(\max(f(x))\) ，不就是等价于取消了强制取 \(m\) 的限制了吗！
在取消资格限制的同时，你还能把取到 \(\max(f(x))\) 的 \(x\)
标签：二分,wqs,小计,凸包,斜率,强制,dp From： https://www.cnblogs.com/g1ove/p/18144397