悬关

lrj3247 @ 2024-02-22 19:49:24

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
/*struct TREE{
    int l,r;
    long long sum;
};*/
int n,m,fi,x,y,k,L[N],R[N];
long long sum[N*5],tag[N],a;
void build(int rt,int l,int r,long long v){
    L[rt]=l;
    R[rt]=r;
    if(l==r){
        sum[rt]=v;
        return ;
    }
    int mid=(l+r)>>1;
    build(rt*2,l,mid,v);
    build(rt*2+1,mid+1,r,v);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void spread(int rt){
    if(tag[rt]){
        sum[rt*2]=sum[rt*2]+tag[rt]*(R[rt*2]-L[rt*2]+1);
        sum[rt*2+1]=sum[rt*2+1]+tag[rt]*(R[rt*2+1]-L[rt*2+1]+1);
        tag[rt*2]+=tag[rt];
        tag[rt*2+1]+=tag[rt];
        tag[rt]=0;
    }
}
void change(int rt,int l,int r,int x,int y,long long v){
    if(x<=l&&r<=y){
        sum[rt]=sum[rt]+(long long)v*(r-l+1);
        tag[rt]+=v;
        return ;
    }
    spread(rt);
    int mid=(l+r)>>1;
    if(x<=mid) change(rt*2,l,mid,x,y,v);
    if(y>mid) change(rt*2+1,mid+1,r,x,y,v);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
}
long long ask(int rt , int l,int r,int x,int y){
    if(x<=l&&r<=y) return sum[rt];
    spread(rt);
    int mid=(l+r)>>1;
    long long ans=0;
    if(mid>=x) ans+=ask(rt*2,l,mid,x,y);
    if(mid+1<=y) ans+=ask(rt*2+1,mid+1,r,x,y);
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(register int i = 1 ; i<=n ; i++){
        cin>>a;
        build(1,1,n,a);
    }
    for(register int i = 1 ; i<=m ; i++){
        cin>>fi>>x>>y;
        if(fi==1){
            cin>>k;
            change(1,1,n,x,y,k);
        }
        else{
            cout<<ask(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

by Iictiw @ 2024-02-22 20:07:15

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
/*struct TREE{
    int l,r;
    long long sum;
};*/
int n,m,fi,x,y,k,L[N*5],R[N*5];
long long sum[N*5],tag[N*5],a[N];
void build(int rt,int l,int r){
    L[rt]=l;
    R[rt]=r;
    if(l==r){
        sum[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(rt*2,l,mid);
    build(rt*2+1,mid+1,r);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void spread(int rt){
    if(tag[rt]){
        sum[rt*2]=sum[rt*2]+tag[rt]*(R[rt*2]-L[rt*2]+1);
        sum[rt*2+1]=sum[rt*2+1]+tag[rt]*(R[rt*2+1]-L[rt*2+1]+1);
        tag[rt*2]+=tag[rt];
        tag[rt*2+1]+=tag[rt];
        tag[rt]=0;
    }
}
void change(int rt,int l,int r,int x,int y,long long v){
    if(x<=l&&r<=y){
        sum[rt]=sum[rt]+(long long)v*(r-l+1);
        tag[rt]+=v;
        return ;
    }
    spread(rt);
    int mid=(l+r)>>1;
    if(x<=mid) change(rt*2,l,mid,x,y,v);
    if(y>mid) change(rt*2+1,mid+1,r,x,y,v);
    sum[rt]=sum[rt*2]+sum[rt*2+1];
}
long long ask(int rt , int l,int r,int x,int y){
    if(x<=l&&r<=y) return sum[rt];
    spread(rt);
    int mid=(l+r)>>1;
    long long ans=0;
    if(mid>=x) ans+=ask(rt*2,l,mid,x,y);
    if(mid+1<=y) ans+=ask(rt*2+1,mid+1,r,x,y);
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(register int i = 1 ; i<=n ; i++)cin>>a[i];
    build(1,1,n);
    for(register int i = 1 ; i<=m ; i++){
        cin>>fi>>x>>y;
        if(fi==1){
            cin>>k;
            change(1,1,n,x,y,k);
        }
        else{
            cout<<ask(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}

by lrj3247 @ 2024-02-22 20:15:59

@Iictiw 多谢