洛谷P2357题解

#include<bits/stdc++.h>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;i++)
#define mid ((l+r)>>1)
#define differ(a,b) (b-a+1)
#define lc p<<1
#define rc p<<1|1
using namespace std;
// #define FOR(i,l,r) for(register int i=l;i<=r;i++)
const int N = 2e5+7;
int n,f;
struct SGN{
    int sum,lz;
}nd[N<<2];
int fs[N];
int ma;//
void pushup(int p){
    nd[p].sum=nd[lc].sum+nd[rc].sum;
}
void build(int p,int l,int r){
    if(l==r){
        nd[p].sum=fs[l];
        return;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(p);
}
void pushdown(int p,int l,int r){
    if(nd[p].lz){
        nd[lc].lz+=nd[p].lz;
        nd[rc].lz+=nd[p].lz;
        nd[lc].sum+=nd[p].lz*differ(l,mid);
        nd[rc].sum+=nd[p].lz*differ((mid+1),r);
        nd[p].lz=0;
    }
}
void update(int p,int l,int r,int x,int y,int k){
    if(x<=l&&y>=r){
        nd[p].sum+=differ(l,r)*k;
        nd[p].lz+=k;
    }
    else{
        pushdown(p,l,r);
        if(x<=mid){
            update(lc,l,mid,x,y,k);
        }
        if(y>mid){
            update(rc,mid+1,r,x,y,k);
        }
        pushup(p);
    }
}
int Qsum(int p,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        return nd[p].sum;
    }
    pushdown(p,l,r);
    int ans = 0;
    if(x<=mid){
        ans+=Qsum(lc,l,mid,x,y);
    }
    if(y>mid){
        ans+=Qsum(rc,mid+1,r,x,y);
    }
    return ans;
    // return Qsum(lc,l,mid,x,y)+Qsum(rc,mid+1,r,x,y);
}
signed main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>f;
    FOR(i,1,n){
        cin>>fs[i];
    }
    build(1,1,n);
    int op;
    FOR(i,1,f){
 
        cin>>op;
        if(op==1){
            int l,r,k;
            cin>>l>>r>>k;
            update(1,1,n,l,r,k);
        }
        if(op==2){
            int k;
            cin>>k;
            update(1,1,n,1,1,k);
        }
        if(op==3){
            int k;
            cin>>k;
            update(1,1,n,1,1,-k);
        }
        if(op==4){
            int l,r;
            cin>>l>>r;
            cout<<Qsum(1,1,n,l,r)<<endl;
        }
        if(op==5){
            cout<<Qsum(1,1,n,1,1)<<endl;
        }
    }
}