求调

Fuxh_18 @ 2024-07-19 09:55:38

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+1;
struct Tr{
    int l,r,v,f;
}t[N<<2];
int n,m;
void pushu(int u){
    t[u].v=t[u<<1].v+t[u<<1|1].v;
}
void pushd(int u){
    t[u<<1].v+=t[u].f;
    t[u<<1|1].v+=t[u].f;
    t[u<<1].f+=(t[u<<1].r-t[u<<1].l+1)*t[u].f;
    t[u<<1|1].f+=(t[u<<1|1].r-t[u<<1|1].l+1)*t[u].f;
    t[u].f=0;
}
void build(int u,int l,int r){
    t[u].l=l,t[u].r=r;
    if(l==r){
        cin>>t[u].v;
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushu(u);
}
void change(int u,int l,int r,int k){
    if(t[u].l>=l&&t[u].r<=r){
        t[u].f+=k;
        t[u].v+=k*(t[u].r-t[u].l+1);
        return ;
    }
    pushd(u);
    int mid=t[u].l+t[u].r>>1;
    if(l<=mid){
        change(u<<1,l,r,k);
    }
    if(r>mid){
        change(u<<1|1,l,r,k);
    }
    pushu(u);
}
int cx(int u,int l,int r){
    if(t[u].l>=l&&t[u].r<=r){
        return t[u].v;
    }
    pushd(u);
    int mid=t[u].l+t[u].r>>1,v=0;
    if(l<=mid){
        v+=cx(u<<1,l,r);
    }
    if(r>mid){
        v+=cx(u<<1|1,l,r);
    }
    return v;
}
int main(){
    cin>>n>>m;
    build(1,1,n);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,k;
            cin>>l>>r>>k;
            change(1,l,r,k);
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<cx(1,l,r)<<endl;
        }
    }
    return 0;
}

by X____ @ 2024-07-19 10:02:49

@Fuxh_18 pushdown写错了，没开long long

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+1;
struct Tr{
    int l,r,v,f;
}t[N<<2];
int n,m;
void pushu(int u){
    t[u].v=t[u<<1].v+t[u<<1|1].v;
}
void pushd(int u){
    if(!t[u].f) return;
    t[u<<1].f+=t[u].f;
    t[u<<1|1].f+=t[u].f;
    t[u<<1].v+=(t[u<<1].r-t[u<<1].l+1)*t[u].f;
    t[u<<1|1].v+=(t[u<<1|1].r-t[u<<1|1].l+1)*t[u].f;
    t[u].f=0;
}
void build(int u,int l,int r){
    t[u].l=l,t[u].r=r;
    if(l==r){
        cin>>t[u].v;
        return ;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushu(u);
}
void change(int u,int l,int r,int k){
    if(t[u].l>=l&&t[u].r<=r){
        t[u].f+=k;
        t[u].v+=k*(t[u].r-t[u].l+1);
        return ;
    }
    pushd(u);
    int mid=t[u].l+t[u].r>>1;
    if(l<=mid){
        change(u<<1,l,r,k);
    }
    if(r>mid){
        change(u<<1|1,l,r,k);
    }
    pushu(u);
}
int cx(int u,int l,int r){
    if(t[u].l>=l&&t[u].r<=r){
        return t[u].v;
    }
    pushd(u);
    int mid=t[u].l+t[u].r>>1,v=0;
    if(l<=mid){
        v+=cx(u<<1,l,r);
    }
    if(r>mid){
        v+=cx(u<<1|1,l,r);
    }
    return v;
}
signed main(){
    cin>>n>>m;
    build(1,1,n);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int l,r,k;
            cin>>l>>r>>k;
            change(1,l,r,k);
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<cx(1,l,r)<<endl;
        }
    }
    return 0;
}

by Fuxh_18 @ 2024-07-19 10:13:21

@X____ 谢谢