重调线段树还是RE

IaLWH @ 2024-08-07 19:54:33

#include<cstdio>
#define int long long
#define lc i<<1
#define rc i<<1|1
#define fc i>>1
int n,m,data[114514],tree[458056],lazy[458056];

void build(int i,int l,int r){
    if(l==r){
        tree[i]=data[l];
        return;
    }
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tree[i]=tree[lc]+tree[rc];
}
inline void add(int i,int l,int r,int v){
    lazy[i]+=v;
    tree[i]+=v*(r-l+1);
}
inline void pushdown(int i,int l,int r,int mid){
    if(!lazy[i])
        return;
    add(lc,l,mid,lazy[i]);
    add(rc,mid+1,r,lazy[i]);
    lazy[i]=0;
}
int query(int i,int l,int r,int L,int R){
            //[l,r]当前区间 
    if(l>L&&r<=R)
        return tree[i];
    int mid=l+r>>1;
    int ans=0;
    pushdown(i,l,r,mid);
    if(L<=mid)ans+=query(lc,l,mid,L,R);
    if(R>mid)ans+=query(rc,mid+1,r,L,R);
    return ans;
}
void change(int i,int l,int r,int L,int R,int v){
    if(l>L&&r<=R){
        add(i,l,r,v);
        return;
    }
    int mid=l+r>>1;
    pushdown(i,l,r,mid);
    if(L<=mid)change(lc,l,mid,L,R,v);
    if(R>mid)change(rc,mid+1,r,L,R,v);
    tree[i]=tree[lc]+tree[rc];
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%lld",data+i);
    build(1,1,n);
    int com,x,y,k;
    while(m--){
        scanf("%lld",&com);
        if(com==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            change(1,1,n,x,y,k);
        }else{
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

by EityDawn @ 2024-08-07 20:00:49

@IaLWH 确定区间都带 =,随便一个单点修或查都会 Re

#include<cstdio>
#define int long long
#define lc i<<1
#define rc i<<1|1
#define fc i>>1
int n,m,data[114514],tree[458056],lazy[458056];

void build(int i,int l,int r){
    if(l==r){
        tree[i]=data[l];
        return;
    }
    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tree[i]=tree[lc]+tree[rc];
}
inline void add(int i,int l,int r,int v){
    lazy[i]+=v;
    tree[i]+=v*(r-l+1);
}
inline void pushdown(int i,int l,int r,int mid){
    if(!lazy[i])
        return;
    add(lc,l,mid,lazy[i]);
    add(rc,mid+1,r,lazy[i]);
    lazy[i]=0;
}
int query(int i,int l,int r,int L,int R){
            //[l,r]当前区间 
    if(l>=L&&r<=R)//这里
        return tree[i];
    int mid=l+r>>1;
    int ans=0;
    pushdown(i,l,r,mid);
    if(L<=mid)ans+=query(lc,l,mid,L,R);
    if(R>mid)ans+=query(rc,mid+1,r,L,R);
    return ans;
}
void change(int i,int l,int r,int L,int R,int v){
    if(l>=L&&r<=R){//这里
        add(i,l,r,v);
        return;
    }
    int mid=l+r>>1;
    pushdown(i,l,r,mid);
    if(L<=mid)change(lc,l,mid,L,R,v);
    if(R>mid)change(rc,mid+1,r,L,R,v);
    tree[i]=tree[lc]+tree[rc];
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%lld",data+i);
    build(1,1,n);
    int com,x,y,k;
    while(m--){
        scanf("%lld",&com);
        if(com==1){
            scanf("%lld%lld%lld",&x,&y,&k);
            change(1,1,n,x,y,k);
        }else{
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(1,1,n,x,y));
        }
    }
    return 0;
}

by EityDawn @ 2024-08-07 20:02:49

@IaLWH 还有就是，你的线段树下标从 1 开始，那么你的 data 数组下标也因从 1 开始

by IaLWH @ 2024-08-07 20:12:27

@hgzx__lc 调了两天终于过了！谢谢