萌新刚学OI求调全RE线段树

P3372 【模板】线段树 1

IaLWH @ 2024-08-06 20:28:34

写完后代码太乱看不出问题力(悲

#include<stdio.h>
#define ll long long
struct node{
    ll sum,lazy;
    int l,r;
}tree[114514<<2];

ll data[114514];
int n,m;

inline void build(int i,int l,int r){
    tree[i].l=l;
    tree[i].r=r;
    if(l==r){
        tree[i].sum=data[i];
        return;
    }
    ll mid=l+r>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    tree[i].sum=tree[i<<1].sum+tree[(i<<1)+1].sum;
}
inline void plus(int l,int r,ll c,int L,int R,int i){
        //[l,r]+c changing  [L,R]node including i index now
    if(l<=L&&r>R){
        tree[i].sum+=(R-L+1)*c;   //屯好所有子节点的数 
        tree[i].lazy+=c;          //懒标记 
        return;
    }
    ll mid=L+R>>1;
    if(tree[i].lazy&&L!=R){     //懒标记非空且非叶节点 
        tree[i<<1].sum+=tree[i].lazy*(mid-L+1);//左边加上数 
        tree[i<<1|1].sum+=tree[i].lazy*(R-mid);//右边加上数 
        tree[i<<1].lazy+=tree[i].lazy;
        tree[i<<1|1].lazy+=tree[i].lazy;       //左右传下懒标记 
        tree[i].lazy=0;    //clear lazy mark
    }
    if(l<=mid)
        plus(l,r,c,L,m,i<<1);
    if(r>mid)
        plus(l,r,c,mid+1,R,i<<1|1);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;  //merge
}
ll search(int l,int r,int L,int R,int i){
    if(l<=L&&r>R)
        return tree[i].sum;
    ll mid=L+R>>1;
    if(tree[i].lazy){
        tree[i<<1].sum+=tree[i].lazy*(mid-L+1);
        tree[i<<1|1].sum+=tree[i].lazy*(R-mid);//右边加上数 
        tree[i<<1].lazy+=tree[i].lazy;
        tree[i<<1|1].lazy+=tree[i].lazy;       //左右传下懒标记 
        tree[i].lazy=0;    //clear lazy mark
    }
    ll t;
    if(l<=mid)
        t=search(l,r,L,mid,i<<1);
    if(r>mid)
        t+=search(l,r,mid+1,R,i<<1|1);
    return t;
}
int main(){
    char command;
    int x,y;
    ll k;
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%lld",data+i);
    build(1,1,n);
    for(int i=0;i<m;i++){
        command=getchar();
        if(command==49){
            scanf("%d%d%lld",&x,&y,&k);
            plus(x,y,k,1,n,1);
        }else{
            scanf("%d%d",&x,&y);
            printf("%lld\n",search(x,y,1,n,1));
        }
    }
    return 0;
}

by Error_Eric @ 2024-08-06 20:43:10

@IaLWH 首先你存储线段端点和计算线段端点的做法混合写是什么风格,其次 plus(l,r,c,L,m,i<<1); 里面的 m 又是什么东西(


by IaLWH @ 2024-08-06 20:51:15

@Error_Eric 嗯混合写指得具体是什么不太明白


by zhaobingjun2010 @ 2024-08-06 20:52:14

@ IaLWH

inline void build(int i,int l,int r){
    tree[i].l=l;
    tree[i].r=r;
    if(l==r){
        tree[i].sum=data[i];//应该是tree[i].sum=data[l].
        return;
    }

要注意tree线段树存的是区间数据, l 和 r 才是对应数组中的地址(关注一下)


by zhaobingjun2010 @ 2024-08-06 20:52:51

@IaLWH


by IaLWH @ 2024-08-06 20:56:49

@zhaobingjun2010 哦哦好的,谢谢


by zhaobingjun2010 @ 2024-08-06 21:01:03

@IaLWH

建议你单独写一个函数用来打懒标记
要不然太乱了


by Error_Eric @ 2024-08-06 21:56:43

@IaLWH 一般情况下 struct 里面没有存储 l,r 才需要在 plus() 里面动态计算 L,R。 你看你初始化 tree[i].l 后面有用过吗。


by _lxc__ @ 2024-08-07 09:09:00

这题用一维前缀和会更方便一些吧


|