題目鏈接：點擊查看

題目大意：給定包含n個數的序列，然后是m次操作，每次操作給出兩個數l，r表示一個閉區間[l，r]，要求令閉區間中的數替換為該閉區間的平均數，對于平均數有以下規定：

若平均數為整數，則直接替換

若當前序列之和大于初始序列之和，則平均數向下取整

若當前序列之和小于等于初始序列之和，則平均數向上取整

最后輸出經過m次操作后的序列（注意輸出格式）

題目分析：這個題需要維護區間和，進行區間更新和區間查詢，以及最后的輸出需要用到點查詢，標準的線段樹思想，我覺得這個題的難點就是就是對于平均數的處理了，因為怕出錯，寫的時候小心翼翼的分成了好多種情況討論，還好最后都討論全了，關于維護區間和的sum變量需要開到long long大小，這個看了題目數據范圍后毋庸置疑，就是向下傳遞的lazy變量也需要開到long long我就有點不太理解了。。可能是我太菜了吧，一開始因為lazy開成了int WA了一發，也沒什么好說的了，直接上代碼吧：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=3e4+100;int n,m;struct Node {int l,r;LL sum,lazy;//注意記得開long long }tree[N<<2];void pushup(int k) {tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; }void pushdown(int k) {tree[k<<1].lazy=tree[k<<1|1].lazy=tree[k].lazy;tree[k<<1].sum=(tree[k<<1].r-tree[k<<1].l+1)*tree[k<<1].lazy;tree[k<<1|1].sum=(tree[k<<1|1].r-tree[k<<1|1].l+1)*tree[k<<1|1].lazy;tree[k].lazy=0; }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].lazy=0;if(l==r){scanf("%lld",&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 l,int r,LL val) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].r<=r&&tree[k].l>=l){tree[k].lazy=val;tree[k].sum=(tree[k].r-tree[k].l+1)*val;return;}if(tree[k].lazy)pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }LL query(int k,int l,int r) {if(tree[k].r<l||tree[k].l>r)return 0;if(tree[k].r<=r&&tree[k].l>=l){return tree[k].sum;}if(tree[k].lazy)pushdown(k);return query(k<<1,l,r)+query(k<<1|1,l,r); }void ans(int k)//輸出函數，直接利用點查詢的遞歸順序依次輸出了，省下了返回到main函數的工夫了 {if(tree[k].l==tree[k].r){printf("%lld%c",tree[k].sum,tree[k].l==n?'\n':' ');return;}if(tree[k].lazy)pushdown(k);ans(k<<1);ans(k<<1|1); }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){build(1,1,n);LL sum=tree[1].sum;while(m--){int x,y;scanf("%d%d",&x,&y);LL sumlr=query(1,x,y);LL lr=(y-x+1);LL temp=tree[1].sum;LL average;if(sumlr%lr==0)//整除 {average=sumlr/lr;}else if(sumlr>=0)//正數 {if(temp>sum)average=sumlr/lr;elseaverage=sumlr/lr+1;}else//負數 {if(temp>sum)average=sumlr/lr-1;elseaverage=sumlr/lr;}update(1,x,y,average);}ans(1);printf("\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的ZOJ - 2706 Thermal Death of the Universe(线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。