CF573E Bear and Bowling

chzhc · 2022-04-06 22:08:55 · 题解

\mathcal O(n^2) 做法

设 f(i, j) 表示前 i 个数选了 j 个数所能组成的序列的最大价值。

显然有转移：

直接转移即可，时间复杂度 \mathcal O (n^2)。

\mathcal O(n\sqrt{n}) 做法

有一个贪心的结论：

我们依次加入每个数，对于 \forall \text{ }i，位置 i 的贡献为 V_i=k_i \times a_i+b_i，其中 k_i 为位置 i 之前被选的数的个数加一，b_i 为 i 之后被选的数的和。那么我们每次选贡献最大的位置得到的序列均为该序列大小下的最优解。

引理 1. 在上述贪心策略下，如果 a_i>a_j 且 i<j，则选 i 之前不可能选 j。

考虑归纳证明：假设引理 1 不成立，考虑整个过程中我们第一次违反这个引理的操作。如果 i 和 j 之间不存在已经取了的元素，那么由于 a_i > a_j，i 的贡献必然比 j 大（k 和 b 都相等）；否则，对于 i 和 j 之间存在已经取了的元素 x，由于 i, j 是第一次违反引理的操作，所以 a_x \geq a_i，所以 a_x \geq a_i > a_j，又考虑到 x 对 V_i 的贡献是 a_x，x 对 V_j 的贡献是 a_j，故 V_i > V_j，不可能先选择 j，由此可知，i, j 不是第一次违反这个引理的操作，假设不成立，故引理 1 得证。

下面证明上面的贪心。

假设不成立，我们考虑第一个不满足这个贪心的时刻，对于某个大小 s，令集合 A 表示该时刻之前已经选取的元素集合，存在 B(A \bigcap B = \varnothing) 和当前价值最大的 V_x(x \notin A, x \notin B)，使得 A \bigcup x 不是任何一个大小为 s 的最优解的子集，且 A \bigcup B 是一个大小为 s 的最优解。考虑分类讨论：

1. 如果 B 中存在位置在 x 的左边，考虑在 x 的左边的最右位置 y，根据引理 1，此时有 a_y \leq a_x，V_x \geq V_y。此时加入集合 B 中的其他元素，我们考虑 V_x,V_y 的变化，那么在 x 右边的元素对 V_x,V_y 的贡献一样，在 y 左边的元素对 V_x,V_y 的贡献是 a_x,a_y，而 x,y 中间没有在 B 中的元素，所以可以发现在其他元素加入之后 V_x \geq V_y，所以将 B 中 y 换成 x 结果不劣。
2. 如果 B 中只有在 x 右边的元素，考虑在 x 右边的最左位置 y，那么 B 集合其他的元素对 V_x,V_y 的贡献是一样的，所以把 y 换成 x 也不会更劣。

故上述假设不成立，贪心正确性证毕。

考虑分块维护凸包从而维护最大值。 每次选完最大值，就相当于对于选定的 pos，pos 前的位置 i 中 b_i 均加上 a_{pos}，pos 后的位置 i 中 k_i 均加上一。因为对于同一块我们加上的 k,b 是一样的，而 pos 所在的块可以 \sqrt{n} 暴力重构凸包，并将 pos 赋为负无穷。我们需要在改变 k 的情况下维护若干一次函数 k \times a_i + b_i 的最大值，可以通过在凸包上三分得到。

时间复杂度 \mathcal O(n \sqrt{n}\log n)。

由于 k \times a_i + b_i 中的 k 是单调不降的，因此我们可以使用单调指针代替三分，其次，重构凸包时不需要每次都对点集进行排序，注意到 a_i 是不变的，初始时排序一次即可。时间复杂度 \mathcal O(n \log n + n \sqrt{n})。

\mathcal O(n \log n) 做法

有一个结论：对于 \forall \text{ }i \in [1, n], \exists \text{ }k\in[1, i] 满足：

设 F(i, j) 表示前 i 个数选了 j 个数，组成的序列中最大价值的某种方案的下标集合。

根据前面的贪心结论，若 i \in F(i, j) 则一定存在一种方案使得 i \in F(i, j + 1)，这也就证明了上述结论。

首先可以去掉第一维，考虑二分出 k，观察转移式子，相当于在某处插入一个新值，然后给后面一部分加上一个等差数列。

