P8067 [BalkanOI 2012] balls 题解

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