ZOJ - 2706 Thermal Death of the Universe(线段树)

题目链接：点击查看

题目大意：给定包含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(线段树)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。