双倍经验: https://www.luogu.org/problem/SP1716
复习一下线段树, 老是写挂…
这道题是一种常见线段树处理连续子段问题的做法. 每个节点维护区间最大子段和, 从左端点开始的最大子段和, 从右端点开始的最大子段和, 区间和. 这样合并两个节点时就可以考虑以下几种情况:
对于合并后的从左端点开始的最大子段和有: 保持原样; 子段跨越mid(左儿子区间和+右儿子左端).
合并后的右端点开始的最大子段和同理.
对于合并后的区间最大子段和有: 子段全在左儿子; 全在右儿子; 子段跨越mid(左儿子右端+右儿子左端).
展开代码
#include<cstdio>
#define in inline
#define re register
#define int long long
#define lc p<<1
#define rc p<<1|1
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
const int size=500005,inf=3223372036854775807;//inf必须取2^63的一半以下, 否则相加时会爆
int n,m,a[size];
in int max(int a,int b){if(a>b)return a;return b;}
struct SegmentTree{
struct node{
int l,r,mx,mxl,mxr,sum;
node(){mx=-inf,mxl=-inf,mxr=-inf,sum=0;}
}t[size<<2];
in void wh(int p)
{
t[p].sum=t[lc].sum+t[rc].sum;
t[p].mxl=max(t[lc].mxl,t[lc].sum+t[rc].mxl);
t[p].mxr=max(t[rc].mxr,t[rc].sum+t[lc].mxr);
t[p].mx=max(max(t[lc].mx,t[rc].mx),t[lc].mxr+t[rc].mxl);
}
void build(int p,int l,int r)
{
t[p].l=l,t[p].r=r;
if(l==r){t[p].mx=t[p].mxl=t[p].mxr=t[p].sum=a[l];return;}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
wh(p);
}
void change(int p,int i,int v)
{
if(t[p].l==i&&t[p].r==i){t[p].mx=t[p].mxl=t[p].mxr=t[p].sum=v;return;}
int mid=(t[p].l+t[p].r)>>1;
if(i<=mid) change(lc,i,v);
else change(rc,i,v);
wh(p);
}
node ask(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r) return t[p];
int mid=(t[p].l+t[p].r)>>1;
node x1,x2,ans;
if(l<=mid) x1=ask(lc,l,r);
if(r>mid) x2=ask(rc,l,r);
ans.sum=x1.sum+x2.sum;
ans.mxl=max(x1.mxl,x1.sum+x2.mxl);
ans.mxr=max(x2.mxr,x2.sum+x1.mxr);
ans.mx=max(max(x1.mx,x2.mx),x1.mxr+x2.mxl);
return ans;
}
}t;
signed main()
{
n=read(),m=read();
for(re int i=1;i<=n;++i) a[i]=read();
t.build(1,1,n);
for(re int i=1;i<=m;++i)
{
int k=read(),a=read(),b=read();
if(k==1){
if(a>b) a^=b,b^=a,a^=b;
printf("%lld\n",t.ask(1,a,b).mx);
}
if(k==2) t.change(1,a,b);
}
return 0;
}