记录编号 |
416603 |
评测结果 |
AAAAAAAAAA |
题目名称 |
数列操作C |
最终得分 |
100 |
用户昵称 |
HZOI_蒟蒻一只 |
是否通过 |
通过 |
代码语言 |
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(){;}