題目鏈接

Solution

線段樹是一門比較刁鉆的手藝...
此題我們需要維護 \(4\) 個變量:

\(amx\) 代表當前節(jié)點的最大值.

\(lmx\) 代表當前節(jié)點以左端點為起點的區(qū)間最大值.

\(rmx\) 代表當前節(jié)點以右端點為結尾的區(qū)間最大值.

\(sum\) 代表整段的和.

然后我們在 \(push\)_\(up\) 的時候,也是要做蠻多工作.
\(lc\) 為左端點,\(rc\) 為右端點.

\(lmx=max(lmx_{lc},sum_{lc}+lmx_{rc})\)
也就是說可以單獨取左兒子里的最大值,也可以一直取到右兒子的 \(lmx\) 為止.

\(rmx=max(rmx_{rc},sum_{rc}+rmx_{lc})\)
和上文同理.

\(sum=sum_{lc}+sum_{rc}\)

\(amx=max(amx_{lc},amx_{rc},rmx_{lc}+lmx_{rc})\)
最關鍵的一步,更新每一個節(jié)點的答案. 可以在圖上自己理解,此處不贅述.

特別注意,查詢的時候也要把所有查出來的區(qū)間進行類似的操作...

Code

#include<bits/stdc++.h> using namespace std; const int maxn=1000008; struct node {int l,r,lc,rc;int lmx,rmx,amx,sum; }sgm[maxn*4]; int n,m,k,x,y; int cnt,a[maxn];void push_up(int x) {int ll=sgm[x].lc,rr=sgm[x].rc;sgm[x].sum=sgm[ll].sum+sgm[rr].sum;sgm[x].lmx=max(sgm[ll].lmx,sgm[ll].sum+sgm[rr].lmx);sgm[x].rmx=max(sgm[rr].rmx,sgm[rr].sum+sgm[ll].rmx);sgm[x].amx=max(max(sgm[ll].amx,sgm[rr].amx),sgm[ll].rmx+sgm[rr].lmx); } void build(int l,int r,int now) {sgm[now].l=l;sgm[now].r=r;if(l==r){sgm[now].lmx=sgm[now].rmx=sgm[now].sum=sgm[now].amx=a[l];return;}int mid=(l+r)>>1;sgm[now].lc=2*now;build(l,mid,sgm[now].lc);sgm[now].rc=2*now+1;build(mid+1,r,sgm[now].rc);push_up(now); } void change(int now,int to,int num) {int x=sgm[now].l,y=sgm[now].r;if(x==y){sgm[now].lmx=sgm[now].rmx=sgm[now].sum=sgm[now].amx=num;return;}int mid=(x+y)>>1;if(to<=mid) change(sgm[now].lc,to,num);else change(sgm[now].rc,to,num);push_up(now); } node query(int now,int l,int r) {int x=sgm[now].l,y=sgm[now].r;if(l<=x&&r>=y) return sgm[now];int mid=(x+y)>>1,ll=sgm[now].lc,rr=sgm[now].rc;if(r<=mid) return query(ll,l,r);else if(l>mid) return query(rr,l,r);else{node t,t1=query(ll,l,r),t2=query(rr,l,r);t.lmx=max(t1.lmx,t1.sum+t2.lmx);t.rmx=max(t2.rmx,t2.sum+t1.rmx);t.amx=max(max(t1.amx,t2.amx),t1.rmx+t2.lmx);return t;} } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,n,1);for(int i=1;i<=m;i++){scanf("%d%d%d",&k,&x,&y);if(k==1) {if(x>y) swap(x,y);printf("%d\n",query(1,x,y).amx);}else change(1,x,y);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Kv-Stalin/p/9535100.html

總結

以上是生活随笔為你收集整理的P4513 小白逛公园 (线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。