算法1
将问题转化为维护前缀和问题,然后在线段树合并时分治
建立sum[]前缀和的线段树
线段树的域为区间最大ma,区间最小mi,当前区间最大子段和ans,区间加懒标记
修改一个值等价于先求出d=y-a[x], 将x~n的前缀和区间增加
对于合并时的两个区间,合并后的区间的答案由3部分组成,为 [l,mid].ans [mid+1,r].ans
和[mid+1,r].ma-[l,mid].mi 的最大值
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn =500000+5;
int n,m,a[maxn],sum[maxn];
struct Node{
int mi,ma,ans;
};
struct SeT{
int l,r,mi,ma,tag,ans;
}t[maxn *4];
#define ls p*2
#define rs p*2+1
#define mid (t[p].l+t[p].r)/2
void up(int p){
t[p].mi=min(t[ls].mi,t[rs].mi);
t[p].ma=max(t[ls].ma,t[rs].ma);
t[p].ans=max({t[ls].ans,t[rs].ans,t[rs].ma-t[ls].mi});
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r){
t[p].mi=t[p].ma=sum[l];
t[p].tag=0;
t[p].ans=-1e9;
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
up(p);
}
void spread(int p){
if(t[p].tag==0) return;
int d=t[p].tag;
t[p].tag=0;
t[ls].mi+=d;t[ls].ma+=d;t[ls].tag+=d;
t[rs].mi+=d;t[rs].ma+=d;t[rs].tag+=d;
}
void upd(int p,int l,int r,int d){
if(l<=t[p].l&&t[p].r<=r){
t[p].mi+=d;t[p].ma+=d;t[p].tag+=d;
return;
}
spread(p);
if(l<=mid) upd(ls,l,r,d);
if(r> mid) upd(rs,l,r,d);
up(p);
}
Node qry(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r)
return Node{t[p].mi,t[p].ma,t[p].ans};
spread(p);
int mi=1e9,ma=-1e9,ans=-1e9;
Node ta,tb;
if(l<=mid){
ta=qry(ls,l,r);
mi=min(mi,ta.mi);
ma=max(ma,ta.ma);
ans=max(ans,ta.ans);
}
if(r> mid){
tb=qry(rs,l,r);
mi=min(mi,tb.mi);
ma=max(ma,tb.ma);
ans=max(ans,tb.ans);
}
if(l<=mid&&r>mid) ans=max(ans,tb.ma-ta.mi);
return Node{mi,ma,ans};
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
build(1,0,n);
for(int i=1;i<=m;++i){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==1){
if(x>y) swap(x,y);
int ret=qry(1,x-1,y).ans;
printf("%d\n",ret);
}
else{
int d=y-a[x];
a[x]=y;
upd(1,x,n,d);
}
}
return 0;
}