wqs二分

· · 个人记录

简介

wqs（王钦石）二分是一种化恰好为无限制的巧妙算法。

考虑一种 01 背包问题：有 n 个物品，选其中 m 个，求价值的最值？以最大值为例。

这里的“物品”是广义的，考虑朴素 \rm dp？受限于状态数过多，复杂度至少 O(n^2)。

wqs 二分运用数形结合分析并简化问题。前提条件：将 (i,g_i) 看成点，在平面直角坐标系上构成上凸包（斜率单调递减）。

其中，g_i 表示选恰好 i 个的最大值。求出 g_m 即可。

我们枚举斜率 k，令一条斜率为 k 的直线从上往下扫，扫到凸包第一个点 p。此时若 p\le m，那么必须让斜率 \ge k 才能扫到 m；反之斜率 <k。显然可以二分。

现在的问题是，怎么求出 (p,g_p) 呢？

考虑 f_i 表示直线扫到 i 时对应截距，即 f_i=g_i-ki。

那么必然 f_p=\max f，所以问题转化为求 \max f。

不妨让所有物品的价值 -k，然后不受限地取就好啦。

共线

注意一个大坑点：凸包上共线的情况。

如果不加以处理，就容易忽略掉正确答案。

具体需要看最后答案输出的是 l 还是 r，这根据 = 号取在哪决定。

以输出 r、上凸包为例，可以每次取得最左端，使得 m 无论位于共线上哪处时，都可以有 r=mid。

最重要还是因题而异吧。

题目

证明考虑其 MST，不妨设为 g_p，那么选取一条不属于 MST 且与 s 相连的边，在最小生成树上构成环，类似次小生成树替换得到新的 MST，那么增长值最小的方案就是 g_{p+1} 了。

显然，改变替换边的顺序不会影响得到的 MST 权值，所以随着 p 增长，g 的变化值递增。对于 p 递减同理。所以是个下凸包。

套 wqs 二分即可，check 部分是容易的。

注意判合法性，注意到下凸包一定是连续的，用斜率为 -inf,inf 的直线扫出下凸包的左右边界，若 k 在边界外就是非法的。

移动 p，那么必然是将一段连续子串反转，如：101\to 010。对于所有合法调整，价值必然小于原价值。

考虑 g_{p+1},g_{p+2}，若调整区间不重合，则一定有 g_{p}-g_{p+1}\ge g_{p+1}-g_{p+2}。否则，重合区间等价于撤销调整，即分别操作 [l,r]、[x,y]，等于操作 [l,x-1]、[r+1,y]，g_{p+1}-g_{p+2}=val[x,y]，显然 val[x,y]\le val[l,r]。

斜率递减，构成上凸包。

考虑怎么求 \max f，先让 a_i-slope，无限制地选取即可。

注意到 1\le a,b，那么只考虑减去 slope 后为负数的 a 即可。

我们只关注选取了那些 a,b，而不关心如何配对。所以等价于选取 a_{p_1}\dots a_{p_m} 和 b_{q_1}\dots b_{q_m}，且 \forall p_i\le q_i。

从后往前，依次为 a 配对，贪心地选取最小的 b 即可，用一个小根堆维护就好了。

注意可以让当前的 a 替换掉之前的 a，怎么实现？只需将 -a 加入堆即可。

首先，显然 g_i 构成上凸包，因为顺序无影响。

那么考虑 f_i 的实际含义，等价于更改 i 条边，代价为 -i*slope，然后求直径。

因为删去边会得到森林，最优连边方案显然是将所有树的直径首尾相连。

没必要非得看作森林，关注直径就好了。于是 f_i 实际上是在原树选 i+1 条不相交的链，边权和减去 i*slope。

不妨选一条链就 -slope，最后再加上 slope。

然后容易树形 \rm dp，记 f_{u,0/1/2} 表示对于 u 子树，u 未被选、往下延申一条链和随意的最大价值。

为了方便实现，不妨将链只有 u 一个点的方案也算进 f_{u,1} 中。转移是容易的。