60pts 的同学们看这里 / pushdown 问题提醒

QQzhi @ 2024-11-27 12:55:26

void pushdown(int id){
  if (tt[id]<+oo){
    tt[id*2]=tt[id*2+1]=tt[id];
    t[id*2]=t[id*2+1]=0;
    a[id*2]=a[id*2+1]=tt[id];
    tt[id]=+oo;
  }else{
    t[id*2]+=t[id];
    t[id*2+1]+=t[id];
    a[id*2]+=t[id];
        a[id*2+1]+=t[id];
    t[id]=0;
  }
}

void pushdown(int id){
    if (tt[id]<+oo){
        tt[id*2]=tt[id*2+1]=tt[id];
        t[id*2]=t[id*2+1]=0;
        a[id*2]=a[id*2+1]=tt[id];
        tt[id]=+oo;
    }
  t[id*2]+=t[id];
  t[id*2+1]+=t[id];
  a[id*2]+=t[id];
  a[id*2+1]+=t[id];
  t[id]=0;
}

by l_dddddd @ 2024-11-27 22:44:07

60分求调

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q,mod;
struct node{
    int lz,val,ml;
};
node tr[1000005*4];
int a[1000005];
void pushup(int rt){
    tr[rt].val=max(tr[rt<<1].val,tr[rt<<1|1].val);
}
void build(int l,int r,int rt){
    tr[rt].ml=-1e18;
    if(l==r){
        tr[rt].val=a[l];
        return ;
    }
    int m=l+r>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void pushdown(int rt){
    if(tr[rt].ml!=-1e18){
        tr[rt<<1].ml=tr[rt].ml;
        tr[rt<<1].val=tr[rt].val;
        tr[rt<<1].lz=0;

        tr[rt<<1|1].lz=0;
        tr[rt<<1|1].ml=tr[rt].ml;
        tr[rt<<1|1].val=tr[rt].ml;
        tr[rt].ml=-1e18;
    }

        tr[rt<<1].lz+=tr[rt].lz;
        tr[rt<<1].val+=tr[rt].lz;

        tr[rt<<1|1].lz+=tr[rt].lz;
        tr[rt<<1|1].val+=tr[rt].lz;
        tr[rt].lz=0;
}

void update(int L,int R,int x,int l,int r,int rt){
    if(L<=l&&r<=R){
        tr[rt].lz+=x;
        tr[rt].val+=x;
        return ;
    }
    int m=l+r>>1;

    pushdown(rt);
    if(m>=L)
    update(L,R,x,l,m,rt<<1);
    if(R>m)
    update(L,R,x,m+1,r,rt<<1|1);
    pushup(rt);
}
void chan(int L,int R,int x,int l,int r,int rt){
     if(L<=l&&r<=R){
        tr[rt].lz=0;
        tr[rt].ml=x;
        tr[rt].val=x;
        return ;
    }
    int m=l+r>>1;
    pushdown(rt);
    if(m>=L)
    chan(L,R,x,l,m,rt<<1);
    if(R>m)
    chan(L,R,x,m+1,r,rt<<1|1);

}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R) return tr[rt].val;
    if(l>R||L>r) return -1e18;
    int m=l+r>>1;

    pushdown(rt);
    return max(query(L,R,l,m,rt<<1),query(L,R,m+1,r,rt<<1|1));
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,n,1);

    while(q--){
        int c;cin>>c;
        if(c==1){
            int x,y,k;cin>>x>>y>>k;
            chan(x,y,k,1,n,1);
        }
        else if(c==2){
            int x,y,k;cin>>x>>y>>k;
            update(x,y,k,1,n,1);
        }
        else{
            int l,r;cin>>l>>r;
            cout<<query(l,r,1,n,1)<<'\n';
        }
    }

}

by weiyiqian @ 2024-11-27 22:46:17

@QQzhi 大佬能说说为什么吗
修改赋值标记的时候会清空加标记，修改加标记的前提是没有赋值标记，那为什么会存在既有赋值标记又有加标记的情况呢？求大佬解答

by weiyiqian @ 2024-11-27 22:51:41

@l_dddddd 你的chan()好像没加pushup

by l_dddddd @ 2024-11-27 22:55:17

@weiyiqian加了还是60

by QQzhi @ 2024-11-27 22:56:40

@weiyiqian

我这里采用的的是：

1. 修改时，覆盖原修改标记，加法标记置零。
2. 加法时，直接加上加法tag。
3. 因为查询或者等等原因需要下到下一级之际pushdown，次序应当是先处理修改再按正常逻辑加上tag。

附本人的记录供参（得先把分数提到80pts可见源码）：https://www.luogu.com.cn/record/191385543

by QQzhi @ 2024-11-27 23:09:32

@l_dddddd 跑出RE+TLE来了，看看各处细节对了没有（

by l_dddddd @ 2024-11-27 23:12:28

@QQzhi tle可能是没开快读

by l_dddddd @ 2024-11-27 23:18:16

@QQzhi 好了,打错个字了

by l_dddddd @ 2024-11-27 23:20:18

tr[rt<<1].val=tr[rt].val;写成tr[rt<<1].val=tr[rt].ml了，看样子是写昏头了

by weiyiqian @ 2024-11-27 23:24:32

@QQzhi 我好像悟了，感谢大佬解答