记录编号	393863	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	新史「新幻想史 -现代史-」	最终得分	100
用户昵称	Ironk	是否通过	通过
代码语言	C++	运行时间	6.233 s
提交时间	2017-04-12 11:38:54	内存使用	7.60 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long LL;
const int N = 5e4 + 10;
const int M = 1e5 + 10;
 
int n, m, t;
inline int read() {
	register char ch = getchar();
	register int ans = 0, neg = 1;
	for (; !isdigit(ch); ch = getchar())
		if (ch == '-') neg = -1;
	for (; isdigit(ch); ch = getchar())
		ans = ans * 10 + ch - '0';
	return ans * neg;
}
 
 
namespace ST {
	const int M = 3e5 + 10;
 
	bool cls[M];
	LL val[M], add[M];
	#define lc(a) (a << 1)
	#define rc(a) (lc(a) | 1)
	inline void clearVal(int a) {
		cls[a] = true, val[a] = add[a] = 0;
	}
	inline void addVal(int a, int l, int r, int c) {
		add[a] += c, val[a] += (LL)c * (r - l + 1);
	}
	inline void pushDown(int a, int l, int r) {
		if (cls[a]) {
			cls[a] = false;
			clearVal(lc(a)), clearVal(rc(a));
		}
		if (add[a]) {
			int mid = (l + r) >> 1;
			addVal(lc(a), l, mid, add[a]);
			addVal(rc(a), mid + 1, r, add[a]);
			add[a] = 0;
		}
	}
	void build(int a, int l, int r) {
		if (l == r) return val[a] = read(), void(0);
		int mid = (l + r) >> 1;
		build(lc(a), l, mid), build(rc(a), mid + 1, r);
		val[a] = val[lc(a)] + val[rc(a)];
	}
	void modify(int a, int l, int r, int ll, int rr, int c) {
		pushDown(a, l, r);
		if (l == ll && r == rr) return addVal(a, l, r, c);
		val[a] += (LL)c * (rr - ll + 1);
		int mid = (l + r) >> 1;
		if (rr <= mid) return modify(lc(a), l, mid, ll, rr, c);
		else if (ll > mid) return modify(rc(a), mid + 1, r, ll, rr, c);
		return modify(lc(a), l, mid, ll, mid, c), modify(rc(a), mid + 1, r, mid + 1, rr, c);
	}
	LL query(int a, int l, int r, int ll, int rr) {
		pushDown(a, l, r);
		if (l == ll && r == rr) return val[a];
		int mid = (l + r) >> 1;
		if (rr <= mid) return query(lc(a), l, mid, ll, rr);
		else if (ll > mid) return query(rc(a), mid + 1, r, ll, rr);
		return query(lc(a), l, mid, ll, mid) + query(rc(a), mid + 1, r, mid + 1, rr);
	}
}
 
int cnt, cntAns;
LL ans[N];
struct Op {
	int type, l, r, t, c;
	LL *plc;
} op[M];
 
void init() {
	n = read(), m = read();
	ST::build(1, 1, n);
	char ss[5];
	for (int i = 1; i <= m; ++i)
		if (scanf("%s", ss), *ss == 'Q') {
			op[++cnt].type = 0;
			op[cnt].l = read(), op[cnt].r = read(), op[cnt].t = read();
			op[cnt].plc = &ans[++cntAns];
			ans[cntAns] += ST::query(1, 1, n, op[cnt].l, op[cnt].r);
		} else {
			op[++cnt].type = 1;
			op[cnt].l = read(), op[cnt].r = read(), op[cnt].c = -read();
			op[++cnt].type = 1;
			op[cnt].l = read(), op[cnt].r = read(), op[cnt].c = read();
			op[cnt - 1].t = op[cnt].t = read();
		}
}
 
Op ary[M];
int getAry(int l, int r) {
	int mid = (l + r) >> 1;
	int ll = l, rr = mid + 1, tmp = 0;
	for (; op[rr].type && rr <= r; ++rr);
	for (; !op[ll].type && ll <= mid; ++ll);
	while (ll <= mid && rr <= r) {
		if (op[ll].t <= op[rr].t)
			ary[++tmp] = op[ll++];
		else ary[++tmp] = op[rr++];
		for (; op[rr].type && rr <= r; ++rr);
		for (; !op[ll].type && ll <= mid; ++ll);
	}
	while (rr <= r) {
		ary[++tmp] = op[rr++];
		for (; op[rr].type && rr <= r; ++rr);
	}
	while (ll <= mid) {
		ary[++tmp] = op[ll++];
		for (; !op[ll].type && ll <= mid; ++ll);
	}
	return tmp;
}
void mergeSort(int l, int r) {
	int mid = (l + r) >> 1;
	int ll = l, rr = mid + 1, tmp = l - 1;
	while (ll <= mid && rr <= r) {
		if (op[ll].t <= op[rr].t)
			ary[++tmp] = op[ll++];
		else ary[++tmp] = op[rr++];
	}
	while (rr <= r) ary[++tmp] = op[rr++];
	while (ll <= mid) ary[++tmp] = op[ll++];
	for (int i = l; i <= r; ++i) op[i] = ary[i];
}
void figure(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	figure(l, mid), figure(mid + 1, r);
	ST::clearVal(1);
	int len = getAry(l, r);
	for (int i = 1; i <= len; ++i) {
		if (ary[i].type)
			ST::modify(1, 1, n, ary[i].l, ary[i].r, ary[i].c);
		else *ary[i].plc += ST::query(1, 1, n, ary[i].l, ary[i].r);
	}
	mergeSort(l, r);
}
 
int main() {
	freopen("cdcq_a.in", "r", stdin);
	freopen("cdcq_a.out", "w", stdout);
	init();
	figure(1, cnt);
	for (int i = 1; i <= cntAns; ++i)
		printf("%lld\n", ans[i]);
	return 0;
}