义乌中学暑假集训 2021.7.8 D

(Updated: )
oi
, , ,

Preface

见到 lxl 小姐姐真的好好好兴奋！！！

果然好可爱

Description

给定一个序列 $A$，求所有 $1\leq l \leq r \leq n$ 的区间 $[l,r]$ 的最大子段和的和，答案对 $2^{64}$ 取模。

$1\leq n\leq 10^5,-10^9\leq A_i\leq 10^9$

Solution

考虑分治，求跨越左右两个区间的贡献。

维护一下区间的 $suf$ 表示后缀和，$pre$ 表示前缀和，$sl$ 表示左区间的后缀最大子段和，$sr$ 表示右区间的前缀最大子段和。

若 $l\leq i \leq mid,mid+1\leq j\leq r$，显然答案为 $\max{suf_i+pre_j,sl_i,sr_j,}$。

然而三个数的最大值难以维护，所以考虑拆成两种情况。

  1. $sl_i\ge sr_j$ 所以答案就变成了 $\max{suf_i+pre_j,sl_i}$，然后先减去 $suf_i$，再加回去，可以得到 $\max{pre_j,sl_i-suf_i}+suf_i$，这样 $j$ 就独自只在一个候选 $\max$ 之中了，这样比较好维护。 那么再继续拆分，分两类讨论，直接根据以上条件二维偏序即可
  2. $sl_i<sr_j$ 和情况 $1$ 同理，这里不再赘述。

然后二维偏序可以直接用 sort + BIT 进行，博主是开了 $3$ 个树状数组。

最后喷一下 lxl，明明 $pre,suf,sl,sr$ 全是有单调性的，直接二分就好了（害我写了二维偏序跑得比二分慢了 $8s$）

放张图纪念一下我的推狮子：

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;//建线段树（求区间最大子段和）、分治
}