记录编号	535093	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	数列操作C	最终得分	100
用户昵称	数声风笛ovo	是否通过	通过
代码语言	C++	运行时间	1.566 s
提交时间	2019-07-04 08:47:32	内存使用	21.67 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
class qwq{//普通的建树操作 
   	public:
   		int l,r,lc,rc;//左端点，右端点，左儿子节点的编号，右儿子节点的编号
   		ll sum;
   		ll lazy;//懒标记，本题难点 
}tree[233333];
int QAQ[233333]={0};//卖个萌嘻嘻 
int num=1; //定义变量以存储L值与R值 
void build(int l,int r){//存树操作，因为存在懒标记所以方式存在差异 
   	int mid=(l+r)/2;
   	int root=num;
   	tree[root].l=l;tree[root].r=r;
   	tree[root].lazy=0;//懒标记初始化 
   	if(l<r){//左右端点不重合 
   		tree[root].lc=++num;
   		build(l,mid);//存左孩子 
   		tree[root].rc=++num;
   		build(mid+1,r);//存右孩子 
   		tree[root].sum=tree[tree[root].lc].sum+tree[tree[root].rc].sum;
   	}
   	else{//左右端点重合 
   		tree[root].lc=0;tree[root].rc=0;//节点两端点重合，即没有孩子 
		tree[root].sum=QAQ[l];
   	}
   	return;
}
void add(int root,int gl,int gr,ll plus,ll lazytag){
//区间加值，本函数调用变量从左至右分别为当前节点编号，加值操作范围左、右端点，所加的值与懒标记值 
   	if(root==-1) return;//意义不明的判错程序 
   	if(gl>tree[root].r||gr<tree[root].l){//所访问节点线段不在加值范围内 
   		tree[root].sum+=lazytag*(tree[root].r-tree[root].l+1);
   		tree[root].lazy+=lazytag;
   		return;
   	}
   	if(gl<=tree[root].l&&gr>=tree[root].r){//所访问节点线段在加值范围内 
   		tree[root].lazy+=(plus+lazytag);
   		tree[root].sum+=(plus+lazytag)*(tree[root].r-tree[root].l+1);
   		return;
   	}
   	else{//所访问节点线段部分在加值范围内 
   		add(tree[root].lc,gl,gr,plus,lazytag+tree[root].lazy);//访问其左孩子 
   		add(tree[root].rc,gl,gr,plus,lazytag+tree[root].lazy);//访问其右孩子 
   		tree[root].lazy=0;//懒标记归零 
   		if(tree[root].lc!=-1){//重置被van坏掉的线段树(???) 
   			tree[root].sum=tree[tree[root].lc].sum+tree[tree[root].rc].sum; 
   		} 
   	}
   	return;
}
ll sum(int root,int gl,int gr,ll lazytag){
//区间查询，本函数调用变量从左至右分别为当前节点编号，查值操作范围左、右端点与懒标记值 
   	if(root==-1) return 0;//意义不明的判错程序 
   	if(gl>tree[root].r||gr<tree[root].l) return 0;//所访问节点线段不在查值范围内
   	if(gl<=tree[root].l&&gr>=tree[root].r){//所访问节点线段在查值范围内
   		return tree[root].sum+lazytag*(tree[root].r-tree[root].l+1);
   	}
   	return sum(tree[root].lc,gl,gr,lazytag+tree[root].lazy)+sum(tree[root].rc,gl,gr,lazytag+tree[root].lazy);//所访问节点线段包含加值范围 
}
int cxw(){
   	int a,b,c,n,m;char ovo[5];
   	freopen("shuliec.in","r",stdin);
   	freopen("shuliec.out","w",stdout);
   	scanf("%d",&n);
   	for(int i=1;i<=n;i++){
   		scanf("%d",&QAQ[i]);
   	}
   	build(1,n);//存树操作 
   	scanf("%d",&m);
   	for(int i=1;i<=m;i++){
   		scanf("%s",&ovo);
   		if(ovo[0]=='A'){//加值操作 
   			scanf("%d%d%d",&a,&b,&c);
   			add(1,a,b,c,0);
   		}
   		else{//查值操作 
   			scanf("%d%d",&a,&b);
   			printf("%lld\n",sum(1,a,b,0));
   		}
   	}
   	return 0;
}
int wjb=cxw();
int main(void){;}