题解 CF573E 【Bear and Bowling】
xht
2020-02-14 02:32:26
> [CF573E Bear and Bowling](https://codeforces.com/contest/573/problem/E)
## 题意
- 给定一个长度为 $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 的提交](https://codeforces.com/contest/573/submission/68101378)），但非常复杂。
考虑分块，块内使用单调队列维护一个上凸壳。
对于每次最大的位置 $p$，先将 $p$ 的贡献计入答案，然后删除 $p$（将 $p$ 的贡献设为 $-\infty$）。
对于 $p$ 之前的位置 $i$，相当于 $b_i$ 加上 $a_p$；对于 $p$ 之后的位置 $i$，相当于 $k_i$ 加上 $1$。
对于每一整块，打上两个分别关于 $k,b$ 的标记即可；而对于 $p$ 所在的块，暴力重构即可。
总时间复杂度 $\mathcal O(n \sqrt n)$。
## 代码
```cpp
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;
}
```