解題思路：基礎(chǔ)的線段樹區(qū)間修改

我按照書上敲的代碼不知道為什么WA。。。

#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1e5; int n,q,l,r,_sum; int setv[maxn<<2],sum[maxn<<2];void maintain(int o,int L,int R) {int lc = o*2, rc = o*2+1;sum[o] = 0;if(R > L){sum[o] = sum[lc] + sum[rc];}else sum[o] = setv[o]; }void pushdown(int o) {int lc = o*2, rc = o*2+1;if(setv[o] >= 0){setv[lc] = setv[rc] = setv[o];setv[o] = -1;} }void update(int o,int L,int R,int v) {int lc = o*2, rc = 2*o+1;if(l <= L && R <= r){setv[o] = v;}else{pushdown(o);int M = (L + R) >> 1;if(l <= M) update(lc,L,M,v);else maintain(lc,L,M);if(r > M)update(rc,M+1,R,v);else maintain(rc,M+1,R);}maintain(o,L,R); }void query(int o,int L,int R) {if(setv[o] >= 0){_sum += setv[o] * (min(R,r) - max(L,l) + 1);}else if(l <= L && R <= r){_sum += sum[o];}else{int M = (L + R) >> 1;if(l <= M) query(o*2,L,M);if(r > M) query(o*2+1,M+1,R);} }int main() {int v,f;scanf("%d",&n);memset(setv,-1,sizeof(setv));for(int i = 1; i <= n; i++){scanf("%d",&v);l = r = i;update(1,1,n,v);}scanf("%d",&q);while(q--){scanf("%d",&f);if(f == 1){scanf("%d%d%d",&l,&r,&v);update(1,1,n,v);}else{scanf("%d%d",&l,&r);_sum = 0;query(1,1,n);printf("%d\n",_sum);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hihocoder #1078 : 线段树的区间修改的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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