带权二分（wqs 二分）解析

引入

现在给出 $n$ 个物品和 $k$ 的限制，要求从 $n$ 个物品中选出恰好 $k$ 个物品满足物品权值之和最大/小。

这是 wqs 二分的经典模型，或者说：

给出 $n$ 个物品，要求划分为 $k$ 组，任意物品组都有权值，要求每组的权值之和最大/小。

用数学语言表达就是：

构造 $k$ 个集合 $S_1,S_2,\dots,S_k$ 满足任意两个集合交为空，所有集合并为全集，此时求 $\max{w_{S_1}+w_{S_2}+\dots+w_{S_k}}$​。

但是在大部分时候 $S$ 的划分都有贪心在里面，所以实际上 $S$ 的每个集合都是 $n$ 个物品按照一定顺序排列后的区间，在后面的例子中会见到它。

用例

下面我们用两个用例来更好地解释一下 wqs 二分模型以及其原理，上面讲述了 wqs 二分的两种常见模型，接下来是第一种模型，由于没有较好的例子，因此我们选择一个“简单”的题目：

给定 $n$ 个物品，每个物品有权值 $w_i$，要求选恰好 $k$ 个满足物品权值和最大。

一个简单的做法就是排序后选就可以了，这显然不是 wqs 二分，时间复杂度为 $O(n \log n)$，我们考虑不用排序，转而 dp：
$$
f_{i,j} = \max(f_{i-1,j},f_{i-1,j-1}+w_i)
$$
这就是最简单的 dp 式，但是它是二维的，时间复杂度也是 $O(n^2)$，我们观察 $f_{n,i}$ 在图上以 $i$ 为 $x$ 轴，$f_{n,i}$ 为 $y$ 轴的图像：

这个时候它是一个上凸壳的样子，意味着我们可以用一条线去截它，并且每个点都有可能被线截到（三点共线除外），并且我们发现截取每个点的直线斜率是单调的，于是我们直接二分这条直线的斜率，然后考虑 dp 求出这条直线截凸包时的截距是多少，容易发现，设截距为 $p$，那么第 $i$ 个点截出来的截距就是 $f_{n,i}-ip$，于是我们令每个物体的代价减去 $k$，最后再额外记录选了多少个物品就是这条线截出来的点，即：
$$
f_i = \max(f_{i-1},f_{i-1}+(w_i-p))
$$
然后再记一个 $g$ 表示选了多少个物品即可，最终 $(g_n,f_n)$ 就是截出来直线与凸包相交的点，对于这道题而言，如果 $g_n=k$，直接输出答案即可；如果 $g_n<k$，那么代表当前直线截距太大了；如果 $g_n>k$，那么代表当前直线斜率太小了；但是有三点共线的情况截不到 $k$ 这个点，因为都知道斜率了，所以直接得到 $f_{n,k}$ 的答案并不难，直接加上 $kp$ 即可。

具体实现上，二分到一定精度，直接四舍五入输出 $f_n+kp$ 就可以了，不需要一定截取到 $k$​​ 这个点。

那么这样就用 wqs 二分实现了这个简单的问题，但是它的精髓是将二维 dp 转化为一维 dp 然后解决，十分巧妙。

通过一道简单的题目得知 wqs 二分的具体作用之后，我们可以上一点层次了，尝试解决之前提到的那个问题：

有 $n$ 个小镇，你需要从中恰好选择 $k$ 个不重复的小镇，$\sum_{i=1}^n dis_i$ 最小，其中 $dis_i$ 表示距离 $i$ 号小镇最近的被选择的小镇距离它多少单位。

首先，贪心地将这些小镇按照数轴顺序排序，设 $w_{l,r}$ 表示 $l \sim r$ 号小镇中选择一个，其他小镇（$l \sim r$）到这一个小镇的距离和最小是多少，容易发现选中位数就可以了。

那么得到：
$$
f_{i,j} = \min_{k=1}^i {f_{k-1,j-1}+w_{k,i}}
$$
因为 $w$ 函数具有四边形不等式（证明略）并且观察得到 $f_{n,i}$ 具有凸性，于是直接二分斜率 $p$ 即可，二分之后按照普通的优化四边形不等式的 dp 就可以了，下面给出参考代码，时间复杂度 $O(n \log^2 n)$​​。

原题：P6246 IOI2000 邮局 加强版 加强版。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#include<bits/stdc++.h>
#define ll long long
#define N 500005
using namespace std;
ll n,m,i,a[N],f2[N],ans2,beg[N],head,tail,pos[N],pro[N];
double f1[N],ans1;
double l,r,mid;
inline ll calc(ll l,ll r){
	if(l>r) return 0;
	if(l==r) return 0;
	ll pos = (l+r)/2;
	return a[pos]*(pos-l+1)-(pro[pos]-pro[l-1])+(pro[r]-pro[pos])-(r-pos)*(a[pos]);
}
inline void solve(double val){
	ans1=1e18,ans2=-1,f1[0]=0,f2[0]=0;
	head=1,tail=1,beg[head]=1,pos[head]=0;
	for(ll i=1;i<=n;i++){
		while(head<tail&&beg[head+1]<=i) head++;
		f1[i]=f1[pos[head]]+calc(pos[head]+1,i)+val,f2[i]=f2[pos[head]]+1;
		while(head<=tail&&f1[pos[tail]]+calc(pos[tail]+1,beg[tail])>f1[i]+calc(i+1,beg[tail])) tail--;
		if(head<=tail){
			if(f1[pos[tail]]+calc(pos[tail]+1,n)<f1[i]+calc(i+1,n)) continue;
			ll l=max(beg[tail],i),r=n;
			while(l<r){
				ll mid = (l+r+1)/2;
				if(f1[pos[tail]]+calc(pos[tail]+1,mid)<f1[i]+calc(i+1,mid)) l=mid;
				else r=mid-1;
			}
			tail++,beg[tail]=l+1,pos[tail]=i;
		}
		else tail++,beg[tail]=i+1,pos[tail]=i;
	}
	ans1 = f1[n],ans2 = f2[n];
	return ;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(i=1;i<=n;i++) cin>>a[i],pro[i]=(pro[i-1]+a[i]);
	l=0,r=1e10;
	while(r-l>1e-8){
		mid=(l+r)/2;
		solve(mid);
		if(ans2<m) r=mid;
		else if(ans2==m){
			cout<<(ll)(round(ans1-m*mid))<<endl;
			return 0;
		}
		else l=mid;
	}
	cout<<(ll)(round(ans1-m*mid))<<endl;
	return 0;
}

总结

wqs 二分应用的场景还很多，特别是在一些大型比赛中，只要函数有凸性（可以是整个上凸壳，不一定单调；或者下凸壳），都可以把二维状态压缩成一维。

不过要特别注意的是，函数单调不代表其具有凸性，这里需要特别注意。

上面就是 wqs 二分，也称带权二分的大部分用法，还算比较容易理解的了。

注意：

二分斜率时候二分整数就可以了，因为就算三点共线的时候，$f$ 的差值也一定是整数。

遇到三点贡献的时候需要钦定一下选最小的点还是最大的点，这样的话二分的时候才能判断到底是哪个指针移动才不会出错。