义乌中学暑假集训 2021.7.8 D

2022-09-19 13:29:50 浏览数 (1)

义乌中学暑假集训 2021.7.8 D

Preface

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

果然好可爱

Description

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

1leq nleq 10^5,-10^9leq A_ileq 10^9

Solution

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

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

若 lleq i leq mid,mid 1leq jleq r，显然答案为 max{suf_i pre_j,sl_i,sr_j,}。

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

  1. sl_ige 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_j1 同理，这里不再赘述。

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

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

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

Code

代码语言：javascript复制
#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 '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;//建线段树（求区间最大子段和）、分治
}
bit max ode sort

0 人点赞