现在的位置: 首页 > 算法 > 正文

poj3468 A Simple Problem with Integers

2019年09月22日 算法 ⁄ 共 1916字 ⁄ 字号 评论关闭
/*
 * poj3468 AC
 * 线段树的基本操作(注意输出要用long long)
 * 区间增减+区间查询
 *
 * 不同于单点增减,区间增减并非立刻更新当前区间,而依赖于"懒惰标记"的运用。
 * 中心思想:
 * 	   在更新时,只要某个结点的区间完全属于增减区间,则更新当前结点,并做上标记,
 * 表示当前结点的信息是可靠的,之后退出而不更新儿子结点。
 * 	   在查询时,当某结点的区间与查询区间有交集而不属于时,则将当前结点信息pushdown到
 * 儿子结点,同时更新"懒惰标记",然后查询儿子结点。
 * 	   
 * 	   什么是"懒惰",就是当前该做的事没做完,做个标记记住。之后要来查询时,没有查到想
 * 查的信息,发现了这个标记,就接着把没做完的事做完,即传递给儿子结点,继续查询。
 * 
 * 区间增减算法流程(在一个增减区间内增加或减少一个值):
 *     1.判断增减区间与结点区间是否有交集。
 *     	 没有交集,则退出。
 *     2.判断结点区间是否属于增减区间。
 *		 若属于,则更新当前结点的"懒惰标记"为真与结点权值,退出。
 *		 否则转3。
 *	   3.如果"懒惰标记"为真,说明当前结点为当前操作的最底层。
 *	     pushdown();  将当前结点信息传递向下层结点。
 *	   4.分别更新左右儿子。
 *	   5.pushup(); 
 *	     更新当前结点值。
 *
 * 区间查询算法流程:
 *     1.判断增减区间与结点区间是否有交集。
 *     	 没有交集,则退出。
 *     2.判断结点区间是否属于查询区间。
 *       若属于,则返回当前结点值。
 *       否则转3。
 *     3.pushdown(); 
 *       在查询时才将之前增减操作时增减的值传向儿子结点。
 *       在pushdown(); 中同时更新了"懒惰标记"。
 *     4.返回左右儿子的查询值。  
 *
 * */
#include<cstdio>

long long sum[400005],cha[400005];
//FILE* fin;
void pushup(long x)
{
	sum[x] = sum[x<<1]+sum[x<<1|1];
}
void pushdown(long x,int m)
{
	cha[x<<1] += cha[x],cha[x<<1|1] += cha[x];
	sum[x<<1] += cha[x]*(m-(m>>1));
	sum[x<<1|1] += cha[x]*(m>>1);
	cha[x] = 0;
}
void build(long l,long r,long x)
{
	cha[x] = 0;
	if(l==r)
	{
		scanf("%lld",&sum[x]);
//		fscanf(fin,"%lld",&sum[x]);
		return;
	}
	long mid = (l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	sum[x] = sum[x<<1]+sum[x<<1|1];
}

void update(long i,long j,long long k,long l,long r,long x)
{
	if(i>r || j<l) return;
	if(i<=l && r<=j) 
	{
		cha[x] += k,sum[x] += (long long)k*(r-l+1);
		return;
	}
	long mid = (l+r)>>1;
	if(cha[x]) pushdown(x,r-l+1);
	update(i,j,k,l,mid,x<<1);
	update(i,j,k,mid+1,r,x<<1|1);
	pushup(x);
	return;
}

long long query(long i,long j,long l,long r,long x)
{
	if(i>r || j<l) return 0;
	if(i<=l && r<=j) return sum[x];
	long mid = (l+r)>>1;
	pushdown(x,r-l+1);
	return query(i,j,l,mid,x<<1)+query(i,j,mid+1,r,x<<1|1);
}

int main()
{
	long n,q;
//	fin = fopen("d.in","r");
	scanf("%ld%ld",&n,&q);
//	fscanf(fin,"%ld%ld",&n,&q);
	build(1,n,1);
	while(q--)
	{
		long i,j;
		long long k;
		char s[10];
		scanf("%s",s);
//		fscanf(fin,"%s",s);
		if(s[0]=='Q') 
		{
			scanf("%ld%ld",&i,&j);
//			fscanf(fin,"%ld%ld",&i,&j);
			printf("%lld\n",query(i,j,1,n,1));
		}else
		{
			scanf("%ld%ld%lld",&i,&j,&k);
//			fscanf(fin,"%ld%ld%lld",&i,&j,&k);
			update(i,j,k,1,n,1);
		}
	}
	return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.