RikkawithMaximumSegmentSum

Output a single line with a single integer, the answer. The answer can be very large, therefore, you are only required to output the answer modulo $2^{64}$ .
More formally, suppose the answer is x, you are required to find the smallest non-negative integer y satisfying $y = x + k \times 2^{64}$ for some integer k.

C++(clang++11) 解法, 执行用时: 45ms, 内存消耗: 5848K, 提交时间: 2020-11-24 19:43:36

#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
using namespace std;
typedef long long ll;
const ll inf=1e18;
const int N=1e5+10;
ll a[N],bl[N],br[N],cl[N],cr[N],sl[N],sr[N],ans;
ll* fd1(ll*l,ll*r,ll x){
	while(l<r){
		ll*m=l+((r-l)>>1);
		if(*m>x)r=m;else l=m+1;
	}
	return l;
}
ll* fd2(ll*l,ll*r,ll x){
	while(l>r){
		ll*m=l-((l-r)>>1);
		if(*m>x)r=m;else l=m-1;
	}
	return l;
}
void sol(int L,int R){
	if(L==R){
		ans+=a[L];return;
	}
	int m=(L+R)>>1;
	sol(L,m);sol(m+1,R);
	ll nw=0,sum=0;bl[m+1]=cl[m+1]=-inf;sl[m+1]=0;
	dep(i,m,L){
		bl[i]=max(nw+=a[i],bl[i+1]);
		cl[i]=max(sum+=a[i],cl[i+1]);
		if(nw<0)nw=0;
		sl[i]=sl[i+1]+cl[i];
	}
	nw=sum=0;br[m]=cr[m]=-inf;sr[m]=0;
	rep(i,m+1,R){
		br[i]=max(nw+=a[i],br[i-1]);
		cr[i]=max(sum+=a[i],cr[i-1]);
		if(nw<0)nw=0;
		sr[i]=sr[i-1]+cr[i];
	}
	int l=m,r=m+1;
	while(l>=L||r<=R){
		if(r>R||(l>=L&&bl[l]<br[r])){
			int x=fd1(cr+m+1,cr+r,bl[l]-cl[l])-cr;
			ans+=bl[l]*(x-m-1)+cl[l]*(r-x)+sr[r-1]-sr[x-1];
			--l;
		}else{
			int x=fd2(cl+m,cl+l,br[r]-cr[r])-cl;
			ans+=br[r]*(m-x)+cr[r]*(x-l)+sl[l+1]-sl[x+1];
			++r;
		}
	}
}
int main(){int n;
	scanf("%d",&n);
	rep(i,1,n)scanf("%lld",&a[i]);
	sol(1,n);printf("%llu\n",(unsigned long long)ans);
}

详情