CF573E 题解

· · 题解

思路

下文中称 \sum\limits_{i=1}^k i \cdot b_i 取到最大值的子序列 b 的位置集合为最优集合。

首先有一个显然的 dp：设 dp_{i,j} 表示前 i 个数中选了 j 个作为子序列的最大值。转移为：dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-1}+a_i \cdot j)。

还有一个贪心：每一次选择对当前序列贡献最大的点 i 加入子序列。显然，这个点的贡献为：V_i=a_i \cdot (x+1) + y。其中 x 表示 i 之前已经选了的位置个数，y 表示 i 之后已经选了的数之和。

引理：在这个贪心策略下，若 i<j,a_i>a_j，则 i 一定比 j 先选。

证明：假设引理不成立，当前是第一次违背引理的时候，当前选了 j。先考虑在 i 左边的已经选了的位置和在 j 右边的已经选了的位置对 V_i,V_j 的贡献。此时 i 和 j 的 x,y 均相等，又因为 a_i>a_j，所以 V_i>V_j。再考虑在 i,j 之间的位置。设这个位置为 wz，考虑它对 V_i,V_j 的贡献。它对 V_i 的贡献为 a_{wz}，对 V_j 的贡献为 a_j。因为 wz 比 i 先选，且之前的时候引理成立，所以 a_{wz} \ge a_i >a_j，因此它对 V_i 的贡献比对 V_j 的贡献要大。因此一定有 V_i>V_j，假设不成立，故引理得证。

接下来考虑证明贪心的正确性。假设贪心不成立，之前选的位置集合 A 是某一个最优集合的子集，设 A 的补集为 B（A\bigcup B 是一个最优集合）。当前选了贡献最大的位置 x，且 A\bigcup \{x\} 不是任意一个最优子序列位置的子集。显然 x \notin B。接下来使用调整法证明，即将 B 中的一个元素 y 删掉换成 x，证明调整后不劣于之前。考虑删掉 y 后再分别尝试添加 y 和 x，看新增的贡献是多少。新增的贡献可以拆成两部分，一部分是原有 A 集合的贡献，另一部分是 B 集合的贡献（比如，设 A 集合中在 x 前面的元素有 cnt_A 个，在 x 后面的数之和为 sum_A，cnt_B,sum_B 同理，则 x 的贡献为 a_x \cdot (cnt_A+cnt_B+1) + sum_A+sum_B=(a_x \cdot (cnt_A+1)+sum_A)+a_x \cdot cnt_B+sum_B）。因为 x 是对于 A 集合贡献最大的位置，所以 x 对于 A 集合的贡献比 y 大，即上面式子中的前半部分 x 比 y 大。现在只需要考虑后半部分的大小关系。

考虑分类讨论：

综上，x 对两个集合的贡献均比 y 大，因此调整后不劣于之前，假设不成立，故贪心是正确的。

考虑回到 dp 上来。有一个结论：对于 \forall 1 \le i \le n,\exists 1 \le k \le i 满足：

dp_{i,j} = \begin{cases}dp_{i-1,j} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ j <k \\ dp_{i-1,j-1}+a_i \cdot j \ \ \ \ \ \ \ \ \ \!j \ge k\end{cases}

这个结论可以用贪心的正确性来证明。考虑用贪心选择前 i 个数。k 实际上就是 i 在贪心中被选择的时刻，根据贪心的正确性，当前被选了，以后就一直会被选。

接下来考虑如何维护 dp 数组。首先 i 这一维没有用了。可以二分找到 k，之后就相当于在 k 这个位置插入一个 dp_{k-1}+a_i \cdot k，并在后面加上一个等差数列。可以使用平衡树来维护。

但是更好的方法是维护差分数组。这样只需要维护区间加的操作，而且细节特别少。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
mt19937 rnd(time(0));
int n; int a[500010];
int tot=0,root=0;
struct Fhq_tree
{
    int x,pri,siz;
    int lson,rson;
    int tag;
} tree[500010];
int get_new(int x)
{
    tree[++tot]={x,(int)rnd(),1,0,0,0};
    return tot;
}
void push_up(int now)
{
    tree[now].siz=tree[tree[now].lson].siz+tree[tree[now].rson].siz+1;
}
void push_down(int now)
{
    tree[tree[now].lson].x+=tree[now].tag,tree[tree[now].lson].tag+=tree[now].tag;
    tree[tree[now].rson].x+=tree[now].tag,tree[tree[now].rson].tag+=tree[now].tag;
    tree[now].tag=0;
}
void split(int now,int x,int siz,int &l,int &r)
{
    if(now==0) return l=r=0,void();
    push_down(now);
    int gtsiz=siz+tree[tree[now].lson].siz+1;
    if(tree[now].x>x*gtsiz) l=now,split(tree[now].rson,x,gtsiz,tree[now].rson,r);
    else r=now,split(tree[now].lson,x,siz,l,tree[now].lson);
    push_up(now);
}
int merge(int l,int r)
{
    if(l==0 || r==0) return l+r;
    push_down(l),push_down(r);
    if(tree[l].pri<tree[r].pri)
    {
        tree[l].rson=merge(tree[l].rson,r);
        return push_up(l),l;
    }
    else
    {
        tree[r].lson=merge(l,tree[r].lson);
        return push_up(r),r;
    }
}
int sum=0,ans=0;
void get_ans(int now)
{
    push_down(now);
    if(tree[now].lson!=0) get_ans(tree[now].lson);
    sum+=tree[now].x,ans=max(ans,sum);
    if(tree[now].rson!=0) get_ans(tree[now].rson);
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; ++i)
    {
        cin>>a[i];
        int l,r; split(root,a[i],0,l,r);
        tree[r].x+=a[i],tree[r].tag+=a[i];
        int k=tree[l].siz+1;
        root=merge(merge(l,get_new(a[i]*k)),r);
    }
    get_ans(root); cout<<ans;
    return 0;
}