最近才学习了WQS二分，发现这是一个很有用的东西。
大概是这样一类问题：决策\(i\)对答案有\(w_i\)贡献，求恰好做\(k\)次该类决策的最大答案
考虑不限制决策的次数，但每个决策除贡献外，都减去一个代价\(cost\)
这样通过调整\(cost\)的值，就能够控制决策的次数
WQS二分其实就是二分这个\(cost\)，使得最优解做不大于\(k\)次该类决策，且\(cost\)尽量大
设最优解做了\(x\)次该决策，定义\(g(x)\)为最优解（不减\(cost\)），\(f(x)\)为最优解
则有：\(g(x)=kx+f(x)\)
\(k\)其实就是\(cost\)
你会发现这其实就是在二分\(g(x)\)的斜率，使该斜率对应的\(x\)满足题意
这样我们就得到了WQS二分的条件：原贡献关于决策次数的函数\(g(x)\)斜率单调（\(g'(x)\)单调）
值得注意的是，最后得到的\(cost\)，对应决策次数不一定是\(k\)（\(g‘(x)\)某段水平）
但这并不影响答案，因为\(g'(x)=g'(k)\)意味着\(f(x)=f(k)\)，我们要的就是\(f(k)\)
推荐题目：BZOJ2654 tree、Codeforces 739E Gosha is hunting
