wqs二分

Agleia · 2024-08-13 22:10:50 · 算法·理论

wqs二分

发现网上的 wqs 二分文章都在凸包凸包，其实跟凸包关系不大。

由于本文的证明更为代数，所以无图警告！

wqs 二分（也叫带权二分）用于解决一类问题，这种问题的特征非常明显。

1.钦定在 n 个物品中选择恰好 k 个物品，然后计算它的权值和之类的。

2.直接做不管怎么优化都是 O(nk) 的，但是去掉k的限制却十分好做。

3.设 f(i) 表示 i 的值为 k 时的答案，该答案具有单峰或单谷性。

由于性质2你直接做大概率用 dp ,去掉之后大概率也用 dp ，所以这算法也叫 dp 凸优化

当然直接基本不是反悔贪心就是 dp 。

对于一道题，如果有性质 1,2，但你不知道有没有性质3，~~你可以直接猜它有~~

这个算法不结合例题理解十分抽象，在这里放一道例题。

gmoj8118. 【2022.10.12联考noip模拟】coffee

题意

在接下来 n 天之中，每天咖啡店的价格是不同的，第i天咖啡的价格为 r_i 。

你手上有m张优惠券，每张优惠券会在第 r_i 天后过期（第 r_i 天时还可以使用），优惠券只能在购买咖啡的时候一并使用，从而使得那杯咖啡价格减少 w_i 元，一天最多使用一张优惠券。

需要注意的是，由于老板并不聪明，咖啡的价格可以变成负数。

由于你最近出题很累，需要喝咖啡补充能量，但是过多的咖啡因不利于身体健康，所以你决定在这 n 天之中，选择恰好 k 天，购买咖啡。

求最小花费。

这道题一眼满足性质1,2。

性质3并不一眼，但我们通过简单推理发现也是符合的。

套路地，先考虑去掉 k 的限制怎么做，去掉 k 的限制之后答案一定是非正数。

然后考虑反悔贪心，我们把优惠券按照 r_i 排序，然后对于一个 r_i 找到前面的最小的一杯 a_k 匹配，产生 a_k-r_i 的贡献（贡献显然不能>0)。

但是可能后面的另一个 r_j 会抢走这杯 r_i，那么我们添加一杯“虚拟咖啡”,价格为 r_i。

上述操作可以用堆维护。

这样如果需要反悔，对答案的贡献相当于 a_k-w_i+w_i-w_j=a_k-w_j。

注意可能出现 a_k-w_j=w_i-w_j 的情况，此时优先选择咖啡而不是"虚拟咖啡"。（具体原因在后面叙述）

这样复杂度 O(n\log n)。

接下来我们二分一个 mid，表示选择一杯咖啡需要额外付出 mid 的代价（注意 mid 可能为负）

然后我们用反悔贪心计算此时的答案。并记录此时答案选择的咖啡杯数 s

接下来分讨。

如果 s=k，说明刚刚好，直接计算答案（注意减去额外权值）

如果 s>k，说明权值给的太小了， l=mid+1。

否则说明权值给的太大了， r=mid-1。

然后做完了。

但是有一种特殊情况（虽然本题造的数据并没有）：

二分权值为 mid 时，s<k ，为 mid+1 时， s>k

这种情况如何处理呢？我们考虑 s=k 一定夹在两种情况之中。

一个看起来很好的做法是小数二分 ~~，确实可以，但有的题卡你小数二分~~。

我们考虑为什么会出现这种情况，发现是因为出现 a_k-w_j=w_i-w_j 的情况时我们优先选择咖啡而不是"虚拟咖啡"。

那么我们发现我们两种方法之间如果替换是等价的，也就是说我们可以把 s>k 的变换成 s=k，答案不变。

也就是说我们直接在 s\ge k 的时候计算答案即可。

如果你先选"虚拟咖啡"，也行，只是我们变成把 s<k 的变换成 s=k，答案不变。

