poj3468.cpp

北大在线题库3468题标程代码

#include<cstdio>
#include<cstring>
struct node
{
	int l,r;
	__int64 sum,add;
};
int num[1<<17];

class SegTree
{
private:
	node tree[1<<18];
	void passDown(int index)
	{
		int j=index*2;
		int mid=(tree[index].l+tree[index].r)/2;
		tree[j].add+=tree[index].add;
		tree[j+1].add+=tree[index].add;
		tree[j].sum+=tree[index].add*(mid-tree[index].l+1);
		tree[j+1].sum+=tree[index].add*(tree[index].r-mid);
		tree[index].add=0;
	}
public:
	
	void buildTree(int l,int r,int index)
	{
		tree[index].l=l; tree[index].r=r; tree[index].add=0;
		if (l==r) tree[index].sum=num[l];
		else
		{
			int mid=(l+r)/2;
			buildTree(l,mid,index*2);
			buildTree(mid+1,r,index*2+1);
			tree[index].sum=tree[index*2].sum+tree[index*2+1].sum;
		}
	};

	void addNew(int l,int r,int c,int index)
	{
		if (tree[index].l>=l&&tree[index].r<=r) //overlay the current segment
		{
			tree[index].sum+=(__int64)c*(tree[index].r-tree[index].l+1);
			tree[index].add+=c;
		}
		else 
		{
			if (tree[index].add) passDown(index);
			int mid=(tree[index].l+tree[index].r)/2;
			int j=index*2;
			if (l<=mid) addNew(l,r,c,j);
			if (r>mid) addNew(l,r,c,j+1);
			tree[index].sum=tree[j].sum+tree[j+1].sum;
		}
	};

	__int64 subSum(int l,int r,int index)
	{
		
		if (tree[index].l>=l && tree[index].r<=r) //overlay the current segment
			return (tree[index].sum);
		else
		{
			if (tree[index].add) passDown(index);
			int mid,j;
			__int64 ans=0;
			mid=(tree[index].l+tree[index].r)/2;
			j=index*2;
			if (l<=mid) ans+=subSum(l,r,j);
			if (r>mid) ans+=subSum(l,r,j+1);
			return ans;
		}
	}
};
SegTree ST;
int main()
{
	int n,m,i,a,b,c;
	char cmd;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) scanf("%d",num+i);
	ST.buildTree(1,n,1);
	getchar();
	while (m--)
	{
		scanf("%c%d%d",&cmd,&a,&b);
		if (cmd=='C') scanf("%d",&c);
		getchar();
		if (cmd=='Q')
			printf("%I64d\n",ST.subSum(a,b,1));
		else
			ST.addNew(a,b,c,1);
	}
	return 0;
}