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

*/