记录编号	160004	评测结果	AAAAAAAAAA
题目名称	数列操作C	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.359 s
提交时间	2015-04-23 16:52:56	内存使用	42.28 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
void file(){
	freopen("shuliec.in","r",stdin);
	freopen("shuliec.out","w",stdout);
}
 
#define N 1000010
#define LL long long
 
struct node{
	node *ch[2];
	int sum;
	LL v,add,sumv;
	int cmp(int x){
		if(x==ch[0]->sum+1) return -1;
		return x>ch[0]->sum+1;
	}
	node* init(LL x);
	void push();
	void update(){
		sum=ch[0]->sum+ch[1]->sum+1;
		sumv=ch[0]->sumv+ch[1]->sumv+v;
	}
}spT[N],*root,Null;
 
int n,tot,m;
LL a[N];
 
void node::push(){
	if(this==&Null) return;
	if(ch[0]!=&Null){
		ch[0]->add+=add;
		ch[0]->v+=add;
		ch[0]->sumv+=ch[0]->sum*add;
	}
	if(ch[1]!=&Null){
		ch[1]->add+=add;
		ch[1]->v+=add;
		ch[1]->sumv+=ch[1]->sum*add;
	}
	add=0;
}
 
void rot(node* &o,int x){
	node *tmp=o->ch[x];
	tmp->push();
	o->ch[x]=tmp->ch[x^1];
	tmp->ch[x^1]=o;
	o->update(); o=tmp;
	o->update();
}
 
node* node::init(LL x){
	sumv=x; sum=1;
	ch[0]=ch[1]=&Null;
	v=x; add=0;
	return this;
}
 
void splay(node* &o,int k){
	o->push();
	int t=o->cmp(k);
	if(t==-1) return;
	if(t) k-=o->ch[0]->sum+1;
	o->ch[t]->push();
	int t1=o->ch[t]->cmp(k);
	if(~t1){
		if(t1) k-=o->ch[t]->ch[0]->sum+1;
		splay(o->ch[t]->ch[t1],k);
		if(t1==t) rot(o,t);
		else rot(o->ch[t],t1);
	}
	rot(o,t);
}
 
node* build(LL src[],int l,int r){
	if(l==r) return spT[++tot].init(src[l]);
	int mid=(l+r)>>1;
	node* tmp=spT[++tot].init(src[mid]);
	if(mid-1>=l) tmp->ch[0]=build(src,l,mid-1);
	if(mid+1<=r) tmp->ch[1]=build(src,mid+1,r);
	tmp->update();
	return tmp;
}
 
void addin(int l,int r,int v){
	int len=r-l+1;
	splay(root,l); splay(root->ch[1],len+1);
	node* tmp=root->ch[1]->ch[0];
	tmp->add+=v; tmp->sumv+=tmp->sum*v;
	tmp->v+=v;
}
 
LL qsum(int l,int r){
	int len=r-l+1;
	splay(root,l);
	splay(root->ch[1],len+1);
	node* tmp=root->ch[1]->ch[0];
	return tmp->sumv;
}
 
int main(){
	file();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	root=build(a,0,n+1);
	scanf("%d",&m);
	char cmd[11];
	int l,r;
	LL v;
	for(int i=1;i<=m;i++){
		scanf("%s%d%d",cmd,&l,&r);
		if(l>r) swap(l,r);
		if(cmd[0]=='S') printf("%lld\n",qsum(l,r));
		else{
			scanf("%lld",&v);
			addin(l,r,v);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}