WQS二分学习笔记
WQS 二分学习笔记
感谢 小跳蛙 的博客，让我真正理解了WQS二分。
是啥
有的时候我们会遇到一些有数量限制的题目，比如从 \(n\) 个物品中选 \(m\) 个使总和最大（虽然排个序就完了，甚至可以不用排序）。
当物品固定时，选的物品最大价值可以视为一个关于 \(m\) 的函数，这个函数的斜率单调不增。
为什么呢？因为如果斜率增加了，这就说明有一个物品在应该选的时候没有选，这是不优的，与函数的定义不符。
我们将斜率单调不增这个性质称为凸性。WQS 二分适用于答案具有凸性的问题。
如何解决
如果没有数量限制，就把所有正数全都选了就行。
那如果有数量限制呢？我们就让比较小的正数成为零或负数，或者让一些负数成为正数，从而减小或增加选的数的个数。
具体怎么实现呢？我们把所有物品的价值都加上一个数 \(k\)，显然这样可以选更少的数。而且，选的物品的个数关于 \(k\) 是单调的，于是可以二分。
这时有一个 hack：
3 2
1 1 1
答案应该是 \(5\)，但我们按照上面的方法，只能选出 \(0\) 个 或 \(5\) 个。
不难发现，当 \(k=1\) 时，选择 \(0\sim 5\) 个都是合法的。所以我们对于每个 \(k\)，求出最多选多少个物品，最少选多少个物品，只要 \(m\) 在这个区间内，就有解。
实际上，我们不用这么麻烦。只要在最少选择个数合法的情况下，让选择的个数尽量大即可。伪代码如下：
while(l<=r){//可以改成小数二分
mid=(l+r)/2;
check(mid);
if(cnt<=m){//cnt表示k=mid时最少可以选择多少个物品
//合法
ans=tmp-mid*k//更新答案，tmp表示加上影响后的本次答案
l=mid+1//合法就多选点
}
else r=mid-1;//不合法，多了，少选点
}
然后就做完了。
其实还有一个很好的角度去理解，就是函数的斜率。我们要二分一个斜率，然后切这个函数，求切点，建议去看网上的博客，这里不再过多赘述。
例题
P1484 种树
显然具有凸性。
WQS 二分每种一棵树的代价，然后 dp 即可。
P5633 最小度限制生成树
还是具有凸性，可以用边的替换证明。
WQS 二分每连一条到 \(s\) 的边产生的代价，Kruskal 即可。
注意卡常，把与 \(s\) 相连的边和其他的边分别排序，每次归并，即可从 \(O(n\log^2 n)\) 优化到 \(O(n\log n)\)。
CF802O April Fools' Problem (hard)
显然具有凸性。
WQS二分 \(a\) 的代价，然后就不会了。
这里显然可以 \(O(n^2)\) dp，也可以 \(O(n\log n)\) 的反悔贪心。
考虑到每天的打印都有两个用途：
- 和之前的一个 \(a\) 配对，产生 \(b_i+a_j\) 的费用
- 替换掉之前的一个 \(b\)，产生 \(b_i-b_j\)
所以开一个小根堆，每天先把这一天的 \(a\) 放进堆里，然后用今天的 \(b\) 去匹配或替换，如果匹配到了就把 \(-b\) 放进堆里，再处理一下匹配的个数。
总复杂度 \(O(n\log^2 n)\)。
CF739E Gosha is hunting
当 \(b\) 固定时，显然答案关于 \(a\) 有凸性。
所以WQS每用一个 \(a\) 的代价，然后进行 \(O(n^2)\) 的 dp。
总复杂度 \(O(n^2\log n)\)。
虽然有 \(O(n\log^2 n)\) 和 \(O(n\log n)\) 的做法，但是萌新太菜了，没看懂QwQ
P4983 忘情
先化简一下式子：
发现最烦人的绝对值没了。如果没有个数限制，这个式子可以斜率优化。
于是WQS二分每分出来一段的额外代价，斜率优化即可。复杂度 \(O(n\log n)\)。
P4383 [八省联考 2018] 林克卡特树
题意可转换为，给定一棵树，在上面选 \(k+1\) 条链，使它们的权值之和最大。
如果没有数量限制，这个可以在树上 dp。设 \(f_{i,0/1/2}\) 表示当前点不在链上、在不完整的链上、在完整的链上的子树答案，转移即可。
所以WQS二分每选出一条链的额外代价，跑一遍 dp 即可。
小Trick
pair
如果题目是 WQS 然后 dp，要记录物品的个数就会很麻烦。所以我们使用伟大的 pair，并重载运算符，使得加减乘除能够使用。而且由于 pair 本身就是双关键字，所以可以自动完成选择较大或较小物品数量的工作。
重载运算符代码：
#define P pair<double,int>
P operator + (P a,P b){
return make_pair(a.first+b.first,a.second+b.second);
}
P operator + (P a,double b){
return make_pair(a.first+b,a.second);
}
P operator - (P a,double b){
return make_pair(a.first-b,a.second);
}