pku--3468 A Simple Proble with Integers（線分樹）

 
テーマ接続:http://poj.org/problem?id=3468
 
 
 
Time Limit：5000 MS Memory Limit：131772 K Total Submissions：17698 Acceptted：4581 Case Time Limit：20000 MS Description You have N integers、A 1、A 2、…You need to deal with twokids of operations.One type of operation isto add some given number to each number in a given interval.The otheher isto ask for the sum of numbersinininterval.InputThe firs firs inininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininof A 1,A 2,…AN.-100000≦Ai≦100000 000.Each of the next Qラインs represents an operation.「C a b c」means adding c to each of Aa，Aa＋1，…，Ab.-10000≦c≦10000.「Q a b」meansquerythe sum of Aa，A＋1，…Ab.Output You need to answer all Q command in order.One answer in a line.Sample Input 10 1 2 3 3 3 4 4 7 7 8 9 Q 4 1 10 Q 2 4 C 3 3 3 3 Q 2 4 Sample Output 4 55 Hige The mashe exted of langed 32 bit。
 
 
件名:
Q（1≦Q≦100,000）個数A 1、A 2…AQと、複数回行われるかもしれない二つの動作：1）ある区間Ai…Ajの個数にn（n可変）2を加えて、ある区間Ai…Ajの数の和を求める。
 
 
問題のデータ規模は簡単な方法で解決できません。
 
本人も一日目は線分樹に接触しました。前のACで水割りの線分樹を作ったら、基本的に自分で線分樹を作ることができます。
 
本題の解法は線分樹を利用したものです。
 
注意すべきなのは1.データ範囲で、データを保存するにはlong longまたは_u uint 64保存（区間を除いて整形が可能です。他の最後は64ビットを使用します。）
 
                   2.和えるだけで、加数するたびに葉っぱノードに更新します。速度が遅すぎるのは避けなければなりません。本題樹ノード構造：struct CNode｛    int a，b;///区間起点と終点    CNode*left、*right；    long long nSum;//元の和    long long Inc;//増分cの積算｝本ノードの区間の和は、実はnSum+Inc*(R-L+1)です。
 
                 3.増加時に、プラスの区間がノードをちょうどカバーすると、そのノードのInc値を増加して、もう下に進まない。そうでないとnSumを更新して、さらにインクリメンタルをクエリに転送します。もし検査待ち区間がノードをちょうどカバーしていないなら、ノードのIncを下にバンドして、Incに代表されるすべての増分をnSumに加えてから、Incを0にクリアして、次に照会します。
 
 

#include <iostream>
using namespace std;
#define MAXN 100010
int N,Q;

__int64 num[MAXN], ans ,x;

struct data
{
	__int64 sum,inc;
	int l,r;
}Tree[4*MAXN];

void CreateTree(int k,int l,int r)								//  
{
	Tree[k].l = l;
	Tree[k].r = r;
	Tree[k].inc = 0;
	if(l == r)
		Tree[k].sum = num[l];
	else
	{
		int mid=(l+r)>>1;
		CreateTree(k+k,l,mid);
		CreateTree(k+k+1,mid+1,r);
		Tree[k].sum = Tree[k+k].sum + Tree[k+k+1].sum;
	}
}


void Add(int k,int l,int r,__int64 inc)								//C  
{
	if(Tree[k].l == l && Tree[k].r == r)
	{
		Tree[k].inc += inc;
	}
	else
	{
		int mid = Tree[k+k].r;
		Tree[k].sum += (r-l+1)*inc;
		if(l>mid)
			Add(k+k+1,l,r,inc);
		else if(r<=mid)
			Add(k+k,l,r,inc);
		else
		{
			Add(k+k ,l,mid,inc);
			Add(k+k+1 ,mid+1,r,inc);
		}
	}
}

void Query(int k,int l,int r,__int64 temp)
{
	temp += Tree[k].inc;
	if(Tree[k].l == l &&Tree[k].r == r)
	{
		ans+= Tree[k].sum + temp * (r-l+1);
	}
	else
	{

		int mid = Tree[k+k].r;
		if(l>mid)
			Query(k+k+1,l,r,temp);
		else if(r<=mid)
			Query(k+k,l,r,temp);
		else
		{
			Query(k+k ,l,mid,temp);
			Query(k+k+1 ,mid+1,r,temp);
		}
	}
}

int main()
{
	int i,j;
	char ch;
	while(scanf("%d%d",&N,&Q)!=EOF)
	{
		
		
		for(i=1;i<=N;i++)
			scanf("%I64d",&num[i]);
		
		CreateTree(1,1,N);

		while(Q--)
		{
			getchar();
			scanf("%c %d %d",&ch,&i,&j);
			if(ch=='Q')
			{
				ans = 0;
				Query(1,i,j,0);
				printf("%I64d
",ans);
			}
			else
			{
				scanf("%I64d",&x);
				Add(1,i,j,x);
			}
		}
	}
}