【线段树】北大 poj 3468 A Simple Problem with Integers

 

/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2012 panyanyany All rights reserved.

    URL   : http://poj.org/problem?id=3468
    Name  : 3468 A Simple Problem with Integers

    Date  : Sunday, April 15, 2012
    Time Stage : 2 hours

    Result:
10074419	panyanyany
3468
Accepted	12492K	2047MS	C++
3148B	2012-04-15 12:46:56

Test Data :

Review :
普通的线段树方法要超时的，貌似还可以用splay tree（伸展树）。小媛的博客上说要用lazy方法……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>

#include <algorithm>
#include <iostream>
#include <queue>

using namespace std ;

#define MEM(a, v)        memset (a, v, sizeof (a))    // a for address, v for value
#define max(x, y)        ((x) > (y) ? (x) : (y))
#define min(x, y)        ((x) < (y) ? (x) : (y))

#define INF     (0x3f3f3f3f)
#define MAXN 100010
#define LESN 10002

#define L(x)	((x)<<1)
#define R(x)	(((x)<<1)|1)

#define DB    /##/
typedef __int64	LL;

struct NODE {
	int lf, rh;
	LL sm, inc;
};

int		q, n;
NODE	segTree[MAXN*6]; 	//开小了一直runtime error
LL		inc;

void build(int id, int lf, int rh)
{
	segTree[id].lf = lf;
	segTree[id].rh = rh;
	segTree[id].sm = 0;
	segTree[id].inc = 0;

	if (lf == rh)
		return ;

	int mid = (lf + rh) / 2;
	build(id<<1, lf, mid);
	build((id<<1)|1, mid+1, rh);
}

LL update(int id, int lf, int rh, int val)
{
	// 不在当前区间（一般来说都不用判断这个……）
	if (segTree[id].lf > rh || segTree[id].rh < lf)
		return 0;

	// 到达匹配区间，这里不深入更新每一个叶子，因为会超时
	if (segTree[id].lf == lf && segTree[id].rh == rh)
	{
		segTree[id].inc += val;
		segTree[id].sm += val*(rh-lf+1);
		return val*(rh-lf+1);
	}

	int mid = (segTree[id].lf + segTree[id].rh) / 2;
	LL sum;

	if (rh <= mid)
		sum = update(id<<1, lf, rh, val);
	else if (mid < lf)
		sum = update((id<<1)|1, lf, rh, val);
	else
		sum = update(id<<1, lf, mid, val) + update((id<<1)|1, mid+1, rh, val);

	segTree[id].sm += sum;
	return sum;
}

LL query(int id, int lf, int rh)
{
	if (rh < segTree[id].lf || segTree[id].rh < lf)
	{
		return 0;
	}

	if (inc = segTree[id].inc)
	{	//查询的时候才更新子节点的增量
		segTree[L(id)].inc += inc; 	//相当于对子区间进行一次update
		segTree[L(id)].sm += inc * (segTree[L(id)].rh - segTree[L(id)].lf + 1);
		segTree[R(id)].inc += inc;
		segTree[R(id)].sm += inc * (segTree[R(id)].rh - segTree[R(id)].lf + 1);
		segTree[id].inc = 0; 	//增量都传递到子区间去了，这里就要置零
	}


	if (lf == segTree[id].lf && rh == segTree[id].rh)
		return segTree[id].sm;

	int mid = (segTree[id].lf + segTree[id].rh) / 2;

	if (rh <= mid)
		return query(id<<1, lf, rh);
	else if (mid < lf)
		return query((id<<1)|1, lf, rh);
	
	return query(id<<1, lf, mid) + query((id<<1)|1, mid+1, rh);
}

int main()
{
	int i, j, x, y, v;
	LL res;
	char c;
	while (scanf("%d%d", &n, &q) != EOF)
	{
		build(1, 1, n);
		for (i = 1; i <= n; ++i)
		{
			scanf("%d", &j);
			update(1, i, i, j);
		}
		while (q--)
		{
			getchar();
			scanf("%c", &c);
			scanf("%d %d", &x, &y);
			if ('Q' == c)
			{
				res = query(1, x, y);
				printf ("%I64d\n", res);
			}
			else
			{
				scanf("%d", &v);
				update(1, x, y, v);
			}
		}
	}
	return 0;
}