题解 P4513 【小白逛公园】

#### 先分析一下题目大概意思。意思很简单 #### 你需要完成两种操作。 #### 1.将X的点进行更改 #### 2.求a到b区间的最大子段和 ### 看到这里，脑袋里第一眼浮现的解题方法就是线段树。（不会线段树左转[线段树](https://www.luogu.org/problem/P3372) ） ### 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 */ ``` ### 代码就是这样，主要是码字较多。 #### 看懂之后，推荐两道题 ### 1.[好一个一中腰鼓](https://www.luogu.org/problem/P2253) ### 2.[你能回答这些问题吗？（一样的）](https://www.acwing.com/problem/content/description/246/)