记录编号	318949	评测结果	AAAAAAAAAA
题目名称	数列操作C	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.223 s
提交时间	2016-10-10 07:42:34	内存使用	0.98 MiB

#include "stdio.h"
#include "math.h"
typedef long long LL;

const int maxnumber = 100100;
int n, m, a[maxnumber];
int block[maxnumber], blocksize, blockl[2100], blockr[2100], blockcnt, tot[2100], cnt[2100], lazy[2100];
// 各点所在块的编号  块的大小          各块的左右边界        块的个数 块中数的总和 块中有几个数

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

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

inline void Block_Add(const int& s, const int& t, const int& num)
{
	for(int i = block[s] + 1; i < block[t]; i++)
		lazy[i] += num;
	for(int i = s; block[i] == block[s] && i <= t; i++){
		tot[block[i]] += num;
		a[i] += num;
	}
	if(block[s] == block[t]) return;
	for(int i = blockl[block[t]]; i <= t; i++){
		tot[block[i]] += num;
		a[i] += num;
	}
}

inline LL Block_Sum(const int& s, const int& t)
{
	LL ret = 0;
	for(int i = block[s] + 1; i < block[t]; i++)
		ret += tot[i] + lazy[i] * cnt[i];
	for(int i = s; block[i] == block[s] && i <= t; i++)
		ret += a[i] + lazy[block[i]];
	if(block[s] == block[t]) return ret;
	for(int i = blockl[block[t]]; i <= t; i++)
		ret += a[i] + lazy[block[i]];
	return ret;
}

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

	Read(n);
	blocksize = (int)sqrt(n);
	for(int i = 1; i <= n; i++){
		Read(a[i]);
		block[i] = i / blocksize + 1;
		tot[block[i]] += a[i];
		cnt[block[i]]++;
	}
	for(int i = 1; i <= n; i++)
		if(block[i] != block[i-1]){
			blockl[++blockcnt] = i;
			blockr[blockcnt-1] = i - 1;
		}
	blockr[blockcnt] = n;

	Read(m);
	char ch[10] = {'\0'};
	int s, t, num;
	while(m--){
		scanf("%s", ch);
		if(ch[0] == 'A'){
			Read(s); Read(t); Read(num);
			Block_Add(s, t, num);
		}
		else{
			Read(s); Read(t);
			Write(Block_Sum(s, t));
		}
	}

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

	return 0;
}