P8067 [BalkanOI 2012] balls 题解

· · 题解

来一发李超线段树的题解。

我们设 s_i 表示 a 的前缀和数组，显然可以得到两种画法的式子

S1=a_i(i-j)+s_n-s_i+s_j \\S2=a_j(i-j+1)+s_n-s_i+s_{j-1}

直接用李超线段树维护即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF=1e18;
const int nn=1e10;
const int N=300005;
struct line{
    int k,b;
    int calc(int x){
        return k*x+b;
    }
};
struct segtree{
    struct tree{
        line sum;
        int ls,rs;
    }tr[N*128];
    int cnt;
    void upd(int &p,int l,int r,line v){
        if(!p){
            p=++cnt;
            tr[p].sum=v;
            return ;
        }
        if(tr[p].sum.calc(l)<=v.calc(l)&&tr[p].sum.calc(r)<=v.calc(r)){
            tr[p].sum=v;
            return ;
        }
        if(tr[p].sum.calc(l)>=v.calc(l)&&tr[p].sum.calc(r)>=v.calc(r))return ;
        int mid=(l+r)>>1;
        upd(tr[p].ls,l,mid,v);
        upd(tr[p].rs,mid+1,r,v);
    }
    int qry(int p,int l,int r,int x){
        if(!p)return -INF;
        if(l==r)return tr[p].sum.calc(x);
        int mid=(l+r)>>1,ans=tr[p].sum.calc(x);
        if(mid>=x)return max(ans,qry(tr[p].ls,l,mid,x));
        else return max(ans,qry(tr[p].rs,mid+1,r,x));
    }
}st;
int a[N],sum[N];
signed main(){
//    freopen("sb.in","r",stdin);
//    freopen("sb.out","w",stdout);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i];
    int ans=-INF,rt=0;
    st.upd(rt,-nn,nn,{0,0});
    st.upd(rt,-nn,nn,{-1,sum[1]});
    for(int i=2;i<=n;i++){
        ans=max(ans,st.qry(rt,-nn,nn,a[i])+sum[n]-sum[i]+a[i]*i);
        st.upd(rt,-nn,nn,{-i,sum[i]});
    }
    cout<<ans<<"\n";
    ans=-INF,rt=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,st.qry(rt,-nn,nn,i)+sum[n]-sum[i]);
        st.upd(rt,-nn,nn,{a[i],-a[i]*i+a[i]+sum[i-1]});
    }
    cout<<ans<<"\n";
}