CF631E Product Sum

· · 题解

前言

不知道为什么题解里的李超线段树都要分两种情况讨论，我觉得的大可不必，其实一遍就好了。

分析

设 ans_i 为 i 移动到 其他位置时获得的最大取值，sum_i 为 a_i 的前缀和。

对于 i < j ，ans_i=\max \{(j-i)\times a_i-(sum_j-sum_i)\}。

对于 i > j，ans_i=\max \{ sum_i-sum_j+[(i-(j+1))]\times a_i\}。

将两式化简会发现它们都是 ans_i=\max \{sum_i-sum_j+(j-i)\times a_i\} 。

发现好像没有单调性，并且二分的斜率优化我也不会，就去考虑李超线段树。

将与 j 相关的式子提出为 a_i\times j-sum_j，令 k=j，b=-sum_j，就可以开始打李超线段树了。

这里大多题解都用了两次 for 循环，正着反着都做了一遍，其实可以将线段先全部插入，再查询，就可以枚举一次了，详见代码，好像还是两次 for 循环。

code 
#include<bits/stdc++.h>
#define N 200005
#define T 2000005
#define int long long
#define ls u<<1
#define rs u<<1|1
#define INF 1e13
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int n,ans1,ans2;
int tree[T<<2];
int a[N],sum[N],k[N],b[N];
int calc(int x,int id){return x*k[id]+b[id];}
int Query(int u,int l,int r,int x){
    if(l==r) return calc(x,tree[u]);
    int mid=(l+r)>>1,res=calc(x,tree[u]);
    if(x<=mid) res=max(res,Query(ls,l,mid,x));
    else res=max(res,Query(rs,mid+1,r,x));
    return res;
}
void UpDate(int u,int l,int r,int id){
    if(!tree[u]) return void(tree[u]=id);
    if(calc(l,id)>calc(l,tree[u])&&calc(r,id)>calc(r,tree[u])) return void(tree[u]=id);
    else if(calc(l,id)<=calc(l,tree[u])&&calc(r,id)<=calc(r,tree[u])) return ;
    int mid=(l+r)>>1;
    if(k[id]>k[tree[u]]){
        if(calc(mid,id)>calc(mid,tree[u])) UpDate(ls,l,mid,tree[u]),tree[u]=id;
        else UpDate(rs,mid+1,r,id);
    }else{
        if(calc(mid,id)>calc(mid,tree[u])) UpDate(rs,mid+1,r,tree[u]),tree[u]=id;
        else UpDate(ls,l,mid,id);
    }
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i) a[i]=read(),sum[i]=sum[i-1]+a[i],ans2+=i*a[i];
    for(int i=1;i<=n;++i){
        k[i]=i,b[i]=-sum[i]; 
        UpDate(1,-1e6,1e6,i);
    }
    for(int i=1;i<=n;++i){
        int x=Query(1,-1e6,1e6,a[i]);
        ans1=max(ans1,x-i*a[i]+sum[i]);
    }
    printf("%lld\n",ans2+ans1);
    return 0;
}