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;//不合法，多了，少选点
}

然后就做完了。

其实还有一个很好的角度去理解，就是函数的斜率。我们要二分一个斜率，然后切这个函数，求切点，建议去看网上的博客，这里不再过多赘述。

例题

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

\[\begin{align} &\frac{\left(\sum x_i\times \bar x+\bar x\right)^2}{\bar x^2}\nonumber\\ =&\left(\frac{\sum x_i\times \bar x+\bar x}{\bar x}\right)^2\nonumber\\ =&\left(\sum x_i+1\right)^2\nonumber\\ \end{align} \]

发现最烦人的绝对值没了。如果没有个数限制，这个式子可以斜率优化。

于是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);
}