#include <stdio.h>
#define N 100000

int n;
__int64 total;

struct node
{
	__int64 sum;
	int addPerElmt;
};

struct node line_tree[4 * N + 3];

void build_tree(int q, int left, int right);

void update(int q, int left, int right, int li, int ri, int value);

void question(int q, int left, int right, int li, int ri);

int main()
{
	int qn;
	int i;
	int tmp;
	char tc;
	int begin, end, add;
	
	scanf("%d %d", &n, &qn);
	build_tree(0, 1, n);
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &tmp);
		update(0, 1, n, i, i, tmp);
	}

	for (i = 0; i < qn; i++)
	{
		getchar();
		scanf("%c", &tc);
		if (tc == 'C')
		{
			scanf("%d %d %d", &begin, &end, &add);
			update(0, 1, n, begin, end, add);
		}
		else
		{
			scanf("%d %d", &begin, &end);
			total = 0;
			question(0, 1, n, begin, end);
			printf("%I64d\n", total);
		}
	}

	return 0;
}

void build_tree(int q, int left, int right)
{
	int mid = (left + right) >> 1;

	line_tree[q].addPerElmt = 0;
	line_tree[q].sum = 0;

	if (left < right)
	{
		build_tree(q * 2 + 1, left, mid);
		build_tree(q * 2 + 2, mid + 1, right);
	}
}

void update(int q, int left, int right, int li, int ri, int value)
{
	int mid = (left + right) >> 1;

	if (left == li && right == ri)
	{
		line_tree[q].addPerElmt += value;
		line_tree[q].sum += (ri - li + 1) * value;

		return;
	}

	line_tree[q].sum += (ri - li + 1) * value;

	if (li <= mid)
	{
		if (ri <= mid)
		{
			update(q * 2 + 1, left, mid, li, ri, value);
		}
		else
		{
			update(q * 2 + 1, left, mid, li, mid, value);
			update(q * 2 + 2, mid + 1, right, mid + 1, ri, value);
		}
	}
	else
		update(q * 2 + 2, mid + 1, right, li, ri, value);
}

void question(int q, int left, int right, int li, int ri)
{
	int mid = (left + right) >> 1;

	if (left == li && right == ri)
	{
		total += line_tree[q].sum;
		return;
	}

	if (line_tree[q].addPerElmt)
		total += line_tree[q].addPerElmt * (ri - li + 1);

	if (li <= mid)
	{
		if (ri <= mid)
		{
			question(q * 2 + 1, left, mid, li, ri);
		}
		else
		{
			question(q * 2 + 1, left, mid, li, mid);
			question(q * 2 + 2, mid + 1, right, mid + 1, ri);
		}
	}
	else
		question(q * 2 + 2, mid + 1, right, li, ri);
}

• Re:我的程序能过，但还是WA (2526) snow_my_dream 2015-12-26 11:17:26