[文章目录]
Description
路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。一开始，小白就根据公园的风景给每个公园打了分。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。 那么，就请你来帮小白选择公园吧。
线段树单点修改，区间查询最大连续子序列和，每个区间维护三个参数，Mx[]是区间最大连续子段和，Mxl[]是必包含最左端断点的最大连续子段和，Mxr[]是必包含最右端最大连续子段和。
然后在维护Mxl、Mxr的时候需要维护一个sum[]，所以总共4个参。通过是否跨mid进行比较就好了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 2001000
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
int n,m,sw,k2,k1;
int val[501000];
int sum[N],Mx[N],Mxl[N],Mxr[N];
void build(int pos,int l,int r)
{
if(l==r)
{
sum[pos]=Mx[pos]=Mxl[pos]=Mxr[pos]=val[l];
return ;
}
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
sum[pos]=sum[lson]+sum[rson];
Mx[pos]=max(Mxr[lson]+Mxl[rson],max(Mx[lson],Mx[rson]) );
Mxl[pos]=max(Mxl[lson],sum[lson]+Mxl[rson]);
Mxr[pos]=max(Mxr[rson],sum[rson]+Mxr[lson]);
}
int get_left(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
return Mxl[pos];
int mid=(l+r)>>1;
if(y<=mid)
return get_left(lson,l,mid,x,y);
if(x>mid)
return get_left(rson,mid+1,r,x,y);
return max(get_left(lson,l,mid,x,y),sum[lson]+get_left(rson,mid+1,r,x,y) );
}
int get_right(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
return Mxr[pos];
int mid=(l+r)>>1;
if(y<=mid)
return get_right(lson,l,mid,x,y);
if(x>mid)
return get_right(rson,mid+1,r,x,y);
return max(get_right(rson,mid+1,r,x,y),sum[rson]+get_right(lson,l,mid,x,y) );
}
int query(int pos,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
return Mx[pos];
int mid=(l+r)>>1;
if(y<=mid)
return query(lson,l,mid,x,y);
else if(x>mid)
return query(rson,mid+1,r,x,y);
else
return max( query(lson,l,mid,x,y),max(query(rson,mid+1,r,x,y),get_right(lson,l,mid,x,y)+get_left(rson,mid+1,r,x,y) ) );
}
void updata(int pos,int l,int r,int x,int y)
{
if(l==x&&r==x)
{
sum[pos]=Mx[pos]=Mxl[pos]=Mxr[pos]=y;
return ;
}
int mid=(l+r)>>1;
if(x<=mid)
updata(lson,l,mid,x,y);
else if(x>mid)
updata(rson,mid+1,r,x,y);
sum[pos]=sum[lson]+sum[rson];
Mx[pos]=max(Mxr[lson]+Mxl[rson],max(Mx[lson],Mx[rson]) );
Mxl[pos]=max(Mxl[lson],sum[lson]+Mxl[rson]);
Mxr[pos]=max(Mxr[rson],sum[rson]+Mxr[lson]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&val[i]);
build(1,1,n);
while(m--)
{
scanf("%d%d%d",&sw,&k1,&k2);
if(sw==1)
{
if(k1>k2)
swap(k1,k2);
printf("%d\n",query(1,1,n,k1,k2));
}
else
updata(1,1,n,k1,k2);
}
return 0;
}