题解 | #A Simple Problem with Integers#

思路

线段树板子。

代码

#include<iostream>
#define pushup(x) (tree[x]=tree[x<<1]+tree[x<<1|1])
#define MID int mid=(start+end)>>1
using namespace std;
const int maxn=1e6+7;
typedef long long ll;
ll tree[maxn<<2],lazy[maxn<<2];
int n,q,a,b,c,arr[maxn];
int ch;

void pushdown(int node,int start,int end){
    if(start==end) return;
    MID;
    if(lazy[node]){
        lazy[node<<1]+=lazy[node];
        lazy[node<<1|1]+=lazy[node];
        tree[node<<1]+=(ll)(mid-start+1)*lazy[node];
        tree[node<<1|1]+=(ll)(end-mid)*lazy[node];
        lazy[node]=0;
    }
}

void build(int node,int start,int end){
    if(start==end){
        tree[node]=arr[start];
        return;
    }
    MID;
    build(node<<1,start,mid);
    build(node<<1|1,mid+1,end);
    pushup(node);
}

void update(int node,int start,int end,int l,int r,int val){
    if(l<=start&&end<=r){
        tree[node]+=(ll)(end-start+1)*val;
        lazy[node]+=val;
        return;
    }
    MID;
    pushdown(node,start,end);
    if(l<=mid) update(node<<1,start,mid,l,r,val);
    if(r>mid) update(node<<1|1,mid+1,end,l,r,val);
    pushup(node);
}

ll query(int node,int start,int end,int l,int r){
    if(l<=start&&end<=r) return tree[node];
    MID;
    pushdown(node,start,end);
    ll res=0;
    if(l<=mid) res+=query(node<<1,start,mid,l,r);
    if(r>mid) res+=query(node<<1|1,mid+1,end,l,r);
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>arr[i];
    build(1,1,n);
    for(int i=1;i<=q;i++){
        //cin>>ch;
        char tt;cin>>tt;
        if(tt=='C'){
            cin>>a>>b>>c;
            update(1,1,n,a,b,c);
        }
        if(tt=='Q'){
            cin>>a>>b;
            cout<<query(1,1,n,a,b)<<endl;
        }
    }
    return 0;
}