线段树板子全RE求调,目测数组大小无误

P3372 【模板】线段树 1

Yang818 @ 2023-10-20 19:13:24

#include<bits/stdc++.h>
#define F(_b,_e) for(int i=_b;i<=_e;i++)
#define int long long
using namespace std;

inline int read(){
    int f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return f*x;
}
void write(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int MAXN=2e5+5;
struct Seg_tree{
    int l,r;
    long long val,tag;
}t[MAXN<<2];
int a[MAXN],n,m; 

void build(int pos,int left,int right){
    t[pos].l=left;
    t[pos].r=right;
    if(left==right){
        t[pos].val=a[left];
        return;
    }
    int mid=(left+right)/2;
    build(pos*2,left,mid);
    build(pos*2+1,mid+1,right);
}

void spread_down(int pos){
    t[pos*2].tag=t[pos].tag;
    t[pos*2+1].tag=t[pos].tag;
    t[pos*2].val+=(t[pos*2].r-t[pos*2+1].l+1)*t[pos].tag;
    t[pos*2+1].val+=(t[pos*2+1].r-t[pos*2+1].l+1)*t[pos].tag;
    t[pos].tag=0;
} 

void modify(int pos,int left,int right,int delta){
    if(t[pos].l>=left && t[pos].r<=right){
        t[pos].val+=delta*(t[pos].r-t[pos].l+1);
        t[pos].tag+=delta;
        return;
    }
    int mid=(t[pos].l+t[pos].r)/2;
    if(left<=mid)   modify(pos*2,left,right,delta);
    if(right>mid)   modify(pos*2+1,left,right,delta);
    t[pos].val=t[pos*2].val+t[pos*2+1].val;
    return;
} 

int query(int pos,int left,int right){
    long long ans=0;
    if(t[pos].l>=left&&t[pos].r<=right)
        return t[pos].val;
    int mid=(t[pos].l+t[pos].r)/2;
    if(left<=mid)
        ans+=query(pos*2,left,right);
    if(right>mid)
        ans+=query(pos*2+1,left,right);
    return ans;
}

signed main(){
    //ios::sync_with_stdio(0);
    n=read();
    m=read();
    while(m--){
        int op=read();
        if(op==1){
            int l=read();
            int r=read();
            int d=read();
            modify(1,l,r,d);
        }
        if(op==2){
            int l=read();
            int r=read();
            cout<<query(1,l,r)<<endl;
        }
    }
    return 0;
}

by 半只蒟蒻 @ 2023-10-20 19:20:54

build 函数里面也要 pushup (即用两个儿子节点的信息更新父亲节点的信息)

对应的就是你代码里面的这行: t[pos].val=t[pos*2].val+t[pos*2+1].val;


by Nobelium_255 @ 2023-10-20 19:21:17

你查询没有下传懒标记


by 半只蒟蒻 @ 2023-10-20 19:21:32

@jeffstart lz 是八倍空间啊,没问题


by 半只蒟蒻 @ 2023-10-20 19:22:14

@Nobelium_255 可能modify的时候也得推标记?我不确定


by Nobelium_255 @ 2023-10-20 19:22:47

哦,收回上句话。应该是你完全没有下传过懒标记


by Nobelium_255 @ 2023-10-20 19:23:24

@半只蒟蒻 都得推,我刚刚没看见


by 半只蒟蒻 @ 2023-10-20 19:23:42

而且这个标记下推感觉写的怪怪的

t[pos*2].val+=(t[pos*2].r-t[pos*2+1].l+1)*t[pos].tag;

应为

t[pos*2].val+=(t[pos*2].r-t[pos*2].l+1)*t[pos].tag;


by Nobelium_255 @ 2023-10-20 19:24:57

@半只蒟蒻 只能说乍一看好像挺正常,细细看全是问题


by 半只蒟蒻 @ 2023-10-20 19:26:00

而且可能区间修改的参数 d 也得开成 long long 类型的,毕竟题目没有明确说明


by 半只蒟蒻 @ 2023-10-20 19:26:48

@半只蒟蒻 query 函数的返回类型改成 long long


| 下一页