求助:区间修改出问题了

P3372 【模板】线段树 1

yangjunhan1 @ 2023-05-26 13:31:12

#include<bits/stdc++.h>
using namespace std;
int n,a[500000],lazy[200000],t[200000],fl,fr,v,m,q;
void build(int l,int r,int ro){//建树 
    if(l==r){//最小节点,返回值 
        t[ro]=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,ro*2);
    build(mid+1,r,ro*2+1);//左右子树 
    t[ro]=t[ro*2]+t[ro*2+1];
} 
int gs(int l,int r,int ro){//区间求和 
    if(fl<=l && r<=fr)  return t[ro];//完全包含,直接返回 
    int mid=l+r>>1,s=0;
    if(fl<=mid) s+=gs(l,mid,ro*2);//与左子树有关 
    if(fr>mid)  s+=gs(mid+1,r,ro*2+1);//与右子树有关; 
    return s;
}
void qjxg(int l,int r,int ro){//区间修改(加上v) 
    if(fl<=l && r<=fr){//完全属于,直接加 
        t[ro]=(r-l+1)*v,lazy[ro]+=v;
        return ;
    }
    int mid=l+r>>1;
    if(lazy[ro]){//懒标记还在
        t[ro*2]+=lazy[ro]*(mid-l+1),lazy[ro*2]+=lazy[ro];//左子树值加v,懒标记传递 
        t[ro*2+1]+=lazy[ro]*(r-mid),lazy[ro*2+1]+=lazy[ro];//右子树…… 
        lazy[ro]=0;//懒标记归零 
    }
    if(fl<=mid) qjxg(l,mid,ro*2);
    if(fr>mid)  qjxg(mid+1,r,ro*2+1);
    t[ro]=t[ro*2]+t[ro*2+1];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    build(1,n,1);
    while(m--){
        scanf("%d %d %d",&q,&fl,&fr);
        if(q==1){
            scanf("%d",&v);
            qjxg(1,n,1);
        }
        else    cout<<gs(1,n,1)<<endl;
        memset(lazy,0,sizeof(lazy));
    }
    return 0;
}

by Nwayy @ 2023-05-26 13:47:30

@yangjunhan1 区间修改是 +=,其次 gs 函数里也要 pushdown


by yangjunhan1 @ 2023-05-26 13:48:59

@winds888 pushdown是什么意思?


by Nwayy @ 2023-05-26 14:12:16

@yangjunhan1 标记下放,也就是你的lazy


by yangjunhan1 @ 2023-05-26 14:14:14

@winds888 哦,可是我现在加了,还是有问题


by Nwayy @ 2023-05-26 14:16:50

@yangjunhan1 再重申一次哈,问题如下:

  1. 懒标记在 gs 函数里也要下放;

  2. 区间加那里是 +=;

  3. 开 long long


by yangjunhan1 @ 2023-05-26 14:21:19

@winds888 哦,谢谢,现在应该没问题了


|