0.前言
水题解使我快乐~
1.题目概述
动态维护最大子段和。
2.题解
首先一看到修改和区间查询→线段树です!
但是这个题需要维护的东西比普通的线段树多亿一点,我们来一步步讲。
首先,题目里都说了查询最大子段和,我们用一个mx
代表。
其次,如何更新mx
?
容易发现,一个区间的最大子段和总共只有三种情况:在左边取、在右边取和左右各取一部分。
前两种好说,但第三种需要多维护一些东西。
易知,答案区间一定占了左边的右半部分和右边的左半部分(还不是很绕)
所以把区间内最大前缀和与最大后缀和统计出来即可。
3.代码
#define N 500010
int n,m,num[N];
struct Node {
int l,r,wei,mx,lmx,rmx;
Node(){l=r=wei=mx=lmx=rmx=0;}
Node(int _l,int _r,int _w,int _m,int _lm,int _rm){
l=_l,r=_r,wei=_w,mx=_m,lmx=_lm,rmx=_rm;
}
}tr[N<<2];
inline void Pushup(int k){
tr[k].wei=tr[ls].wei+tr[rs].wei;
tr[k].lmx=max(tr[ls].lmx,tr[ls].wei+tr[rs].lmx);
tr[k].rmx=max(tr[ls].rmx+tr[rs].wei,tr[rs].rmx);
tr[k].mx=max(max(tr[ls].mx,tr[rs].mx),tr[ls].rmx+tr[rs].lmx);
}
void Build(int k,int l,int r){
tr[k].l=l,tr[k].r=r;
if(l==r){
tr[k].wei=tr[k].lmx=tr[k].rmx=tr[k].mx=num[l];
return;
}
Build(ls,l,nmid);
Build(rs,nmid+1,r);
Pushup(k);
}
void Modify(int k,int pos,int val){
if(tr[k].l==tr[k].r){
tr[k].wei=tr[k].lmx=tr[k].rmx=tr[k].mx=val;
return;
}
if(pos<=tmid)Modify(ls,pos,val);
else Modify(rs,pos,val);
Pushup(k);
}
Node Query(int k,int l,int r){
if(l<=tr[k].l&&tr[k].r<=r)return tr[k];
if(r<=tmid)return Query(ls,l,r);
else if(tmid<l)return Query(rs,l,r);
else {
Node ll=Query(ls,l,r),rr=Query(rs,l,r),res;
res=Node(l,r,ll.wei+rr.wei,0,max(ll.lmx,ll.wei+rr.lmx),max(rr.rmx,rr.wei+ll.rmx));
res.mx=max(max(ll.mx,rr.mx),ll.rmx+rr.lmx);
return res;
}
}
int main(){
Read(n),Read(m);
for(rg int i=1;i<=n;i++)Read(num[i]);
Build(1,1,n);
while(m--){
int k,ap,bs;
Read(k),Read(ap),Read(bs);
if(k==1){
if(ap>bs)swap(ap,bs);
Node res=Query(1,ap,bs);
cout<<res.mx<<endl;
}else Modify(1,ap,bs);
}
return 0;
}
lmx,rmx
即为前缀和与后缀和。
4.完结撒花
总觉得这题讲过做过来着……déjà vu?