题解 P4513 【小白逛公园】
先分析一下题目大概意思。意思很简单
你需要完成两种操作。
1.将X的点进行更改
2.求a到b区间的最大子段和
看到这里，脑袋里第一眼浮现的解题方法就是线段树。（不会线段树左转线段树 ）
why？？
单点修改，区间查询，线段树不就可以处理吗？
现在问题来了：该怎么处理最大子段和呢？
我们不难想到，一个区间的最大子段和源于三个地方；
1.左边界以左的最大子段和。
2.右边界以右的最大子段和。
3.中间向两边拓展的最大子段和。
思路已经有了具体看代码。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=(500000+10)*4;
int num[maxn],addval[maxn];
struct node{
int lx,sum,rx,ans,l,r;
//lx:左边界以左的最大子段和；
//rx：右边界以右的最大子段和；
//ans：最后的最大子段和
//sum：区间总和
//l：左边界，r 右边界
}tree[maxn];
void build(int k,int left,int right){//建树
tree[k].l=left;
tree[k].r=right;//左右范围
if(left==right){
tree[k].sum=tree[k].lx=tree[k].rx=tree[k].ans=num[left];//初始值
return ;
}
int mid=(left+right)>>1;//二分拓展
build(k*2,left,mid);
build(k*2+1,mid+1,right);
tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;//求区间总和
tree[k].lx=max(tree[k*2].lx,tree[k*2].sum+tree[k*2+1].lx);//左边界最大值有两种可能：1.左子树的最大子段和，2.左子树的总和，加上右子树的左边界起始的最大子段和。
tree[k].rx=max(tree[k*2+1].rx,tree[k*2+1].sum+tree[k*2].rx);//右子树同理，可以自己推一下
tree[k].ans=max(max(tree[k*2].ans,tree[k*2+1].ans),tree[k*2].rx+tree[k*2+1].lx);//最终值比较
}
node query(int k,int lt,int rt){//查询
if(lt<=tree[k].l&&rt>=tree[k].r)return tree[k];//区间被包含，全部返回
node a,b,ans;//取出左子树，右子树
a.lx=a.rx=a.ans=a.ans=-2047483647;
b.lx=b.rx=b.ans=b.ans=-2047483647;
a.sum=b.sum=0;
ans.ans=-2047483647;
ans.sum=0;
int mid=(tree[k].l+tree[k].r)>>1;
if(lt<=mid){
a=query(k*2,lt,rt);
ans.sum+=a.sum;
}
if(rt>=mid+1){
b=query(k*2+1,lt,rt);
ans.sum+=b.sum;
}
ans.ans=max(a.rx+b.lx,max(a.ans,b.ans));//和建树时的想法相同
ans.lx=max(a.lx,a.sum+b.lx);
ans.rx=max(b.rx,b.sum+a.rx);
if(lt>mid){
ans.lx=max(ans.lx,b.lx);
}
if(rt<mid){
ans.rx=max(ans.rx,a.rx);
}
return ans;
}
void modify(int k,int lt,int rt,int qx,int val){//更改，和建树想法差不多
if(qx<lt||qx>rt)return ;
else if(lt==qx&&rt==qx){
tree[k].ans=tree[k].lx=tree[k].rx=tree[k].sum=val;
return ;
}
else {
int mid=lt+(rt-lt)/2;
modify(k*2,lt,mid,qx,val);
modify(k*2+1,mid+1,rt,qx,val);
tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
tree[k].lx=max(tree[k*2].lx,tree[k*2].sum+tree[k*2+1].lx);
tree[k].rx=max(tree[k*2+1].rx,tree[k*2+1].sum+tree[k*2].rx);
tree[k].ans=max(max(tree[k*2].ans,tree[k*2+1].ans),tree[k*2].rx+tree[k*2+1].lx);
return ;
}
}
signed main(){//主函数
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%lld",&num[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
int pre,x,y,z;
scanf("%lld%lld%lld",&pre,&x,&y);
if(pre==2){
modify(1,1,n,x,y);
}
else {
if(x>y)swap(x,y);
node a=query(1,x,y);
cout<<a.ans<<endl;
}
}
return 0;
}
/*
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
*/