比赛 |
数列操作练习题 |
评测结果 |
AAAAAAAAAA |
题目名称 |
数列操作C |
最终得分 |
100 |
用户昵称 |
HZOI_蒟蒻一只 |
运行时间 |
0.951 s |
代码语言 |
C++ |
内存使用 |
8.32 MiB |
提交时间 |
2017-03-19 06:18:30 |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
long long data,del;}tree[400001];
int x[150001],y[150001];char ch[5];long long delta;int ax,ay,n,m;
long long num[100001];
void updata(int left,int right,int root){
if (ax>right || ay<left) return ;
if (ax<=left && ay>=right){tree[root].data+=delta*(right-left+1);tree[root].del+=delta;return;}
int mid=(left+right)/2;int del=tree[root].del;
tree[root*2].del+=del;tree[root*2+1].del+=del;tree[root*2].data+=del*(mid-left+1);
tree[root*2+1].data+=del*(right-mid);tree[root].del=0;
updata(left,mid,root*2);updata(mid+1,right,root*2+1);
tree[root].data=tree[root*2].data+tree[root*2+1].data;
}
long long search(int left,int right,int root){
if (ax>right || ay<left) return 0;
if (ax<=left && ay>=right){return tree[root].data;}
int mid=(left+right)/2;int del=tree[root].del;
tree[root*2].del+=del;tree[root*2+1].del+=del;tree[root*2].data+=del*(mid-left+1);
tree[root*2+1].data+=del*(right-mid);tree[root].del=0;
long long tmp1,tmp2;tmp1=search(left,mid,root*2);tmp2=search(mid+1,right,root*2+1);
tree[root].data=tree[root*2].data+tree[root*2+1].data;return tmp1+tmp2;
}
void init(){freopen("shuliec.in","r",stdin);freopen("shuliec.out","w",stdout);
int i;
scanf("%d\n",&n);
for (i=1;i<=n;i++)cin>>num[i];
}
void work(){
int i;
for (i=1;i<=n;i++){ax=i;ay=i;delta=num[i];updata(1,n,1);}
scanf("%d\n",&m);int p=0;
for (i=1;i<=m;i++){scanf("%s",ch);if (ch[0]=='A'){
cin>>ax>>ay>>delta;scanf("\n");updata(1,n,1);}
if (ch[0]=='S'){scanf("%d%d",&ax,&ay);delta=0;
long long ans=search(1,n,1);cout<<ans<<endl;}}}
int haha()
{
init();
work();
return 0;
}
int sb=haha();
int main(){;}