wqs二分学习笔记

引入

是什么？ 能用来解决什么问题？

序列 $a$ 有 $n$ 个元素，求选正好 $k$ 个元素和的最大值？

这道题可以用排序，但是这道题可以用来理解 wqs 二分 的思路。
用 $g_k$ 表示选恰好 $k$ 个元素的最佳答案，把 $(k,g_k)$ 形成的点画在坐标系上，就能得到一个「上凸包」。

例如 $a=[9,8,4,2,-9,-15]$ 时，

对于大多数题目，如果没有 $k$ 的限制（即取的次数的限制），应该是可以在可观的复杂度内如 $\mathcal{O}(n)$ 得出答案，比如这道题就是把所有正数加起来，答案相当于求凸包的最高点纵坐标。
但是有了准确的次数限制之后就行不通了。

wqs 二分的作用就是能利用这个和 $k$ 与答案关系 的斜率的单调性，二分一条直线的斜率来切凸包。

什么是切凸包？

wqs 二分的 check 环节在切凸包。

有了一个确定斜率 $c$ 的直线之后，假设与凸包切在一个点 $(p,g_p)$，那么此时一定满足直线的「截距」最大，为 $g_p-c\cdot p$。

这个可以看作是在每个元素基础上加上一个代价 $c$，就是对于每个元素减 $c$ 后，计算不带元素个数限制的本问题的答案 $\mathtt{\text{Maxn}}$，结果就能得到 $(p,g_p)$ 这个点，即 $\mathtt{\text{Maxn}}+c\cdot p=g_p$。

形象地理解，加上代价之后凸包变形，求变形凸包的最高点等同于原来用 $c$ 斜率的直线切凸包，切出来就是最大的截距。

如下图所示，$A^{\prime }{B}^{\prime }{C}^{\prime }{D}^{\prime }{E}^{\prime }{F}^{\prime }{G}^{\prime }$ 便是上图变形后的凸包，点 $(i,p_i)$ 由于加上代价，移动到 $(i,p_i-c\cdot i)$。可以看出，切凸包的斜率为 $c$ 的线，切到的点就是单次加上代价 $c$ 后的答案 $\mathtt{\text{Maxn}}$。

动态演示

动态演示 By qzhwlzy

高级的动态演示

不断改变 $c$，因为斜率具有单调性，可以看出 $p$ 是随着 $c$ 单调变化的。所以通过不断二分 $c$，可以找到需要的 $k$ 的限制。

当然这只是一个思想，还有许多细节需要注意。

例题

买卖股票的最佳时机 IV

套用上面的套路可以发现，答案与限制条件之间的关系是满足 $k$ 与答案关系 的斜率有单调性，加上代价后的答案可以使用线性的 DP 或贪心计算。

点击查看不带限制的 DP 写法

int f[100010][2];
int g[100010][2];

int num, ans;
void fee(int k) { // k 表示每笔交易附加的费用，用于二分
	f[0][1] = -1e9, f[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		if (f[i - 1][0] < f[i - 1][1] + a[i])
			f[i][0] = f[i - 1][1] + a[i], g[i][0] = g[i - 1][1];
		else
			f[i][0] = f[i - 1][0], g[i][0] = g[i - 1][0];
		if (f[i - 1][1] < f[i - 1][0] - a[i] - k) //这样求出来的交易次数也是最小的
			f[i][1] = f[i - 1][0] - a[i] - k, g[i][1] = g[i - 1][0] + 1;
		else
			f[i][1] = f[i - 1][1], g[i][1] = g[i - 1][1];
	}
	ans = f[n][0];
	num = g[n][0];
}

由于我们知道答案都是整数，斜率只需要二分整数就行了，一定能二分到 $k$ 的一段。

点击查看二分代码

int main() {
	int i, k;
	int l = 0, r = 1, mid, Ans = -1;
	cin >> n >> k;
	for (i = 1; i <= n; i++)
		cin >> a[i], r = max(r, (int)a[i]);
	while (l <= r) {
		mid = (l + r) / 2;
		fee(mid);
		if (num <= k) {
			Ans = k * mid + ans;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	if (Ans == -1) {
		fee(0);
		cout << ans << endl;
	} else
		cout << Ans << endl;
	return 0;
}

细节解析：

1. if (Ans == -1) 在此情况下二分失败，说明 $k$ 在非正斜率的部分，直接忽略 $k$ 的限制进行贪心可行；

2. Ans = k * mid + ans; 我们当前切到的点在 $(\mathtt{\text{num}},\mathtt{\text{num}}\cdot \mathtt{\text{mid}}+\mathtt{\text{ans}})$，为什么不写 Ans = num * mid + ans; 呢？

这就要说一个很恶心的情况了。如果凸包上三点共线，我们只能取到上面的一些特殊点（如最左最右的点），不一定取到 $k$；如果读者想要尝试，本题目中以下样例存在该情况：

Hack 数据

8 2
3 3 5 0 0 3 1 4

于是，我们用 DP 处理交易次数最大值，在 $\mathtt{\text{num}}\ge \mathtt{\text{k}}$ 时更新答案，只需要最后一次，但因为不一定能取到等号，所以最好都更新。

或者，我们用 DP 处理交易次数最小值，在 $\mathtt{\text{num}}\le \mathtt{\text{k}}$ 时更新答案，只需要最后一次（而且不能使用 $max$），但因为不一定能取到等号，所以最好都更新。

此外在上面的例子中，我们还发现，k * mid + ans 似乎也有一些单调性，(mid,k * mid + ans) 构成的点很像下凸包......不过我们暂时不研究 其实是不会到时候填坑吧

种树

这道题完美符合上述特点，同样需要注意三点共线情况。写法同样有两种。
写法1
写法2

Tree

与上相同。三份代码详情

• 引入
•     是什么？ 能用来解决什么问题？
•     什么是切凸包？
•     动态演示 By qzhwlzy
• 例题
•     买卖股票的最佳时机 IV
•     种树
•     Tree

__EOF__