记录编号	88391	评测结果	AAAAAAAAAA
题目名称	数列操作C	最终得分	100
用户昵称	ranto	是否通过	通过
代码语言	C++	运行时间	0.469 s
提交时间	2014-02-20 17:18:03	内存使用	0.31 MiB

#include <fstream>
#include <string>
#include <cmath>
#define to_long(a) static_cast<long long>(a)

using namespace std;

ifstream in("shuliec.in");
ofstream out("shuliec.out");

class SegTree
{
	struct node
	{
		long long l, r;//[l, r]
		node *lchd, *rchd;
		//node *father;//sometime it may be useful
		long long add;
		long long value;
		node() : l(0), r(0), lchd(0), rchd(0), add(0), value(0)/*, father(0)*/ {}
	};
	node *root;
	long long _construct(long long arr[], long long lenth, node *pn);
	long long _get_sum(long long l, long long r, node *pn);
	void _add(long long l, long long r, long long addn, node *pn);
	long long *st;//to evalueate the distance
public:
	SegTree() : root(new node) {}
	SegTree(long long arr[], long long lenth)//arr base on 0
	{
		st=arr;
		root=new node;
		_construct(arr, lenth, root);
	}
	long long get_sum(long long l, long long r) //[l, r] 
	{
		return _get_sum(l, r, root);
	}
	void add(long long l, long long r, long long addn)
	{
		_add(l, r, addn, root);
	}
	void display_structure();
};

long long SegTree::_construct(long long arr[], long long lenth, node *pn)//tested
{
	if(lenth == 1)
	{
		pn->value=*arr;
		pn->l=arr-st;
		pn->r=arr-st;
		return pn->value;
	}
	long long itemp(to_long(log(lenth)/log(2)));
	long long _lenth(1<<itemp);
	pn->lchd=new node;
	pn->rchd=new node;
	pn->l=arr-st;
	pn->r=pn->l+lenth-1;
	long long ret(0);
	if(lenth == _lenth)
	{
		ret+=_construct(arr, lenth/2, pn->lchd);
		ret+=_construct(arr+lenth/2, lenth/2, pn->rchd);
	}
	else
	{
		ret+=_construct(arr, _lenth, pn->lchd);
		ret+=_construct(arr+_lenth, lenth-_lenth, pn->rchd);
	}
	pn->value=ret;
	return ret;
}

long long SegTree::_get_sum(long long l, long long r, node *pn)//[l, r]//tested
{
	if(pn->l==l && pn->r==r)
	{
		return pn->value;
	}
	long long ret((r-l+1)*pn->add);
	if(r <= pn->lchd->r)
	{
		return ret+_get_sum(l, r, pn->lchd);
	}
	if(l >= pn->rchd->l)
	{
		return ret+_get_sum(l, r, pn->rchd);
	}
	ret+=_get_sum(l, pn->lchd->r, pn->lchd);
	ret+=_get_sum(pn->rchd->l, r, pn->rchd);
	return ret;
}

void SegTree::_add(long long l, long long r, long long addn, node *pn)
{
	pn->value+=(r-l+1)*addn;
	if(pn->l == l && pn->r == r)
	{
		pn->add+=addn;
		return ;
	}
	if(pn->lchd->r >= r)
	{
		_add(l, r, addn, pn->lchd);
	}
	else if(pn->rchd->l <= l)
	{
		_add(l, r, addn, pn->rchd);
	}
	else
	{
		_add(l, pn->lchd->r, addn, pn->lchd);
		_add(pn->rchd->l, r, addn, pn->rchd);
	}
	return ;
}

int main()
{
	long long n;
	in>>n;
	long long *num=new long long [n];
	for(long long i=0; i!=n; ++i)
	{
		in>> num[i];
	}
	SegTree st(num, n);
	//st.display_structure();
	in>> n;
	string tstring;
	for(long long i=0; i!=n; ++i)
	{
		in>> tstring;
		if(tstring == "SUM")
		{
			long long a, b;
			in>> a>> b;
			--a;
			--b;
			out<< (st.get_sum(a, b))<< endl;
		}
		else
		{
			long long a, b, c;
			in>> a>> b>> c;
			--a;
			--b;
			st.add(a, b, c);
		}
	}
	return 0;
}