CF573E Bear and Bowling 题解

CF573E Bear and Bowling

题意

• 给定一个长度为 $n$ 的序列 $a_{1\dots n}$。
• 你要求一个 $a$ 的子序列 $b_{1\dots m}$（可以为空），使得 $\sum_{i=1}^m ib_i$ 的值最大。
• $n \le 10^5$，$|a_i| \le 10^7$。

题解

首先有个显然的贪心：每次选择贡献最大的位置，直到贡献非正，此时贡献和即为答案。

这里的贡献可以简单的写成 $k_ia_i+b_i$，其中 $k_i$ 为 $i$ 之前被选择的位置数 $+1$，$b_i$ 表示 $i$ 之后被选择的位置的 $a$ 之和。

相当于我们要维护 $n$ 个一次函数 $k_ia_i + b_i$，支持区间 $k_i,b_i$ 加和全局最大值。

这玩意儿是有办法 $\text{polylog}$ 维护的（详见 EI 的提交），但非常复杂。

考虑分块，块内使用单调队列维护一个上凸壳。

对于每次最大的位置 $p$，先将 $p$ 的贡献计入答案，然后删除 $p$（将 $p$ 的贡献设为 $-\infty$）。

对于 $p$ 之前的位置 $i$，相当于 $b_i$ 加上 $a_p$；对于 $p$ 之后的位置 $i$，相当于 $k_i$ 加上 $1$。

对于每一整块，打上两个分别关于 $k,b$ 的标记即可；而对于 $p$ 所在的块，暴力重构即可。

总时间复杂度 $\mathcal O(n \sqrt n)$。

代码

const int N = 1e5 + 7, M = 370;
const ld inf = 1e18L;
int n, m, k, a[N], b[N], p[N], l[M], r[M];
ll f[N], ans;

struct T {
	int l, r, q[M];
	ll k, b;
	inline ll c(int i) {
		return f[i] + k * a[i] + b;
	}
	inline ld s(int i, int j) {
		if (a[i] == a[j]) return f[i] > f[j] ? -inf : inf;
		return 1.0L * (f[i] - f[j]) / (a[i] - a[j]);
	}
	inline void build(int x) {
		for (int i = ::l[x]; i <= ::r[x]; i++) f[i] += k * a[i] + b;
		k = b = l = r = 0;
		for (int i = ::l[x]; i <= ::r[x]; i++) {
			while (r - l > 1 && s(q[r-2], q[r-1]) < s(q[r-1], p[i])) --r;
			q[r++] = p[i];
		}
	}
	inline pair<ll, int> ask() {
		while (r - l > 1 && c(q[l]) <= c(q[l+1])) ++l;
		return mp(c(q[l]), q[l]);
	}
} t[M];

int main() {
	rd(n), m = sqrt(n);
	for (int i = k = 1; i <= n; k += !(i % m), i++)
		rd(a[i]), f[i] = a[i], p[i] = i, b[i] = k;
	if (!(n % m)) --k;
	for (int i = 1; i <= k; i++) {
		l[i] = r[i-1] + 1, r[i] = min(i * m, n);
		sort(p + l[i], p + r[i] + 1, [&](int i, int j) { return a[i] < a[j]; });
		t[i].build(i);
	}
	while (1) {
		pair<ll, int> o = mp(0ll, 0);
		for (int i = 1; i <= k; i++) o = max(o, t[i].ask());
		if (!o.fi) return print(ans), 0;
		ans += o.fi, f[o.se] = -inf;
		for (int i = 1; i < b[o.se]; i++) t[i].b += a[o.se];
		for (int i = l[b[o.se]]; i < o.se; i++) f[i] += a[o.se];
		for (int i = o.se + 1; i <= r[b[o.se]]; i++) f[i] += a[i];
		for (int i = b[o.se] + 1; i <= k; i++) ++t[i].k;
		t[b[o.se]].build(b[o.se]);
	}
	return 0;
}