题面：小白逛公园
题解：
对于线段树的每个节点除了普通线段树该维护的东西以外，额外维护lsum（与左端点相连的最大连续区间和）、rsum（同理）和sum……就行了
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=+,maxm=+,inf=<<;
int N,M,K,P,S,ans,flag;
struct Tree{int lsum,rsum,l,r,mx,sum;}t[maxn<<],now;
inline void Pushup(int x){
int ls=x<<,rs=ls|;
t[x].sum=t[ls].sum+t[rs].sum;
t[x].lsum=max(t[ls].lsum,t[ls].sum+t[rs].lsum);
t[x].rsum=max(t[rs].rsum,t[rs].sum+t[ls].rsum);
t[x].mx=max(t[ls].mx,t[rs].mx);
t[x].mx=max(t[x].mx,t[ls].rsum+t[rs].lsum);
return;
}
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r){
t[x].sum=t[x].lsum=t[x].rsum=t[x].mx=rd();
return;
}
Build(x<<,l,mid);Build(x<<|,mid+,r);
Pushup(x);
return;
}
inline void Update(int x,int p,int s){
int l=t[x].l,r=t[x].r,mid=(l+r)>>,ls=x<<,rs=ls|;
if(l==r&&l==p){
t[x].sum=t[x].lsum=t[x].rsum=t[x].mx=s;
return;
}
if(p<=mid)Update(ls,p,s);else Update(rs,p,s);
Pushup(x);
return;
}
inline void Query(int x,int ql,int qr){
int l=t[x].l,r=t[x].r,mid=(l+r)>>,ls=x<<,rs=ls|;
if(ql<=l&&r<=qr){
if(flag==-){
flag=;
now.lsum=t[x].lsum;now.rsum=t[x].rsum;
now.mx=t[x].mx;now.sum=t[x].sum;
}
else{
int sum,lsum,rsum,mx;
sum=now.sum+t[x].sum;
lsum=max(now.lsum,now.sum+t[x].lsum);
rsum=max(t[x].rsum,now.rsum+t[x].sum);
mx=max(now.mx,t[x].mx);
mx=max(mx,now.rsum+t[x].lsum);
now.sum=sum;now.lsum=lsum;now.rsum=rsum;now.mx=mx;
}
return;
}
if(ql<=mid)Query(ls,ql,qr);if(qr>mid)Query(rs,ql,qr);
return;
}
int main(){
N=rd();M=rd();
Build(,,N);
while(M--){
K=rd();P=rd();S=rd();
if(K==){
if(P>S)swap(P,S);
flag=-;
Query(,P,S);
ans=now.mx;
printf("%d\n",ans);
}
else Update(,P,S);
}
return ;
}
By:AlenaNuna