所以用平衡树来实现即可。其实可以直接在平衡树上二分。时间复杂度 \mathcal O(n \log n)。

#include <bits/stdc++.h>
const int N = 1e6 + 10;
template < typename T >
inline void read(T &cnt)
{
    cnt = 0; char ch = getchar(); bool op = 1;
    for (; ! isdigit(ch); ch = getchar())
        if (ch == '-') op = 0;
    for (; isdigit(ch); ch = getchar())
        cnt = cnt * 10 + ch - 48;
    cnt = op ? cnt : - cnt;
}

int n, a[N];
long long D, P, ans;

namespace FHQ
{ 
    // fhq treap 维护首项 a0 公差 d
    // 以及当前值 val 和当前区间最右边的值 rval
    struct treap
    {
        int lc, rc, siz; int rnd;
        long long val, rval, a0, d;
    } t[N];

    int root, tot;

    inline int New(long long x)
    {
        ++ tot; t[tot].siz = 1; 
        t[tot].rnd = rand();
        t[tot].val = t[tot].rval = x;
        t[tot].a0 = t[tot].d = 0;
        t[tot].lc = t[tot].rc = 0;
        return tot;
    }

    inline void upd(int p)
    {
        t[p].siz = t[t[p].lc].siz + t[t[p].rc].siz + 1;
        t[p].rval = t[p].rc ? t[t[p].rc].rval : t[p].val;
    }

    inline void addAll(int p, long long a0, long long d)
    {
        // a0 表示前一个 即 p 子树加的值分别为 a0 + d, a0 + 2d ...
        t[p].val += a0 + (t[t[p].lc].siz + 1) * d;
        t[p].rval += a0 + (t[p].siz) * d;
        t[p].a0 += a0; t[p].d += d;
    }
    inline void psd(int p)
    {
        addAll(t[p].lc, t[p].a0, t[p].d);
        addAll(t[p].rc, t[p].a0 + 1ll * (t[t[p].lc].siz + 1) * t[p].d, t[p].d);
        t[p].a0 = t[p].d = 0;
    }
    inline void split(int p, int k, int &x, int &y)
    {
        if (! p) 
        {
            x = y = 0;
            return;
        }
        psd(p);
        if (t[t[p].lc].siz >= k)
        {
            y = p;
            split(t[p].lc, k, x, t[p].lc);
        }
        else
        {
            x = p;
            split(t[p].rc, k - t[t[p].lc].siz - 1, t[p].rc, y);
        } 
        upd(p);
    }

    inline int merge(int x, int y)
    {
        if (! x || ! y) return x + y;
        if (t[x].rnd > t[y].rnd)
        {
            psd(x);
            t[x].rc = merge(t[x].rc, y);
            upd(x);
            return x;
        }
        else
        {
            psd(y);
            t[y].lc = merge(x, t[y].lc);
            upd(y);
            return y;
        }
    }

    inline void search(int id, int p, int k, long long v)
    {
        if (! p) return;
        psd(p);
        int rk = k + t[t[p].lc].siz + 1;
        if (t[p].val >= (t[p].lc ? t[t[p].lc].rval : v) + 1ll * rk * a[id])
        {
            P = rk, D = t[p].val;
            search(id, t[p].rc, rk, t[p].val);
        }
        else search(id, t[p].lc, k, v);
    }

    inline void insert(int pos, long long val)
    {
        int x = 0;
        split(root, pos, root, x);
        root = merge(root, New(val));
        root = merge(root, x);
    }

    inline void modify(int pos, long long a0, int d)
    {
        int x = 0;
        split(root, pos, root, x);
        addAll(x, a0, d);
        root = merge(root, x);
    }

    inline void dfs(int p)
    {
        ans = std::max(ans, t[p].val);
        psd(p);
        if (t[p].lc) dfs(t[p].lc);
        if (t[p].rc) dfs(t[p].rc);
    }
}

int main()
{

    read(n); srand(time(0));

    for (int i = 1; i <= n; ++ i)
    {
        read(a[i]); D = P = 0; FHQ::search(i, FHQ::root, 0, 0);
        FHQ::insert(P, D); FHQ::modify(P, P * a[i], a[i]);
        // 插入一个数 以及 将一个区间加上一个等差数列
    }

    FHQ::dfs(FHQ::root);

    std::cout << ans << std::endl;
    return 0;
}