这种时候在 s\le k 的时候统计答案就行

因此，我们在维护堆的时候，要加一个第二关键字，表示它是真咖啡还是“虚拟咖啡”，并且第二关键字一定要有大小关系，否则你就不能直接统计答案！！！

这样就做完了，时间复杂度 O(n\log n\log V)。

假如你对这道例题有了一些一知半解的理解，我们就可以开始抽象模型。

抽象模型

我们考虑原本答案为一个函数 f(x)，我们二分相当于二分一条直线y=ax的斜率a。

我们减权值的操作相当于构造一个新的函数 g(x)=f(x)-ax，显然这个函数也是单峰或者单谷函数

然后我们希望这个函数的最值是 (k,g(k))，这样我们就去掉了那个恰好为k的限制。

但是显然我们构造出的方案不一定能满足这个条件。

我们考虑最值位于 (k',g(k'))，那么也就是说 g(k')<g(k) (假设求的最值为最小值，最大值同理)

即 f(k')+ak'< f(k)+ak。

当k'<k的时候，移项可得 \large a>\frac{f(k')-f(k)}{k-k'}

只要不满足这个条件，则 g(k')>g(k)，则最值为 g(k)。所以我们应该减小 a，反之应该增加 a

至于上题中的特殊情况，我们发现是出现了 f(k')+ak'=f(k)+ak 的情况。

而我们的处理方式就是只记录这种情况的最左点或者最右点，因为答案都是一样的，所以选择哪个点其实没区别，只要减掉的是对应的额外贡献就行。

所以 wqs 二分是对的。

习题

P2619 [国家集训队] Tree I

板中板，1,2,3性质都比较显然了。

套路地给白边二分加一个权值 mid，然后直接跑 MST 就行了。

P4383 [八省联考 2018] 林克卡特树

首先我们发现一件事，把链接在一起其实如接，一条大链的权值和与选出的k+1条不相交的链的权值和相同。

那么我们考虑先设一个 dp 状态 f_{i,j} 表示点 i 的子树内有 j 条链的方案数，发现完全无法转移，因为你不知道点 i 的状态

然后发现由于是选出 k+1 条不相交的链,所以每个点的度数至多为2

于是我们设 f_{i,j,0/1/2} 额外记录点 i 的度数，每次转移分类讨论是否将该点与其儿子接上。

如果接上那么转移到度数+1，dp 值在权值和的基础上加上边权，否则转移到度数相同的点，dp 值简单相加。应该还是好想的。

这样时间复杂度是 O(nk) 的，然后我们通过感性理解+打表发现这个答案随着k的变化是凸的

然后套个 wqs 二分，在 dp 的时候额外记录选了几条链即可。

时间复杂度 O(n\log n)

P4694 [PA2013] Raper

限制 k，5\times 10^5 ,纸接套wqs二分。

考虑去掉k如何做，发现跟例题1差不多，直接反悔贪心做即可。

P6821 [PA2012] Tanie linie

双倍经验

三倍经验

考虑转化为恰好 k 个，发现如果正数的个数 \le k ，那么可能不能选出 k 个区间。

然后考虑设 f_{i,0/1} 表示第i个数选或者不选的答案，直接 O(n) 转移即可

P5633 最小度限制生成树

~~传奇WA13发~~

最难点在于判无解，其他跟第一道例题类似。

考虑找到二分的左右端点 l,r,我们记与 x 相连的边为关键边。

那么如果二分 l 的时候都选不出 k 条边或者在 r 的时候都选了超过 k 条边，那么无解。

然后直接做，注意到你不能每次 wqs 二分都排序，于是你先对关键边和非关键边分别排序再归并。

这样时间复杂度是 O(m\log V\alpha(n)) 的。

[ABC218H] Red and Blue Lamps

如果前面的题都会了应该能随便秒。

设 f_{i,0/1} 表示当前点选红/蓝，发现贡献只跟上一个有关，套个板子随便过了。