Visits: 272

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;
}