比赛 2017级练习 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 数列操作C 最终得分 100
用户昵称 サイタマ 运行时间 3.362 s
代码语言 C++ 内存使用 7.67 MiB
提交时间 2018-03-22 21:17:18
显示代码纯文本
#include<cstdio>
#include<cstring>
#define LL long long
#define FILE freopen("shuliec.in","r",stdin);freopen("shuliec.out","w",stdout);
using namespace std;
int n,i,m;
class node
{public:
	LL addMark,val;
}seg[601000];
int a[201000];
void BUILD(int root,int l,int r)
{
	seg[root].addMark=0;
	if(l==r)
		seg[root].val=a[l];
	else
	{
		int mid=l+(r-l)/2;
		BUILD(2*root,l,mid);
		BUILD(2*root+1,mid+1,r);
		seg[root].val=seg[2*root].val+seg[2*root+1].val;
	}
}
void pushdown(int root,int ml)
{
	if(seg[root].addMark)
	{
		seg[2*root].addMark+=seg[root].addMark;
		seg[2*root].val+=seg[root].addMark*(ml-(ml/2));
		seg[2*root+1].addMark+=seg[root].addMark;
		seg[2*root+1].val+=seg[root].addMark*(ml/2);
		seg[root].addMark=0;
	}
}
LL SUM(int root,int l,int r,int q_l,int q_r)
{
	LL nn=0;
	//if(q_l>r||q_r<l)
	//	return 0;
	if(q_l<=l&&q_r>=r)
		return seg[root].val;
	int mid=l+(r-l)/2;
	pushdown(root,r-l+1);
	if(q_l<=mid)
		nn+=SUM(2*root,l,mid,q_l,q_r);
	if(q_r>mid)
		nn+=SUM(2*root+1,mid+1,r,q_l,q_r);
	return nn;
}
void ADD(int root,int l,int r,int q_l,int q_r,int add)
{
	int mid=l+(r-l)/2;
	//if(q_l>r||q_r<l)
	//	return ;
	if(q_l<=l&&q_r>=r){
		seg[root].val+=(LL)add*(r-l+1);
		seg[root].addMark+=add;
		return;
	}
	pushdown(root,r-l+1);
	if(q_l<=mid)
		ADD(2*root,l,mid,q_l,q_r,add);
	if(q_r>mid)
		ADD(2*root+1,mid+1,r,q_l,q_r,add);
	seg[root].val=seg[2*root].val+seg[2*root+1].val;
}
int lyh()
{
	FILE
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	BUILD(1,1,n);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		char str[10];
		scanf("%s",&str);
		if(!strcmp(str,"SUM"))
		{
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%lld\n",SUM(1,1,n,l,r));
		}
		else
		{
			int l,r,d;
			scanf("%d%d%d",&l,&r,&d);
			ADD(1,1,n,l,r,d);
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
int Main=lyh();
int main(){;}