最大子段和解题记录

## 前记

SPOJ - GSS系列 on : 2022.10.27 总用时 $ 4 $ 天

P5073 on : 2023.02.15 总用时 $ 1 $ 天

P5693 on : 2023.02.15 总用时 $ 1 $ 天

P4118 on : 2023.07.29 总用时 $ 1 $ 天 ( 拉了P5073的代码 )

## Part 1 SPOJ - GSS 系列 Easy Version

### - GSS1 不带修的区间最大子段和

考虑维护 $  lmax,rmax,sum,maxsum $ 四个部分。

$lmax $ 用于维护区间内最大前缀和。

$rmax $ 用于维护区间内最大后缀和。

$sum $ 用于维护区间和。

$maxsum $ 用于维护区间内最大子段和。

容易发现该结构可以支持快速合并与查询。

选择一种你喜欢的数据结构维护该分治结构即可。

### - GSS3 单点修的区间最大子段和

直接套用 $GSS1$ 的做法即可。

### - GSS5 有端点限制的区间最大子段和

直接套用 $GSS1$ 的做法再加点分讨即可。

- $ x1 \leq y1 \leq x2 \leq y2 $ 相当于
    
	$ \max_{i=x1}^{y1} \{ \sum_{j=i}^{y1} a_j \}+ \sum_{i=y1+1} ^ {x2-1}ai + \max_{i=x2}^{y2} \{ \sum_{j=x2}^{i} a_j \}$
    
 - $ x1 \leq x2 \leq y1 \leq y2 $

$Max \{ \max_{i=x1}^{x2}\{\sum_{j=i}^{x2}a_j \} + \max_{i=x2+1}^{y2} \{\sum_{j=x2+1}^{i}a_j \} , $
    
	$ \ \ \ \ \ \ \ \ \ \ \ \max_{i=x1}^{x2}\{\sum_{j=i}^{x2}a_j \} + \max_{i=x2+1}^{y2} \{\sum_{j=x2+1}^{i}a_j \} , $ 
    
   $ \ \ \ \ \ \ \ \ \ \ \ \max_{i=y1}^{x2}\max_{j=i}^{x2}\sum_{k=i}^j a_k\} $
   
### - GSS6 带插入删除的区间最大子段和

直接套用 $GSS1$ 的做法即可。

### - GSS7 树上的区间最大子段和

先树剖然后套用 $GSS1$ 的做法即可。

修改只需要添加 $lazytag$ 即可

## Part 2 P5693 & P5073 Medium Version

### P5693 区间加正数的最大子段和

该题在 $ \textcolor{black}E\textcolor{red}{ntropyIncreaser} $ 的集训队论文《浅谈函数最值的动态维护》中 用 Kinetic Tournament 树（KTT）以 $ O((n+q)log^3n) $ 的复杂度解决，其实际运行效率较快，类似于 $ \Theta((n+q)log^2n) $。

首先我们有一个事实, 一个长度为 $n$ 的区间的 $ lmax,rmax,maxsum $ 和在整体加一个数时可以构成一个直线数量为 $ O(n) $ 的下凸壳。

于是可以通过维护一颗线段树，记录下一次切换直线还需要添加的数的大小，如果该值变为负，就暴力重构子树，可以用势能法证明时间复杂度的正确性。

### P5073 全局加正数的最大子段和

首先可以通过离线把操作变为只加正数，但是直接上 KTT 的话复杂度达到了 $ O(nlog^2n) $，这在 Ynoi 是显然过不去的。

