救救孩子吧,20分实在改不出来了

P1253 扶苏的问题

INTP_A @ 2024-11-26 20:54:45

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,maxn=-1e18-1,a[2000010];
struct node{
    int sum,add;
    bool g=false;
}c[8000010];
void pushup(int k){
    c[k].sum=max(c[k<<1].sum,c[k<<1|1].sum);
    return;
}
void build(int k,int l,int r){
    if(l==r){
        c[k].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    pushup(k);
    return;
}
void pushdown(int k){
    if(c[k].g){
        c[k].add=0;
        c[k].g=0;
        c[k<<1].add=0;
        c[k<<1].sum=c[k].sum;
        c[k<<1].g=true;
        c[k<<1|1].add=0;
        c[k<<1|1].sum=c[k].sum;
        c[k<<1|1].g=true;
        return;
    }
    c[k<<1].add+=c[k].add;
    c[k<<1].sum+=c[k].add;
    c[k<<1|1].add+=c[k].add;
    c[k<<1|1].sum+=c[k].add;
    c[k].add=0;
    pushup(k);
    return;
}
void ope1(int k,int l,int r,int x,int y,int ll){
    if(l>y||r<x)return;
    if(l>=x&&r<=y){
        c[k].add+=ll;
        c[k].sum+=ll;
        return;
    }
    pushdown(k);
    int mid=(l+r)>>1;
    ope1(k<<1,l,mid,x,y,ll);
    ope1(k<<1|1,mid+1,r,x,y,ll);
    pushup(k);
    return;
}
void ope2(int k,int l,int r,int x,int y,int oo){
    if(l>y||r<x)return;
    if(l>=x&&r<=y){
        c[k].add=0;
        c[k].sum=oo;
        c[k].g=true;
        return;
    }
    pushdown(k);
    int mid=(l+r)>>1;
    ope2(k<<1,l,mid,x,y,oo);
    ope2(k<<1|1,mid+1,r,x,y,oo);
    pushup(k);
    return;
}
void chaxun(int k,int l,int r,int x,int y){
    if(l>y||r<x)return;
    if(l>=x&&r<=y){
        maxn=max(maxn,c[k].sum);
        return;
    }
    int mid=(l+r)>>1;
    chaxun(k<<1,l,mid,x,y);
    chaxun(k<<1|1,mid+1,r,x,y);
    return;
}
signed main(){
    cin>>n>>m;
    int op,l,r,x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>op;
        if(op==1){
            cin>>l>>r>>x;
            ope2(1,1,n,l,r,x);
        }else if(op==2){
            cin>>l>>r>>x;
            ope1(1,1,n,l,r,x);
        }else{
            cin>>l>>r;
            chaxun(1,1,n,l,r);
            cout<<maxn<<endl;
            maxn=-1e18-1;
        }
    }
    return 0;
}

20分真的调不出来了


by zzz13579zzz @ 2024-11-26 20:59:10

区间修改为什么sum直接等于修改值?


by wjr_jok @ 2024-11-26 21:04:50

@INTP_A 对啊你改的是个区间欸


by INTP_A @ 2024-11-26 21:43:52

因为sum里存的是区间最大值啊,如果把整个区间修改,不就相当于修改值就是最大值吗@wjr_jok@zzz13579zzz


by wjr_jok @ 2024-11-26 21:45:03

@INTP_A 所以记录加法的是 add


by zzz13579zzz @ 2024-11-26 21:51:58

push_down里面不用清空加标记,不然下传不了@@INTP_A


by zzz13579zzz @ 2024-11-26 21:52:47

就是下传修改标记的时候


by wjr_jok @ 2024-11-26 22:01:53

wc什么四不像线段树啊


by INTP_A @ 2024-11-27 15:12:17

@wjr_jok 刚学线段树写的确实抽象QWQ


by INTP_A @ 2024-11-27 15:20:27

才看到查询函数没写pushdown,此贴已结。谢谢两位大佬


|