题解 SP1716 【GSS3 - Can you answer these queries III】
流逝丶
2019-09-21 14:41:28
维护最大子段和嘛，要维护这东西我们需要四个东西，
区间和sum，从最左端起的最大连续和ls，从最右端起最大的连续和rs，区间内最
大的连续和mx。
为什么是这四个呢？
我们区间合并的时候，大区间的mx，可能由左或右区间mx更新过
来，可能是左区间rs和右区间ls更新。
对于sum，我们为什么需要？
因为更新新区间的ls可能是原左区间的ls或左区间的sum和右区间的ls
同理更新新区间的rs可能是原右区间的rs或右区间的sum和左区间的rs
对于一个叶子结点，它的sum=ls=rs=mx=val
知道怎么维护了，就开始想change，因为是单点修改，所以直接修改叶子结点，
ask的话我们对于区间分开的话要分开找最后返回。
### [双倍经验](https://www.luogu.org/problem/P4513)
### [升级版](https://www.luogu.org/problem/P2572)
提供一种结构体重载的写法，省了不少码量
```cpp
#include<iostream>
#include<cstdio>
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
#define lso k<<1
#define rso k<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int N=500000;
struct data{
int ls,rs,mx,sum;
}tr[N<<2];
int n,m;
int a[N+5];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
data operator +(const data &a,const data &b){
data c;
c.ls=max(a.ls,a.sum+b.ls);
c.rs=max(b.rs,b.sum+a.rs);
c.sum=a.sum+b.sum;
c.mx=max(a.mx,max(b.mx,a.rs+b.ls));
return c;
}
void update(int k){
tr[k]=tr[lso]+tr[rso];
}
void change(int k,int l,int r,int pos,int val){
if(l==r){
tr[k].ls=tr[k].rs=tr[k].mx=tr[k].sum=val;
return;
}
if(pos<=mid)change(lson,pos,val);
else change(rson,pos,val);
update(k);
}
data ask(int k,int l,int r,int x,int y){
if(l==x&&r==y)return tr[k];
if(y<=mid)return ask(lson,x,y);
else if(x>mid)return ask(rson,x,y);
else {
data temp1=ask(lson,x,mid);
data temp2=ask(rson,mid+1,y);
return temp1+temp2;
}
}
void build(int k,int l,int r){
if(l==r){
tr[k].sum=tr[k].ls=tr[k].rs=tr[k].mx=a[l];
return;
}
build(lson);build(rson);
update(k);
}
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i]=read();
m=read();
build(1,1,n);
for(int i=1;i<=m;i++){
int t,x,y;
t=read(),x=read(),y=read();
if(t==1){
if(x>y)swap(x,y);
printf("%d\n",ask(1,1,n,x,y).mx);
}
if(t==0)
change(1,1,n,x,y);
}
return 0;
}
```