wqs 二分简记

wqs 二分一般用于解决这样的问题：\(n\) 个物品，恰好选 \(x\) 个获得的最大或最小价值为 \(F(x)\)，求 \(F(K)\)。\(F\) 需要具有凸性质。

二分一个斜率 \(k\)，check 时，用斜率为 \(k\) 的直线去切凸包。具体地，将每个物品的价值减去 \(k\)，取消个数限制，求出最大或最小的价值 \(b\) 和此时选择的物品个数 \(x\)，则可以发现 \(b=F(x)-kx\)，故切点为 \((x,kx+b)\)。如果它不是切点，其对应的截距必然更劣。可以画图理解。如果有多个切点，可以想办法保证取到最左或者最右的切点。

例题：Luogu P4694 [PA2013] Raper

基本上是 wqs 二分的模板题。首先我们可以将题目转化为：一张左右各 \(n\) 个点的二分图，左部第 \(i\) 个点向右部 \(j\ge i\) 的点连边，一个匹配的权值为两点的点权和，求恰好 \(K\) 对匹配的最小权值和。这显然是一个费用流模型，我们知道费用流问题肯定是凸的（现在我还不会证明），所以这个函数应当是下凸的。

于是跑 wqs 二分，check 是一个很容易的反悔贪心，注意实现细节保证取的匹配数最少或最多。

#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+5;
typedef long long ll;
typedef pair<ll,int>pli;
int n;ll a[N],b[N];
pli check(ll k){
	ll sum=0;int cnt=0;
	priority_queue<pli,vector<pli>,greater<pli>>q;
	for(int i=n;i>=1;i--){
		q.emplace(b[i]-k,i);
		if(q.top().first+a[i]<0){
			auto[val,pos]=q.top();q.pop();
			sum+=a[i]+val;cnt+=!!pos;
			q.emplace(-a[i],0);
		}
	}
	return pair(sum,cnt);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int K;cin>>n>>K;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	ll l=0,r=2e9,ans=1;while(l<=r){
		ll mid=(l+r)>>1;
		auto[b,cnt]=check(mid);
		if(cnt<=K)ans=b+mid*K,l=mid+1;
		else r=mid-1;
	}
	cout<<ans<<'\n';
	return 0;
}