记录编号	352272	评测结果	AAAAAAAAAA
题目名称	magictree	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.279 s
提交时间	2016-11-17 06:28:13	内存使用	122.35 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

const int maxnumber = 2000100;
LL n, m;
LL s, t, num;
LL Tsum[maxnumber << 2];
LL lazy[maxnumber << 2];

template <class T>
inline void Read(T& a)
{
	a = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') {
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

template <class T>
inline void Write(T a)
{
	int cnt = 0;
	char ch[30] = {'\0'};
	while (1) {
		ch[++cnt] = a % 10LL + '0';
		a /= 10LL;
		if (!a) break;
	}
	while (cnt) putchar(ch[cnt--]);
	putchar('\n');
}

inline void PushDown(const int& l, const int& r, const int& rt)
{
	int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	lazy[lch] += lazy[rt]; lazy[rch] += lazy[rt];
	Tsum[lch] += (mid - l + 1) * lazy[rt]; Tsum[rch] += (r - mid) * lazy[rt];
	lazy[rt] = 0;
}

void Build(const int& l, const int& r, const int& rt)
{
	if (l == r) {
		Read(Tsum[rt]);
		return;
	}
	int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	Build(l, mid, lch);
	Build(mid + 1, r, rch);
	Tsum[rt] = Tsum[lch] + Tsum[rch];
}

void Modify(const int& l, const int& r, const int& rt)
{
	if (s <= l && t >= r) {
		Tsum[rt] += (r - l + 1) * num;
		lazy[rt] += num;
		return;
	}
	if (lazy[rt]) PushDown(l, r, rt);
	int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	if (t <= mid) Modify(l, mid, lch);
	else if (s >= mid + 1) Modify(mid + 1, r, rch);
	else {
		Modify(l, mid, lch);
		Modify(mid + 1, r, rch);
	}
	Tsum[rt] = Tsum[lch] + Tsum[rch];
}

LL Query_Sum(const int& l, const int& r, const int& rt)
{
	if (s <= l && t >= r) return Tsum[rt];
	if (lazy[rt]) PushDown(l, r, rt);
	int mid = (l + r) >> 1, lch = rt << 1, rch = lch | 1;
	if (t <= mid) return Query_Sum(l, mid, lch);
	else if (s >= mid + 1) return Query_Sum(mid + 1, r, rch);
	else return Query_Sum(l, mid, lch) + Query_Sum(mid + 1, r, rch);
	Tsum[rt] = Tsum[lch] + Tsum[rch];
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("magictree.in", "r", stdin); freopen("magictree.out", "w", stdout);
#endif

	char type[10] = {'\0'};
	Read(n); Read(m);
	Build(1, n, 1);
	while (m--) {
		scanf("%s", type);
		Read(s); Read(t); 
		s++; t++;
		if (type[0] == 'Q') Write(Query_Sum(1, n, 1));
		else { Read(num); Modify(1, n, 1); }
	}

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}