义乌中学暑假集训 2021.7.8 D

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

#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<<1|1,mid+1,r
        #define PU(x) (T[x]=T[x<<1]+T[x<<1|1])
    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;//建线段树(求区间最大子段和)、分治
}

评论

  1. noip
    Windows Firefox 89.0
    2周前
    2021-7-11 12:57:45

    stO yzx Orz

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