萌新刚学OI1ms,线段树求助

CSP_JAKME @ 2024-10-19 15:06:10

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m,a[maxn],tree[maxn*4];
int lzy[maxn*4]; 
void pushup(int u){
    tree[u]=tree[u*2]+tree[u*2+1];
}
void build(int u,int left,int right){
    if(left==right){
        tree[u]=a[left];
        return;
    }
    int mid=(left+right)/2;
    build(u*2,left,mid);
    build(u*2+1,mid+1,right);
    pushup(u);
    return;
}
bool intheline(int L,int R,int l,int r){
    return l<=L&&r>=R;
}
bool cdline(int L,int R,int l,int r){
    return L<=r&&R>=l;
}
int sum(int u,int left,int right,int l,int r){
    if(intheline(left,right,l,r)) return tree[u];
    else if(cdline(left,right,l,r)){
        int mid=(left+right)/2;
        return sum(u*2,left,mid,l,r)+sum(u*2+1,mid+1,right,l,r);
    }
    return 0;
}
void make(int u,int k,int len){
    lzy[u]+=k;
    tree[u]+=len*k;
    return;
}
void pushdown(int u,int left,int right){
    int mid=(left+right)/2;
    make(u*2,lzy[u],mid-left+1);
    make(u*2+1,lzy[u],right-mid);
    lzy[u]=0;
    return;
}
/*
void printt(int u){
    if(u>2*n-1) return;
    cout << tree[u] << " ";
    printt(u*2);
    printt(u*2+1);
}
*/
void update(int u,int left,int right,int l,int r,int k){
    if(intheline(left,right,l,r)){
        make(u,k,right-left+1);
        return;
    }else if(cdline(left,right,l,r)){
        int mid=(left+right)/2;
        pushdown(u,left,right);
        update(u*2,left,mid,l,r,k);
        update(u*2+1,mid+1,right,l,r,k);
        pushup(u);
    }else return;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt,x,y;
        cin >> opt >> x >> y;
        if(opt==1){
            int k;
            cin >> k;
            update(1,1,n,x,y,k);
        }else{
            printf("%d\n",sum(1,1,n,x,y));
        }
    }
    return 0;
}

by liuhaoyan0323 @ 2024-10-19 15:25:10

@CSP_JAKME

#include <bits/stdc++.h>
#define lc idx<<1
#define rc idx<<1|1
#define int long long
#define N 100005
using namespace std;
typedef struct TreeNode{
    int idx,l,r,sum,add;
}TreeNode;
TreeNode tr[N<<2];
int n,m,opt,x,y,k,data[N];
inline void read(int &num){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        f=(ch=='-')?-1:1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    num=x*f;
}
inline void pushup(int idx){
    tr[idx].sum=tr[lc].sum+tr[rc].sum;
}
inline void pushdown(int idx){
    if(tr[idx].add){
        tr[lc].add+=tr[idx].add;
        tr[rc].add+=tr[idx].add;
        tr[lc].sum+=(tr[lc].r-tr[lc].l+1)*tr[idx].add;
        tr[rc].sum+=(tr[rc].r-tr[rc].l+1)*tr[idx].add;
        tr[idx].add=0;
    }
}
inline void build(int idx,int l,int r){
    tr[idx].sum=tr[idx].add=0;
    tr[idx].l=l;
    tr[idx].r=r;
    if(l==r){
        tr[idx].sum=data[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(idx);
}
inline int query(int idx,int l,int r){
    if(tr[idx].l>=l&&tr[idx].r<=r){
        return tr[idx].sum;
    }
    pushdown(idx);
    int mid=(tr[idx].l+tr[idx].r)>>1,res=0;
    if(l<=mid)res+=query(lc,l,r);
    if(r>mid)res+=query(rc,l,r);
    pushup(idx);
    return res;
}
inline void update(int idx,int l,int r,int add){
    if(tr[idx].l>=l&&tr[idx].r<=r){
        tr[idx].add+=add;
        tr[idx].sum+=(tr[idx].r-tr[idx].l+1)*add;
        return ;
    }
    pushdown(idx);
    int mid=(tr[idx].l+tr[idx].r)>>1;
    if(l<=mid)update(lc,l,r,add);
    if(r>mid)update(rc,l,r,add);
    pushup(idx);
}
signed main(){
    read(n);
    read(m);
    for(int i=1;i<=n;++i){
        read(data[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;++i){
        read(opt);
        read(x);
        read(y);
        switch(opt){
            case 1:
                read(k);
                update(1,x,y,k);
                break;
            case 2:
                printf("%lld\n",query(1,x,y));
                break;
        }
    }
    return 0;
}