70pts wa求条

P3372 【模板】线段树 1

sadly_shark @ 2024-08-11 11:39:13

WA#8,#9,#10三个点,代码如下,玄关

#include<bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
using namespace std;
struct node{
    int l;
    int r;
    int lazy;
    int sum;
}tr[400010];
long long a[100010],n,m,op,x,y,k;

void putup(int p){
    tr[p].sum=tr[ls].sum+tr[rs].sum; 
    return;
}

void putdown(int p){
    if(tr[p].lazy){
        tr[ls].lazy+=tr[p].lazy;
        tr[rs].lazy+=tr[p].lazy;
        tr[ls].sum+=(tr[ls].r-tr[ls].l+1)*tr[p].lazy;
        tr[rs].sum+=(tr[rs].r-tr[rs].l+1)*tr[p].lazy;
        tr[p].lazy=0;
    }
    return;
}
void xiugai(int left,int right,int kk,int p=1){
    if(tr[p].l>=left&&tr[p].r<=right){
        tr[p].lazy+=kk;
        tr[p].sum+=(tr[p].r-tr[p].l+1)*kk;
        return;
    }
    putdown(p);
    if(left<=tr[ls].r)xiugai(left,right,kk,ls);
    if(right>=tr[rs].l)xiugai(left,right,kk,rs);
    putup(p);
}

long long qiuhe(int left,int right,int p=1){
    if(tr[p].l>=left&&tr[p].r<=right)return tr[p].sum;
    putdown(p);
    long long ans=0;
    if(left<=tr[ls].r)ans+=qiuhe(left,right,ls);
    if(right>=tr[rs].l)ans+=qiuhe(left,right,rs);
    return ans;
}

void build(int left,int right,int p=1){
    tr[p].l=left;
    tr[p].r=right;
    if(tr[p].l==tr[p].r){
        tr[p].sum=a[left];
        return;
    }
    int mid=(left+right)>>1;
    build(left,mid,ls);
    build(mid+1,right,rs);
    putup(p);
}

int main(){
    //freopen("in.in","r",stdin); 
    //freopen("solution.out","w",stdout); 

    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,n);
    while(m--){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            xiugai(x,y,k);
        }
        else{
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",qiuhe(x,y));
        }
    }

    return 0;
}

by Error_Eric @ 2024-08-11 11:42:11

long long qiuhe(int left,int right,int p=1){
    if(tr[p].l>=left&&tr[p].r<=right)return tr[p].sum;
    putdown(p);

putdown 再返回 sum


by Error_Eric @ 2024-08-11 11:46:01

@sadly_shark 而且你 qiuhe 如果到了叶子节点岂不是一定返回 0 了。

if(tr[p].l == tr[p].r) return tr[p].sum;


by sadly_shark @ 2024-08-11 13:34:09

破案了,其实是node定义里lazy和sum没开long long(见祖宗了)


by sadly_shark @ 2024-08-11 13:34:43

@Error_Eric 已关,请查收


|