洛谷P2357 守墓人

老是写挂:)

#include<bits/stdc++.h>

using namespace std;

using ll=long long ;


const int maxn=2e5+9;
struct Node{
    ll l,r,v,tag;
}tr[maxn<<2];

ll n,f,a[maxn];

void build(int l,int r,int tot){
    if(l==r){
        tr[tot].v=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,tot<<1),build(mid+1,r,(tot<<1)|1);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
}

void update(int nl,int nr,int tot,int l,int r,ll x){
    int mid=(nl+nr)>>1;
    if(tr[tot].tag&&nl!=nr){
        tr[tot<<1].v+=tr[tot].tag*(mid-nl+1ll),tr[(tot<<1)|1].v+=tr[tot].tag*(nr-mid+0ll);
        tr[tot<<1].tag+=tr[tot].tag,tr[(tot<<1)|1].tag+=tr[tot].tag;
        tr[tot].tag=0;
    }
    if(l<=nl&&nr<=r){
        tr[tot].v+=(nr-nl+1ll)*x,tr[tot].tag+=x;
        return ;
    }
    if(mid>=l)update(nl,mid,tot<<1,l,r,x);
    if(mid<r)update(mid+1,nr,(tot<<1)|1,l,r,x);
    tr[tot].v=tr[tot<<1].v+tr[(tot<<1)|1].v;
}

ll query(int nl,int nr,int tot,int l,int r){
    ll mid=(nl+nr)>>1,res=0;
    if(tr[tot].tag&&nl!=nr){
        tr[tot<<1].v+=tr[tot].tag*(mid-nl+1ll),tr[(tot<<1)|1].v+=tr[tot].tag*(nr-mid+0ll);
        tr[tot<<1].tag+=tr[tot].tag,tr[(tot<<1)|1].tag+=tr[tot].tag;
        tr[tot].tag=0;
    }
    if(l<=nl&&nr<=r)return tr[tot].v;
    if(mid>=l)res+=query(nl,mid,tot<<1,l,r);
    if(mid<r)res+=query(mid+1,nr,(tot<<1)|1,l,r);
    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>f;
    for(int i=1;i<=n;++i)cin>>a[i];
    build(1,n,1);
    for(int i=1,x,y,z,w;i<=f;++i){
        cin>>x;
        if(x==1){
            cin>>y>>z>>w;
            update(1,n,1,y,z,w);
        }else if(x==2){
            cin>>y;
            update(1,n,1,1,1,y);
        }else if(x==3){
            cin>>y;
            update(1,n,1,1,1,-y);
        }else if(x==4){
            cin>>y>>z;
            cout<<query(1,n,1,y,z)<<"\n";
        }else cout<<query(1,n,1,1,1)<<"\n";
    }
}