題目鏈接：點擊查看

題目大意：給出一個長度為n的序列，進行m次操作：

1 x y? 查詢區(qū)間[l,r]中的最大連續(xù)子段和

0 x y??將第x個數(shù)修改為y

題目分析：因為涉及到單點修改和區(qū)間查詢等操作，所以可以選擇線段樹和樹狀數(shù)組，但又因為需要維護的變量比較多，所以我們選擇用線段樹操作方便點。因為要維護每個區(qū)間段的最大連續(xù)子段和，所以我們需要像區(qū)間合并那種題目一樣，另外維護四個變量，ll,rr,all,sum分別表示區(qū)間內(nèi)從左端開始的最大連續(xù)子段和，從右端開始的最大連續(xù)子段和，該區(qū)間內(nèi)的最大連續(xù)子段和，該區(qū)間的權(quán)值和。

---

轉(zhuǎn)移狀態(tài)時，我們需要考慮全所有的情況再寫pushup函數(shù)：

sum：這個最簡單，等于左右兒子區(qū)間和之和

關(guān)于ll變量：要從下面幾點中取最大值：

左兒子的ll

左兒子的sum+右兒子的ll

關(guān)于rr變量：同樣要從下面幾點中取最大值：

右兒子的rr

右兒子的sum+左兒子的rr

關(guān)于all變量：從下面幾點中取最大值：

左兒子的all

右兒子的all

左兒子的rr+右兒子的ll

---

這樣一梳理，就解決了一大半的難點了，只要照著一句一句實現(xiàn)就好了，下面在講一下這個題目比較難想的query，即查詢函數(shù)

因為涉及到區(qū)間合并，我們同樣也要分三個階段來分類討論：

所求區(qū)間全部都在當前區(qū)間的左兒子區(qū)間內(nèi)：繼續(xù)進入左兒子遞歸

所求區(qū)間全部都在當前區(qū)間的右兒子區(qū)間內(nèi)：繼續(xù)進入右兒子遞歸

所求區(qū)間既在左兒子的區(qū)間，又在右兒子的區(qū)間內(nèi)：將左右兒子遞歸后的結(jié)果儲存到結(jié)構(gòu)體中，對這兩個結(jié)構(gòu)體進行類似于pushup的操作來達到區(qū)間合并的效果，最后返回結(jié)構(gòu)體

---

直接上代碼了：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<cmath> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e4+100;struct Node {int ll,rr,sum,all;int l,r; }tree[N<<2];void pushup(int k) {tree[k].ll=max(tree[k<<1].ll,tree[k<<1].sum+tree[k<<1|1].ll);tree[k].rr=max(tree[k<<1|1].rr,tree[k<<1|1].sum+tree[k<<1].rr);tree[k].all=max(max(tree[k<<1].all,tree[k<<1|1].all),tree[k<<1].rr+tree[k<<1|1].ll);tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;if(l==r){scanf("%d",&tree[k].sum);tree[k].ll=tree[k].rr=tree[k].all=tree[k].sum;return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); }void update(int k,int pos,int val) {if(tree[k].l==tree[k].r){tree[k].sum=tree[k].ll=tree[k].rr=tree[k].all=val;return;}int mid=(tree[k].r+tree[k].l)>>1;if(mid>=pos)update(k<<1,pos,val);elseupdate(k<<1|1,pos,val);pushup(k); }Node query(int k,int l,int r)//注意查詢函數(shù)返回的是結(jié)構(gòu)體，方便對左右兒子區(qū)間進行合并的操作 {if(tree[k].l>=l&&tree[k].r<=r)return tree[k];int mid=(tree[k].l+tree[k].r)>>1;if(mid>=r)return query(k<<1,l,r);else if(mid<l)return query(k<<1|1,l,r);else{Node a,b,ans;a=query(k<<1,l,r);b=query(k<<1|1,l,r);ans.sum=a.sum+b.sum;ans.ll=max(a.ll,a.sum+b.ll);ans.rr=max(b.rr,b.sum+a.rr);ans.all=max(max(a.all,b.all),a.rr+b.ll);return ans;} }int main() { // freopen("input.txt","r",stdin)int n,m;while(scanf("%d",&n)!=EOF){build(1,1,n);scanf("%d",&m);while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==1){Node temp=query(1,x,y);cout<<temp.all<<endl;}else{update(1,x,y);} // cout<<endl; // for(int i=1;i<=10;i++) // cout<<tree[i].l<<' '<<tree[i].r<<' '<<tree[i].ll<<' '<<tree[i].rr<<' '<<tree[i].all<<' '<<tree[i].sum<<endl;}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的SPOJ - GSS3 Can you answer these queries III(线段树+区间合并)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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