记录编号 416603 评测结果 AAAAAAAAAA
题目名称 数列操作C 最终得分 100
用户昵称 GravatarHZOI_蒟蒻一只 是否通过 通过
代码语言 C++ 运行时间 0.463 s
提交时间 2017-06-22 11:08:48 内存使用 2.23 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100005,maxk=320;
int n,m,cnt,size,st[maxk],en[maxk],belong[maxn];
typedef long long LL;
LL a[maxn],pre[maxn],sum[maxk];
void Build()
{
	size=(int)sqrt(n);cnt=n/size+(n%size?1:0);
	for(int i=1;i<=n;i++)belong[i]=(i-1)/size+1;
	for(int i=1;i<=cnt;i++)
	{
		st[i]=(i-1)*size+1;
		en[i]=min(i*size,n);
		for(int j=st[i];j<=en[i];j++)
		{
			pre[j]=a[j];
			sum[i]+=a[j];
		}
	}
}
void Add(int from,int to,long long val)
{
	if(belong[from]==belong[to])
	{
		for(int i=from;i<=to;i++)
		{
			sum[belong[to]]+=val;
			pre[i]+=val;
		}
		return;
	}
	for(int i=belong[from]+1;i<=belong[to]-1;i++)
	{
		sum[i]+=val*size;
		for(int j=st[i];j<=en[i];j++)pre[j]+=val;
	}
	for(int i=from;i<=en[belong[from]];i++)
	{
		pre[i]+=val;
		sum[belong[from]]+=val;
	}
	for(int i=st[belong[to]];i<=to;i++)
	{
		pre[i]+=val;
		sum[belong[to]]+=val;
	}
}
LL Query(int x,int y)
{
	LL res=0;
	if(belong[x]==belong[y])
	{
		for(int i=x;i<=y;i++)res+=pre[i];
		return res;
	}
	for(int i=belong[x]+1;i<=belong[y]-1;i++)res+=sum[i];
	for(int i=x;i<=en[belong[x]];i++)res+=pre[i];
	for(int i=st[belong[y]];i<=y;i++)res+=pre[i];
	return res;
}
int haha()
{
	freopen("shuliec.in","r",stdin);
	freopen("shuliec.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	Build();
	char opt[5];int x,y;LL z;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",opt);
		if(opt[0]=='A')
		{
			scanf("%d%d%lld",&x,&y,&z);
			Add(x,y,z);
		}
		else
		{
			scanf("%d%d",&x,&y);
			printf("%lld\n",Query(x,y));
		}
	}
	//while(1);
}
int sb=haha();
int main(){;}