求动态区间最大子段和，并支持单点修改。 \(n\leq 5\times 10^5,m\leq10^5\)。
用线段树处理。对于每一个节点维护以下变量： \(ans\) 表示区间内最大子段和， \(sum\) 表示区间和， \(lmax\) 表示最大前缀和， \(rmax\) 表示最大后缀和，那么对于上传信息时进行以下操作：
\[sum[p]=sum[lson]+sum[rson] \]\[lmax[p]=max(lmax[lson],sum[lson]+lmax[rson]) \]\[rmax[p]=max(rmax[rson],sum[rson]+rmax[lson]) \]\[ans[p]=max(ans[lson],ans[rson],lmax[rson]+rmax[lson]) \]在询问时也做上述的合并操作即可。
#include<bits/stdc++.h>
using namespace std;
struct node{
int ans,a;
int lmax,rmax,sum;
int l,r;
};
struct ST{
node nd[2000005];
inline int ls(int p){
return p<<1;
}
inline int rs(int p){
return p<<1|1;
}
inline void push_up(int p){
nd[p].sum=nd[ls(p)].sum+nd[rs(p)].sum;
nd[p].lmax=max(nd[ls(p)].lmax,nd[ls(p)].sum+nd[rs(p)].lmax);
nd[p].rmax=max(nd[rs(p)].rmax,nd[rs(p)].sum+nd[ls(p)].rmax);
nd[p].ans=max(nd[ls(p)].ans,nd[rs(p)].ans);
nd[p].ans=max(nd[p].ans,nd[ls(p)].rmax+nd[rs(p)].lmax);
return;
}
void build(int l,int r,int p){
nd[p].l=l;
nd[p].r=r;
if(l==r){
nd[p].ans=nd[l].a;
nd[p].lmax=nd[l].a;
nd[p].rmax=nd[l].a;
nd[p].sum=nd[l].a;
return;
}
int mid=(l+r)>>1;
build(l,mid,ls(p));
build(mid+1,r,rs(p));
push_up(p);
return;
}
void updata(int p,int lr,int k){
if(nd[p].l==nd[p].r && nd[p].l==lr){
nd[p].ans=k;
nd[p].lmax=k;
nd[p].rmax=k;
nd[p].sum=k;
return;
}
int mid=(nd[p].l+nd[p].r)>>1;
if(mid>=lr)
updata(ls(p),lr,k);
if(mid<lr)
updata(rs(p),lr,k);
push_up(p);
return;
}
node query(int p,int ql,int qr){
int l=nd[p].l;
int r=nd[p].r;
if(ql<=l && r<=qr){
return nd[p];
}
node ret,gl,gr;
int mid=(l+r)>>1;
if(ql<=mid)
gl=query(ls(p),ql,qr);
else if(qr>mid)
return query(rs(p),ql,qr);
if(qr>mid)
gr=query(rs(p),ql,qr);
else
return gl;
ret.sum=gl.sum+gr.sum;
ret.lmax=max(gl.lmax,gl.sum+gr.lmax);
ret.rmax=max(gr.rmax,gr.sum+gl.rmax);
ret.ans=max(gl.ans,gr.ans);
ret.ans=max(ret.ans,gl.rmax+gr.lmax);
return ret;
}
}S;
int n,m;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&S.nd[i].a);
S.build(1,n,1);
while(m){
m--;
int k,a,b;
scanf("%d %d %d",&k,&a,&b);
switch(k){
case 1:{
if(a>b)
swap(a,b);
printf("%d\n",S.query(1,a,b).ans);
break;
}
case 2:{
S.updata(1,a,b);
break;
}
}
}
return 0;
}