前文说到，一个区间的 $ lmax,rmax,maxsum $是关于加的数的下凸壳，而 $sum$ 则是一条直线。所以我们可以考虑直接维护凸包，对于 $maxsum$的维护需要用到闵可夫斯基和，不会的可以通过 [[JSOI2018] 战争](https://www.luogu.com.cn/problem/P4557)了解一下。

在维护出下凸壳后，我们可以简单地通过维护一个指针找到此时对应的直线从而达到在凸包上均摊 $O(1)$ 的查询。

但此时我们发现空间复杂度达到了 $ O(nlogn) $，这是简单的，只需要及时把已用完的凸包空间释放即可达到 $ O(n)$ 。

## Part 3 P4118 Hard Version

~~臭名昭著的研究珂学的最佳方式~~

看见 Ynoi 和 $n,m \leq 10^5$ ，果断分块

设块长为 $B$，可以发现，每次操作变为了 $O(nm/B)$次整块操作和 $O(m)$次散块操作。

对于整块的操作，可以直接套用 $P5073$ 的做法，由于只有整块加和整块求，可以实现 $ O(BlogB) - O(1)$的复杂度。

对于散块的询问可以直接暴力求。

对于散块的修改可以直接在线段树上找到对应区间维护 $lazytag$ ，由于加操作可看做凸包上加直线，故可以 $O($凸包大小$)$ 维护，于是复杂度降到了 $O(B)$

对于整块询问的排序，使用松式基排可以达到 $O(n)$

取 $B = \sqrt n$ ，时间复杂度为 $O(n \sqrt n)$

接下来就是卡常了。(我也不知道为什么我跑得那么慢，但是最大点不超过900ms)

- I/O 优化
- 封装后不仅容易调，还可能跑的更快
- ...

接下来给出抠掉快读的代码，方便各位调试

```cpp
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define ldb long double
using namespace std;
/*快读*/
int plen,ptop,pstk[40];
char out[1<<20];
#define pc(x) out[plen++]=(x)
#define flush() fwrite(out,1,plen,stdout),plen=0
template<class T=int>inline void write(T x){
	if(plen>=1000000)flush();
	if(!x)return pc('0'),void();
	if(x<0)pc('-'),x=-x;
	for(;x;x/=10)pstk[++ptop]=x%10;
	while(ptop)pc(pstk[ptop--]+'0');
}
inline void write(const char*s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
inline void write(char*const s){
	if(plen>=1000000)flush();
	for(int i=0;(*(s+i))!='\000';pc(*(s+(i++))));
}
typedef pair<LL,int> PII;
const int N=1e5+5,B=317,M=1285;
const LL INF=4e9,Inf=2e18+7;
int n,m,q;
int c1[256],c2[256];
int O[N],L[N],R[N],X[N];
LL a[N],tag[M];
struct node{
    LL l,r,s,m;
    node(){l=r=s=m=0;}
    node(LL x){s=x,l=r=m=max(x,0LL);}
    node(LL _l,LL _r,LL _s,LL _m){l=_l,r=_r,s=_s,m=_m;}
}ans[N];
inline node operator+(const node &i,const node &j){
    return node(max(i.l,i.s+j.l),max(j.r,j.s+i.r),\
            i.s+j.s,max(max(i.m,j.m),i.r+j.l));
}
struct qnode{int id;LL x;}Q[N],F[N];
inline bool cmp(const qnode &i,const qnode &j){
    return i.x<j.x||(i.x==j.x&&i.id<j.id);
}
struct pii{LL x,y;}pA[10][N],pB[10][N],pC[10][N];
pii pool1[N],pool2[N],pool3[N];
inline pii operator+(const pii& x,const pii& y){
    return (pii){x.x+y.x,x.y+y.y};
}
inline pii operator-(const pii& x,const pii& y){
    return (pii){x.x-y.x,x.y-y.y};
}
inline bool operator<=(const pii& x,const pii& y){
    return x.y*y.x<=x.x*y.y;
}
struct hull{
    pii *st;
    int top,cur;
    inline void copy(const hull &o){
        top=o.top,cur=o.cur;
        for(int i=1;i<=top;++i)st[i]=o.st[i];
    }
    inline void push(const pii &o){
        for(;top>1&&o-st[top-1]<=o-st[top];--top);
        st[++top]=o;
    }
    inline void mul(LL z){
        for(int i=1;i<=top;++i)st[i].y+=z*st[i].x;
    }
    inline LL qry(LL z){
        while(cur<top&&st[cur+1].y+z*st[cur+1].x>st[cur].y+z*st[cur].x)++cur;
        return st[cur].y+z*st[cur].x;
    }
    hull operator+(pii x){
        hull res;
        res.st=pool3,res.top=top;
        for(int i=1;i<=top;++i)res.st[i]=st[i]+x;
        return res;
    }
    hull operator+(hull x){
        hull z;
        z.st=pool2,z.top=1;
        z.st[1]=st[1]+x.st[1];
        int i=1,j=1;
        for(;i<top&&j<x.top;++z.top){
            pii f=st[i+1]-st[i],g=x.st[j+1]-x.st[j];
            if(f<=g)z.st[z.top+1]=z.st[z.top]+g,++j;
            else z.st[z.top+1]=z.st[z.top]+f,++i;
        }
        for(;i<top;++i,++z.top)z.st[z.top+1]=z.st[z.top]+st[i+1]-st[i];
        for(;j<x.top;++j,++z.top)z.st[z.top+1]=z.st[z.top]+x.st[j+1]-x.st[j];
        return z;
    }
};
hull merge(hull x,hull y){
    hull z;
    z.st=pool1,z.top=0,z.cur=1;
    int i=1,j=1;
    for(;i<=x.top&&j<=y.top;)
        if(x.st[i].x==y.st[j].x)
            z.push((pii){x.st[i].x,max(x.st[i].y,y.st[j].y)}),
            ++i,++j;
        else if(x.st[i].x<y.st[j].x)z.push(x.st[i++]);
        else z.push(y.st[j++]);
    while(i<=x.top)z.push(x.st[i++]);
    while(j<=y.top)z.push(y.st[j++]);
    return z;
}
struct tnode{LL sz;hull A,B,C;}T[M];
void build(int p,int l,int r,int d){
    tag[p]=0;
    if(l==r){
        hull A,B,C;
        A.st=pA[d]+(l<<1),B.st=pB[d]+(l<<1),C.st=pC[d]+(l<<1);
        A.st[1]=B.st[1]=C.st[1]=(pii){0,0};
        A.st[2]=B.st[2]=C.st[2]=(pii){1,a[l]};
        A.cur=B.cur=C.cur=1,A.top=B.top=C.top=2;
        T[p]=(tnode){a[l],A,B,C};
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid,d+1),build(p<<1|1,mid+1,r,d+1);
    tnode &L=T[p<<1],&R=T[p<<1|1];
    hull &A=T[p].A,&B=T[p].B,&C=T[p].C;
    A.st=pA[d]+(l<<1),B.st=pB[d]+(l<<1),C.st=pC[d]+(l<<1);
    C.copy(merge(L.C,R.C)),C.copy(merge(C,L.B+R.A));
    A.copy(merge(L.A,R.A+(pii){mid-l+1,L.sz}));
    B.copy(merge(R.B,L.B+(pii){r-mid,R.sz}));
    T[p].sz=L.sz+R.sz;
}
void upd(int p,int l,int r,int d,int x,int y,LL z){
    if(x<=l&&r<=y){
        tag[p]+=z,T[p].sz+=(r-l+1)*z;
        T[p].A.mul(z),T[p].B.mul(z),T[p].C.mul(z);
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)upd(p<<1,l,mid,d+1,x,y,z);
    if(y>mid)upd(p<<1|1,mid+1,r,d+1,x,y,z);
    tnode &L=T[p<<1],&R=T[p<<1|1];
    hull &A=T[p].A,&B=T[p].B,&C=T[p].C;
    C.copy(merge(L.C,R.C)),C.copy(merge(C,L.B+R.A));
    A.copy(merge(L.A,R.A+(pii){mid-l+1,L.sz}));
    B.copy(merge(R.B,L.B+(pii){r-mid,R.sz}));
    if(tag[p])A.mul(tag[p]),B.mul(tag[p]),C.mul(tag[p]);
    T[p].sz=L.sz+R.sz+tag[p]*(r-l+1);
}
inline void sort(int n){
    if(n<=1000)return sort(Q+1,Q+n+1,cmp),void();
    memset(c1,0,sizeof(c1)),memset(c2,0,sizeof(c2));
    for(int i=1;i<=n;++i)++c1[Q[i].x&255],++c2[(Q[i].x>>8)&255];
    for(int i=1;i<256;++i)c1[i]+=c1[i-1],c2[i]+=c2[i-1];
    for(int i=n;i>=1;--i)F[c1[Q[i].x&255]--]=Q[i];
    for(int i=n;i>=1;--i)Q[c2[(F[i].x>>8)&255]--]=F[i];
    memset(c1,0,sizeof(c1)),memset(c2,0,sizeof(c2));
    for(int i=1;i<=n;++i)++c1[(Q[i].x>>16)&255],++c2[Q[i].x>>24];
    for(int i=1;i<256;++i)c1[i]+=c1[i-1],c2[i]+=c2[i-1];
    for(int i=n;i>=1;--i)F[c1[(Q[i].x>>16)&255]--]=Q[i];
    for(int i=n;i>=1;--i)Q[c2[F[i].x>>24]--]=F[i];
}
inline node qry(LL s,int len){
    return node(T[1].A.qry(s),T[1].B.qry(s),T[1].sz+s*len,T[1].C.qry(s));
}
signed main(){
    n=read(),q=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=q;++i){
        O[i]=read(),L[i]=read(),R[i]=read();
        if(O[i]&1)X[i]=read();
    }
    int bn=(n-1)/B+1;
    for(int i=1;i<=bn;++i){
        int l=(i-1)*B+1,r=min(n,i*B),len=r-l+1,qc=0,mxq=0;
        LL s=0;
        build(1,l,r,0);
        for(int j=1;j<=q;++j)
            if(L[j]<=l&&r<=R[j])mxq=j;
        for(int j=1;j<=q;++j){
            if(R[j]<l||L[j]>r)continue;
            if(L[j]<=l&&r<=R[j]){
                if(O[j]==1)s+=X[j];
                else Q[++qc]=(qnode){j,s+INF};
            }
            else{
                sort(qc);
                for(int t=1;t<=qc;++t)
                    ans[Q[t].id]=ans[Q[t].id]+qry(Q[t].x-INF,len);
                qc=0;
                if(s){
                    for(int t=l;t<=r;++t)a[t]+=s;
                    upd(1,l,r,0,l,r,s),s=0;
                }
                int pl=max(l,L[j]),pr=min(r,R[j]);
                if(O[j]==1){
                    for(int t=pl;t<=pr;++t)a[t]+=X[j];
                    if(j<=mxq)upd(1,l,r,0,pl,pr,X[j]);
                }
                else for(int t=pl;t<=pr;++t)ans[j]=ans[j]+node(a[t]);
                T[1].A.cur=T[1].B.cur=T[1].C.cur=1;
            }
        }
        sort(qc);
        for(int t=1;t<=qc;++t)
            ans[Q[t].id]=ans[Q[t].id]+qry(Q[t].x-INF,len);
    }
    for(int i=1;i<=q;++i)
        if(O[i]==2)write<LL>(ans[i].m),pc('\n');
	return flush(),0;
}
/*

*/
```

## Part 4 最大子段和的其他解法

+ 贪心解法

记录两个值 $ans,sum$ 从前向后扫描序列
   
   初始时有 $ sum=0, ans=- \inf$（若最大子段和可以为空，则 $ans=0$ ）
   
	$ sum <- sum +a_i $ ，$ ans <- \max(ans,sum)$，$ sum<- \max(sum,0) $。
    
   $ans$ 即为所求。

+ 动态DP解法

只需要把贪心解法描述成矩阵形式即可。

正在渲染内容...