首页 > 代码库 > ZOJ 2706 Thermal Death of the Universe (线段树)
ZOJ 2706 Thermal Death of the Universe (线段树)
题目链接:ZOJ 2706 Thermal Death of the Universe (线段树)
题意:n个数,m个操作。
每个操作(a,b)表示(a,b)所有值更新为这个区间的平均数:1.当前的数列总和小于等于原数列总和,取平均值的上界,反之,取下界。
注意有负数的情况。
AC代码:
#include<stdio.h> #include <math.h> #define LL long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=30010; const LL INF=0xffffffffffff; struct node { LL l,r,laz; LL sum; LL mid() { return (l+r)/2; } }; struct node tree[maxn<<2]; LL pre; void build(LL l,LL r,LL rt) { tree[rt].l=l; tree[rt].r=r; tree[rt].laz=INF; if(tree[rt].l==tree[rt].r) { scanf("%lld",&tree[rt].sum); return ; } LL m=tree[rt].mid(); build(lson); build(rson); tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; } void PushDown(LL rt,LL m) { if(tree[rt].laz!=INF) { tree[rt<<1].laz=tree[rt].laz; tree[rt<<1|1].laz=tree[rt].laz; tree[rt<<1].sum=(m-(m>>1))*tree[rt].laz; tree[rt<<1|1].sum=(m>>1)*tree[rt].laz; tree[rt].laz=INF; } } void updata(LL L,LL R,LL add,LL rt) { if(L<=tree[rt].l && tree[rt].r<=R) { tree[rt].laz=add; tree[rt].sum=(tree[rt].r-tree[rt].l+1)*add; return ; } LL m=tree[rt].mid(); PushDown(rt,tree[rt].r-tree[rt].l+1); if(R<=m) updata(L,R,add,rt<<1); else if(L>m) updata(L,R,add,rt<<1|1); else { updata(L,R,add,rt<<1); updata(L,R,add,rt<<1|1); } tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; } LL query(LL L,LL R,LL rt) { if(L<=tree[rt].l && tree[rt].r<=R) { return tree[rt].sum; } LL m=tree[rt].mid(); PushDown(rt,tree[rt].r-tree[rt].l+1); LL ret=0; if(R<=m) ret+=query(L,R,rt<<1); else if(L>m) ret+=query(L,R,rt<<1|1); else { ret+=query(L,R,rt<<1); ret+=query(L,R,rt<<1|1); } return ret; } int main() { LL a,b,i; LL n,m; LL ans; double ave; //printf("%lld\n",INF); while(scanf("%lld %lld",&n,&m)!=EOF) { //memset(tree,0,sizeof tree); build(1,n,1); pre=0; for(i=1;i<=n;i++) pre+=query(i,i,1); while(m--) { scanf("%lld%lld",&a,&b); LL sum=query(a,b,1); ave=1.0*sum/(b-a+1); if(query(1,n,1)<=pre) ans=(LL)ceil(ave); else ans=(LL)floor(ave); updata(a,b,ans,1); } for(i=1;i<n;i++) printf("%lld ",query(i,i,1)); printf("%lld\n\n",query(i,i,1)); } return 0; } /* 6 1 1 2 3 4 5 6 1 6 6 2 1 2 3 4 5 6 2 6 1 5 1 1 1 1 1 1 1 6 2 1 1 1 3 1 1 3 4 4 5 6 4 1 2 3 4 5 6 1 2 2 6 1 3 2 5 3 3 -1 -1 -2 1 2 2 3 1 3 */
ZOJ 2706 Thermal Death of the Universe (线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。