记录编号	393797	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	新史「新幻想史 -现代史-」	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	3.152 s
提交时间	2017-04-12 08:53:45	内存使用	6.36 MiB

#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;
typedef long long ll;

int n, m;

namespace Solve1 {
	const int MAXN = 503, MAXM = 503;
    
	ll a[MAXM][MAXN];

	void do_Q() {
		int x, y, z;
		scanf( "%d%d%d", &x, &y, &z );
		ll ans = 0;
		for( int i = x; i <= y; ++i ) ans += a[z][i];
		printf( "%lld\n", ans );
	}
	void do_M( int now ) {
		int x, y, z, l, r, v, t;
		scanf( "%d%d%d%d%d%d%d", &x, &y, &z, &l, &r, &v, &t );
		for( int i = t; i <= now; ++i ) {
			for( int j = x; j <= y; ++j ) a[i][j] -= z;
			for( int j = l; j <= r; ++j ) a[i][j] += v;
		}
	}
	void solve() {
		for( int i = 1; i <= n; ++i ) scanf( "%lld", &a[0][i] );
		for( int t = 1; t <= m; ++t ) {
			for( int i = 1; i <= n; ++i ) a[t][i] = a[t-1][i];
			char c; scanf( " %c", &c );
			if( c == 'Q' ) do_Q();
			else do_M(t);
		}
	}
}

namespace BIT {
	const int MAXN = 50010;
	inline int lowbit( int x ) {
		return x&(-x);
	}
    ll d[MAXN] = {0}, d2[MAXN] = {0};
	void add( int x, int v ) {
		for( int i = x; i <= n; i += lowbit(i) ) {
			d[i] += v;
			d2[i] += (ll)x*v;
		}
	}
	void add( int l, int r, int v ) {
		add(l,v), add(r+1,-v);
	}
	ll query( int x ) {
		ll sum = 0;
		for( int i = x; i; i -= lowbit(i) )
			sum += (x+1)*d[i] - d2[i];
		return sum;
	}
	ll query( int l, int r ) {
		return query(r) - query(l-1);
	}
	void clear( int x ) {
		for( ; x <= n; x += lowbit(x) )
			d[x] = d2[x] = 0;
	}
	void clear( int l, int r ) {
		clear(l), clear(r+1);
	}
}

namespace Solve2 {
	const int MAXN = 50010, MAXM = 50010;
	const int MAXQ = MAXN + MAXM*2;
	
	struct Query {
		int tm, tp, l, r, v;
		Query(){}
		Query( int tm, int tp, int l, int r, int v ):
			tm(tm),tp(tp),l(l),r(r),v(v){}
		bool operator<( const Query &rhs ) const {
			if( tm == rhs.tm ) return tp < rhs.tp;
			else return tm < rhs.tm;
		}
	};
	Query qy[MAXQ];
	ll ans[MAXN];
	int qidx = 0, aidx = 0;

	Query tmp[MAXQ];
	void cdq( int L, int R ) {
		if( R-L <= 1 ) return;
		int M = (L+R)>>1;
		cdq(L,M), cdq(M,R);
		int p = L, q = M, o = L;
		while( p < M && q < R ) {
			if( qy[p] < qy[q] ) {
				if( qy[p].tp == 0 )
					BIT::add(qy[p].l, qy[p].r, qy[p].v);
				tmp[o++] = qy[p++];
			} else {
				if( qy[q].tp == 1 )
					ans[qy[q].v] += BIT::query(qy[q].l, qy[q].r);
				tmp[o++] = qy[q++];
			}
		}
		while( p < M ) tmp[o++] = qy[p++];
		while( q < R ) {
			if( qy[q].tp == 1 )
				ans[qy[q].v] += BIT::query(qy[q].l, qy[q].r);
			tmp[o++] = qy[q++];
		}
		for( int i = L; i < R; ++i ) {
			qy[i] = tmp[i];
			if( qy[i].tp == 0 ) {
				BIT::clear(qy[i].l, qy[i].r);
			}
		}
	}
	
	void solve() {
		for( int i = 1; i <= n; ++i ) {
			int a; scanf( "%d", &a );
			qy[qidx++] = Query(0,0,i,i,a);
		}
		while( m-- ) {
			char ch; scanf( " %c", &ch );
			if( ch == 'Q' ) {
				int x, y, z;
				scanf( "%d%d%d", &x, &y, &z );
				qy[qidx++] = Query(z,1,x,y,aidx++);
			} else {
				int x, y, z, l, r, v, t;
				scanf( "%d%d%d%d%d%d%d", &x, &y, &z, &l, &r, &v, &t );
				qy[qidx++] = Query(t,0,x,y,-z);
				qy[qidx++] = Query(t,0,l,r,v);
			}
		}
		cdq(0,qidx);
		for( int i = 0; i < aidx; ++i ) printf( "%lld\n", ans[i] );
	}
}

int main() {
	freopen( "cdcq_a.in", "r", stdin );
	freopen( "cdcq_a.out", "w", stdout );
	scanf( "%d%d", &n, &m );
	if( n <= 500 && m <= 500 ) Solve1::solve();
	else Solve2::solve();
	return 0;
}