比赛 |
数据结构模板题 |
评测结果 |
RRRRRRRRRRRRRRR |
题目名称 |
数列操作A |
最终得分 |
0 |
用户昵称 |
dream |
运行时间 |
3.034 s |
代码语言 |
C++ |
内存使用 |
3.17 MiB |
提交时间 |
2025-04-15 19:55:41 |
显示代码纯文本
#include<bits/stdc++.h>
#define ls p*2
#define rs p*2+1
using namespace std;
typedef long long ll;
const int N=100005;
int a[N];
struct node{
int l,r;
ll sum,add;
}tr[4*N];
int n,m;
void pushup(int p){
tr[p].sum=tr[ls].sum+tr[rs].sum;
}
void build(int p,int l,int r){
tr[p]={l,r,0,0};
if(l==r){
tr[p].sum=a[l];
return;
}
int mid=(l+r)/2;
build(ls,l,mid);
build(rs,mid+1,r);
pushup(p);
}
void pushdown(int p){
tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[p].add;
tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[p].add;
tr[ls].add+=tr[p].add;
tr[rs].add+=tr[p].add;
tr[p].add=0;
}
void update(int p,int l,int r,ll v){
if(l<=tr[p].l&&tr[p].r<=r){
tr[p].sum+=(tr[p].r-tr[p].l+1)*v;
tr[p].add+=v;
return;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
if(l<=mid){
update(ls,l,r,v);
}
if(r>mid){
update(rs,l,r,v);
}
pushup(p);
}
ll query(int p,int l,int r){
if(l<=tr[p].l&&tr[p].r<=r){
return tr[p].sum;
}
pushdown(p);
int mid=(tr[p].l+tr[p].r)/2;
ll res=0;
if(l<=mid){
res+=query(ls,l,r);
}
if(r>mid){
res+=query(rs,l,r);
}
return res;
}
int main(){
freopen("shuliea.in","r",stdin);
freopen("shuliea.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
cin>>m;
for(int i=1;i<=m;i++){
string str;
cin>>str;
if(str[0]=='S'){
int x,y;
cin>>x>>y;
cout<<query(1,x,y)<<"\n";
}
else{
int x,y;
cin>>x>>y;
update(1,x,x,y);
}
}
return 0;
}