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\) 后,计算不带元素个数限制的本问题的答案 \(\texttt{Maxn}\),结果就能得到 \((p,g_p)\) 这个点,即 \(\texttt{Maxn} + c\cdot p = g_p\)

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

如下图所示,\(A’B’C’D’E’F’G’\) 便是上图变形后的凸包,点 \((i,p_i)\) 由于加上代价,移动到 \((i,p_i-c\cdot i)\)。可以看出,切凸包的斜率为 \(c\) 的线,切到的点就是单次加上代价 \(c\) 后的答案 \(\texttt{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; 我们当前切到的点在 \((\texttt{num},\texttt{num} \cdot \texttt{mid} + \texttt{ans})\),为什么不写 Ans = num * mid + ans; 呢?

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

Hack 数据
8 2
3 3 5 0 0 3 1 4

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

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

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

种树

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

Tree

与上相同。三份代码详情

张贴在2