比赛 |
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(){;}