比赛 数据结构模板题 评测结果 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;
}