注:本人还要上学，可能无法及时看到回复
by cbkxx @ 2024-02-27 22:37:55
@[cbkxx](/user/705343) 改完了，死因：pushup最后一句应该是左儿子包含右端点的最大子段和+右儿子包含左端点的最大子段和。
100pts代码：
```cpp
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
int n,m,a[500005];
struct node{
int s1,s2,s3,s4;
}t[2000005];
void push_up(int x){
t[x].s1=t[x*2].s1+t[x*2+1].s1;
t[x].s2=max(t[x*2].s2,t[x*2].s1+t[x*2+1].s2);
t[x].s3=max(t[x*2+1].s3,t[x*2+1].s1+t[x*2].s3);
t[x].s4=max(max(t[x*2].s4,t[x*2+1].s4),t[x*2].s3+t[x*2+1].s2);
}
void build(int l,int r,int x){
if(l==r){
t[x].s1=t[x].s2=t[x].s3=t[x].s4=a[l];
return;
}
build(l,mid,x*2);
build(mid+1,r,x*2+1);
push_up(x);
}
node ask(int L,int R,int l,int r,int x){
if(l>=L&&r<=R)return t[x];
if(R<=mid)return ask(L,R,l,mid,x*2);
if(L>mid)return ask(L,R,mid+1,r,x*2+1);
node ans,a1=ask(L,R,l,mid,x*2),b1=ask(L,R,mid+1,r,x*2+1);
ans.s1=a1.s1+b1.s1;
ans.s2=max(a1.s2,a1.s1+b1.s2);
ans.s3=max(b1.s3,b1.s1+a1.s3);
ans.s4=max(max(a1.s4,b1.s4),a1.s3+b1.s2);
return ans;
}
void add(int d,int e,int l,int r,int x){
if(l==r){
t[x].s1=t[x].s2=t[x].s3=t[x].s4=e;
return;
}
if(d<=mid)add(d,e,l,mid,x*2);
else add(d,e,mid+1,r,x*2+1);
push_up(x);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)scanf("%d",a+i);
build(1,n,1);
while(m--){
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if(k==1){
if(x>y)swap(x,y);
printf("%d\n",ask(x,y,1,n,1).s4);
}else{
add(x,y,1,n,1);
}
}
return 0;
}
```
by XHY20180718 @ 2024-02-28 07:41:45
@[XHY20180718](/user/399475) 谢谢，已关
by cbkxx @ 2024-02-28 16:17:29