POJ 3468 A Simple Problem with Integers 线段树区间修改

http://poj.org/problem?id=3468

题目大意：

思路：

线段树的区间修改。。。。。

昨天晚上改了老半天。

然后关机准备睡觉毕竟今天有实验。。去洗个头。。突然有灵感。。急急忙忙的开电脑改了就对了~哈哈哈

PS:POJ AC 100了~ 因为混迹各个OJ，SO才100

用位运算优化*2  1600+MS，不用2200MS。。。差了挺多

顺便测试了下很久以前想的k<<1和k+k的效率，果然是k<<1的效率高，k+k慢了30多MS

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=100000+10;
typedef long long LL;
LL sum[MAXN<<2],add[MAXN<<2];
int a[MAXN];
void build(LL  k,LL  L,LL  R)
{
	if(L==R) sum[k]=a[L];
	else
	{
		int m=(L+R)>>1;
		build(k<<1,L,m);
		build((k<<1)+1,m+1,R);
		sum[k]=sum[k<<1]+sum[(k<<1)+1];
	}
}

void update(LL  k,LL  L,LL  R,LL  a,LL  b,LL  v)
{
	sum[k]+=(min(R,b)-max(L,a)+1)*v;
	if(a<=L&&R<=b)   add[k]+=v;	
	else
	{
		int m=(L+R)>>1;
		if(a<=m) update(k<<1,L,m,a,b,v);
		if(m<b)  update((k<<1)+1,m+1,R,a,b,v);
	}	
}
LL ans;
void query(LL  k,LL L,LL  R,LL  a,LL  b,LL  addv)
{
	if(a<=L&&R<=b) ans+= sum[k]+(R-L+1)*addv;
	else
	{
		LL ans=0;
		int m=(L+R)>>1;
		if(a<=m)   query(k<<1,L,m,a,b,addv+add[k]);
		if(m<b)    query((k<<1)+1,m+1,R,a,b,addv+add[k]);
	}  
}

int main()
{
//	freopen("e:\\input.txt","r",stdin);
	int n,q;
	while(~scanf("%d%d",&n,&q))
	{
		memset(add,0,sizeof(add));
		memset(sum,0,sizeof(sum));
		
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		
		build(1,1,n);
	
		for(int i=0;i<q;i++)
		{
			char cmd[5];
			int a,b,v;
			scanf("%s",cmd);
			if(cmd[0]==‘Q‘)
			{
				ans=0;
				scanf("%d%d",&a,&b);
				query(1,1,n,a,b,0);
				printf("%lld\n",ans);
			}
			else
			{
				scanf("%d%d%d",&a,&b,&v);
				update(1,1,n,a,b,v);
			}
		}
	}
	return 0;
}

POJ 3468 A Simple Problem with Integers 线段树区间修改,布布扣,bubuko.com

POJ 3468 A Simple Problem with Integers 线段树区间修改

原文：http://blog.csdn.net/murmured/article/details/21321417