求助70pts

P3372 【模板】线段树 1

ikun_god @ 2024-01-06 16:36:09

RT

8 9 10WA了

#include<bits/stdc++.h>
using namespace std;
long long a[500010],tree[40010],mark[40010],n,m;
void jian(int l,int r,int p){
    if (l==r){
        tree[p]=a[l];
    }else{
        int mid=(l+r)/2;
        jian(l,mid,p*2);
        jian(mid+1,r,p*2+1);
        tree[p]=tree[p*2]+tree[p*2+1];
    }
}
void push(int p,int len){
    mark[p*2]+=mark[p];
    mark[p*2+1]+=mark[p];
    tree[p*2]+=mark[p]*(len-len/2);
    tree[p*2+1]+=mark[p]*(len/2);
    mark[p]=0;
}
void xiu(int l,int r,int d,int p,int cl,int cr){
    if (cl>r || cr<l){
        return ;
    }else if (cl>=l && cr<=r){
        tree[p]+=(cr-cl+1)*d;
        if (cr>cl){
            mark[p]+=d;
        }
    }else{
        int mid=(cl+cr)/2;
        push(p,cr-cl+1);
        xiu(l,r,d,p*2,cl,mid);
        xiu(l,r,d,p*2+1,mid+1,cr);
        tree[p]=tree[p*2]+tree[p*2+1];
    }
}
long long shu(int l,int r,int p,int cl,int cr){
    if (cl>r || cr<l){
        return 0;
    }else if (cl>=l && cr<=r){
        return tree[p];
    }else{
        int mid=(cl+cr)/2;
        push(p,cr-cl+1);
        return shu(l,r,p*2,cl,mid)+shu(l,r,p*2+1,mid+1,cr);
    }
}
int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    jian(1,n,1);
    for (int i=1;i<=m;++i){
        int op,l,r,k;
        cin>>op;
        if (op==1){
            cin>>l>>r>>k;
            xiu(l,r,k,1,1,n);
        }else{
            cin>>l>>r;
            cout<<shu(l,r,1,1,n)<<endl;
        }
    }
}

by I_will_AKIOI @ 2024-01-06 16:47:32

tree数组开小了


by ikun_god @ 2024-01-06 16:58:12

谢谢,已关注


|