义乌中学暑假集训 2021.7.8 D

#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int&
#define gc getchar
#define pc putchar 
#define int LL
#define LL long long 
#define ull unsigned long long 
using namespace std;
Cn int N=1e5+10;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(ull x){x>=10&&(write(x/10),0),pc(x%10+'0');}
int n,a[N];
LL P,s1[N],s2[N],pre[N],suf[N];
ull Ans;
struct node{LL pre,suf,sum,ans;}T[N<<2];
I node operator + (Cn node& x,Cn node& y){return (node){max(x.pre,x.sum+y.pre),max(x.suf+y.sum,y.suf),x.sum+y.sum,max(max(x.ans,y.ans),x.suf+y.pre)};}
class SegmentTree{//线段树求最大子段和
    private:
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=n
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        #define PU(x) (T[x]=T[x<<1]+T[x<<11])
    public:
        I void B(PT){
            if(l==r) return void(T[x]=(node){a[l],a[l],a[l],a[l]});
            B(LT),B(RT),PU(x);
        }
        I node Q(CI L,CI R,PT){
            if(L<=l&&r<=R) return T[x];
            if(R<=mid) return Q(L,R,LT);if(L>mid) return Q(L,R,RT);
            return Q(L,R,LT)+Q(L,R,RT);
        }
}S;
struct Temp{LL s;int id;};
I bool cmp1(Cn Temp& x,Cn Temp& y){return x.s<y.s;}
I bool cmp2(Cn Temp& x,Cn Temp& y){return x.s>y.s;}
class TreeArray{//树状数组
    private:
        LL c[N];
        #define lowbit(x) (x&(-x))
    public:
        I void C(CI x){RI i;for(i=x;i<=n;i+=lowbit(i)) c[i]=0;}
        I void U(CI x,CI y){RI i;for(i=x;i<=n;i+=lowbit(i)) c[i]+=y;}
        I LL Q(CI x){RI i;LL S=0;for(i=x;i;i-=lowbit(i)) S+=c[i];return S;}
}A,B,C;
#define LW(x) (lower_bound(b+1,b+c2+1,x)-b)
I void Solve(CI l,CI r){
    if(l==r) return void(Ans+=a[l]);
    RI i,j,c1,c2;Solve(l,mid),Solve(mid+1,r);Temp t[r-l+5];LL b[r-l+5];
    for(suf[mid]=a[mid],i=mid-1;i>=l;i--) suf[i]=suf[i+1]+a[i];
    for(pre[mid+1]=a[mid+1],i=mid+2;i<=r;i++) pre[i]=pre[i-1]+a[i];//预处理出前/后缀和
    for(s1[mid]=S.Q(mid,mid).ans,i=mid-1;i>=l;i--) s1[i]=max(s1[i+1],S.Q(i,mid).ans);
    for(s2[mid+1]=S.Q(mid+1,mid+1).ans,i=mid+2;i<=r;i++) s2[i]=max(s2[i-1],S.Q(mid+1,i).ans);//预处理出前/后缀最大子段和
    for(i=mid-1;i>=l;i--) suf[i]=max(suf[i+1],suf[i]);for(i=mid+2;i<=r;i++) pre[i]=max(pre[i],pre[i-1]);//记得取 max
    for(c2=0,i=mid+1;i<=r;i++) b[++c2]=pre[i];for(i=l;i<=mid;i++) b[++c2]=s1[i]-suf[i];//第一种情况
    sort(b+1,b+c2+1),c2=unique(b+1,b+c2+1)-b-1;
    for(c1=0,i=mid+1;i<=r;i++) t[++c1]=(Temp){s2[i],i};
    for(sort(t+1,t+c1+1,cmp1),j=1,i=mid;i>=l;i--){
        W(j<=c1&&t[j].s<=s1[i]) A.U(LW(pre[t[j].id]),1),B.U(LW(pre[t[j].id]),pre[t[j].id]),j++;//二维偏序
        Ans+=A.Q(LW(s1[i]-suf[i]))*s1[i]+(A.Q(n)-A.Q(LW(s1[i]-suf[i])))*suf[i]+(B.Q(n)-B.Q(LW(s1[i]-suf[i])));
    }for(i=1;i<j;i++) A.C(LW(pre[t[i].id])),B.C(LW(pre[t[i].id]));//记得清空
    for(c2=0,i=mid+1;i<=r;i++) b[++c2]=s2[i]-pre[i];for(i=l;i<=mid;i++) b[++c2]=suf[i];//第二种情况
    sort(b+1,b+c2+1),c2=unique(b+1,b+c2+1)-b-1;
    for(sort(t+1,t+c1+1,cmp2),j=1,i=l;i<=mid;i++){
        W(j<=c1&&t[j].s>s1[i]) A.U(LW(s2[t[j].id]-pre[t[j].id]),1),B.U(LW(s2[t[j].id]-pre[t[j].id]),pre[t[j].id]),C.U(LW(s2[t[j].id]-pre[t[j].id]),s2[t[j].id]),j++;//二维偏序
        Ans+=A.Q(LW(suf[i]))*suf[i]+B.Q(LW(suf[i]))+(C.Q(n)-C.Q(LW(suf[i])));
    }for(i=1;i<j;i++) A.C(LW(s2[t[i].id]-pre[t[i].id])),B.C(LW(s2[t[i].id]-pre[t[i].id])),C.C(LW(s2[t[i].id]-pre[t[i].id]));//记得清空
}
signed main(){
    RI i;for(read(n),i=1;i<=n;i++) read(a[i]);
    return S.B(),Solve(1,n),write(Ans),pc('\n'),0;//建线段树（求区间最大子段和）、分治
}