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 23:27:04

@l_dddddd不对,不只是改了这个,不知道改了什么ac 了

by FireFly620 @ 2024-11-30 10:53:36

@QQzhi

我也是按您的下放规则来做的，为什么也是50pts?

望解答。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int M,n,m,dep;
int tr[N<<2],sum[N<<2],cov[N<<2];
inline int r(){
    int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;
}
void covdown(int p){
    if(cov[p]!=-1145144747){
        sum[p<<1|1]=sum[p<<1]=0;
        tr[p<<1|1]=tr[p<<1]=cov[p];
        cov[p<<1|1]=cov[p<<1]=cov[p];
        cov[p]=-1145144747;
    }
}
void sumdown(int p){
    if(sum[p]){
        covdown(p);
        tr[p<<1|1]+=sum[p];
        tr[p<<1]+=sum[p];
        sum[p<<1|1]+=sum[p];
        sum[p<<1]+=sum[p];
        sum[p]=0;
    }
}
inline void pushdown(int p,int k){
    k>>=1;
    covdown(p);
    sumdown(p);
}
inline void maintain(int p){
    tr[p]=max(tr[p<<1],tr[p<<1|1]);
}
inline void update1(int s,int t,int k){
    int num=1;
    s+=M-1;t+=M+1;
    for(int i=dep;i;--i){
        pushdown(s>>i,1<<i);
        pushdown(t>>i,1<<i);
    }
    while(s^1^t){
        if(~s&1)tr[s^1]+=k,sum[s^1]+=k;
        if(t&1)tr[t^1]+=k,sum[t^1]+=k;
        s>>=1;t>>=1;num<<=1;
        maintain(s);
        maintain(t); 
    }
    for(s>>=1;s;s>>=1)maintain(s);
}
inline void update2(int s,int t,int k){
    int num=1;
    s+=M-1;t+=M+1;
    for(int i=dep;i;--i){
        pushdown(s>>i,1<<i);
        pushdown(t>>i,1<<i);
    }
    while(s^1^t){
        if(~s&1){
            tr[s^1]=cov[s^1]=k;
            sum[s^1]=0;
        }
        if(t&1){
            tr[t^1]=cov[t^1]=k;
            sum[t^1]=0;
        }
        s>>=1;t>>=1;num<<=1;
        maintain(s);
        maintain(t); 
    }
    for(s>>=1;s;s>>=1)maintain(s);
}
inline int query(int s,int t){
    s+=M-1;t+=M+1;
    for(int i=dep;i;--i){
        pushdown(s>>i,1<<i);
        pushdown(t>>i,1<<i);
    }
    int res=-1145144747;
    while(s^t^1){
        if(~s&1)res=max(res,tr[s^1]);
        if(t&1)res=max(res,tr[t^1]);
        s>>=1;t>>=1;
    }
    return res;
}
signed main(){
    n=r();m=r();
    for(M=1;M<=n;M<<=1)dep++;
    for(int i=1;i<=n;++i){
        tr[i+M]=r();
        cov[i+M]=-1145144747;
    }
    for(int i=M-1;i;--i){
        maintain(i);
        cov[i]=-1145144747;
    }
    while(m--){
        int f=r(),x=r(),y=r(),k;
        if(f==1){
            k=r();
            update2(x,y,k);
        }
        else if(f==2){
            k=r();
            update1(x,y,k);
        }else cout<<query(x,y)<<endl;
    }
    return 0;
}