WA 20 求助

qwq___qaq @ 2021-12-24 00:10:40

#include<bits/stdc++.h>
#define int long long
#define ls k<<1
#define rs k<<1|1
#define inf -1e14
using namespace std;
const int maxn=1e6+5;
int n,m,a[maxn],add[maxn<<2],num[maxn<<2],up[maxn<<2];
inline int read(){
    int res=0,f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9'){
        res=(res<<1)+(res<<3)+(ch^'0');
        ch=getchar();
    }
    return f?-res:res;
}
void Build(int k,int l,int r){
    up[k]=inf;
    if(l==r){
        num[k]=a[l];
        return;
    }
    int mid=l+r>>1;
    Build(ls,l,mid);
    Build(rs,mid+1,r);
    num[k]=max(num[ls],num[rs]);
}
void pushdown(int k){
    if(add[k]){
        num[ls]+=add[k];
        num[rs]+=up[k];
        add[ls]+=add[k];
        add[rs]+=add[k];
        up[ls]=up[rs]=inf;
        add[k]=0;
    }
}
void modify(int k,int l,int r,int x,int y,int v){
    if(l>=x&&r<=y){
        num[k]+=v;
        up[k]=inf;
        add[k]+=v;
        return;
    }
    int mid=l+r>>1;
    pushdown(k);
    if(x<=mid) modify(ls,l,mid,x,y,v);
    else modify(rs,mid+1,r,x,y,v);
    num[k]=max(num[ls],num[rs]);
}
void Pushdown(int k){
    if(up[k]!=inf){
        num[ls]=up[k];
        num[rs]=up[k];
        add[ls]=add[rs]=0;
        up[ls]=up[rs]=up[k];
        up[k]=inf;
    }
}
void Modify(int k,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y){
        num[k]=v;
        up[k]=v;
        add[k]=0;
        return;
    }
    int mid=l+r>>1;
    Pushdown(k);
    if(x<=mid)
        Modify(ls,l,mid,x,y,v);
    if(y>mid)
        Modify(rs,mid+1,r,x,y,v);
    num[k]=max(num[ls],num[rs]);
}
int query(int k,int l,int r,int x,int y){
    if(l>=x&&r<=y)
        return num[k];
    int mid=l+r>>1,res=inf;
    pushdown(k);
    Pushdown(k);
    if(x<=mid)
        res=max(res,query(ls,l,mid,x,y));
    if(mid<y)
        res=max(res,query(rs,mid+1,r,x,y));
    return res;
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    Build(1,1,n);
    while(m--){
        int op=read(),b=read(),c=read();
        if(op==1)
            Modify(1,1,n,b,c,read());
        else if(op==2)
            modify(1,1,n,b,c,read());
        else
            printf("%lld\n",query(1,1,n,b,c));
    }
    return 0;
}

by qwq___qaq @ 2021-12-24 00:11:05

两个样例都过了，但是 20 分。

by OldVagrant @ 2021-12-24 07:34:21

@_sto_pengzijunorz 为啥你下传加法标记要把两个儿子的强转标记都清空？

by OldVagrant @ 2021-12-24 07:36:28

@_sto_pengzijunorz 再说你强转标记肯定要比加法标记先下传啊，你这样会导致左右儿子就直接被强转了，就算父亲有加法标记也没用

by OldVagrant @ 2021-12-24 07:37:58

你区间加也不能清空强转标记啊
你这能有20分说明有两个点是样例

by OldVagrant @ 2021-12-24 07:39:06

区间修改的时候无论哪一种修改都要把两个标记往下传，只传一个不行

by OldVagrant @ 2021-12-24 07:45:33

还有你修改不能加else，加了else就少了一种情况，少修改一部分区间

by __zzy__ @ 2021-12-24 07:50:50

你pushdown的时候为啥要给左右儿子的最大值加上强转标记的值？应该加上加法标记的值啊

by qwq___qaq @ 2021-12-24 23:32:14

@z_z_y 改了改，现在 60：

#include<bits/stdc++.h>
#define int long long
#define ls k<<1
#define rs k<<1|1
#define inf -1e14
using namespace std;
const int maxn=1e6+5;
int n,m,a[maxn],add[maxn<<2],num[maxn<<2],up[maxn<<2];
namespace Tree{
    inline int read(){
        int res=0,f=0;
        char ch=getchar();
        while(ch<'0'||ch>'9')
            f|=(ch=='-'),ch=getchar();
        while(ch>='0'&&ch<='9'){
            res=(res<<1)+(res<<3)+(ch^'0');
            ch=getchar();
        }
        return f?-res:res;
    }
    void Build(int k,int l,int r){
        up[k]=inf;
        if(l==r){
            num[k]=a[l];
            return;
        }
        int mid=l+r>>1;
        Build(ls,l,mid);
        Build(rs,mid+1,r);
        num[k]=max(num[ls],num[rs]);
    }
    void pushdown(int k){
        if(add[k]){
            num[ls]+=add[k];
            num[rs]+=add[k];
            add[ls]+=add[k];
            add[rs]+=add[k];
            add[k]=0;
        }
    }
    void modify(int k,int l,int r,int x,int y,int v){
        if(l>=x&&r<=y){
            num[k]+=v;
            add[k]+=v;
            return;
        }
        int mid=l+r>>1;
        pushdown(k);
        if(x<=mid)
            modify(ls,l,mid,x,y,v);
        if(y>mid)
            modify(rs,mid+1,r,x,y,v);
        num[k]=max(num[ls],num[rs]);
    }
    void Pushdown(int k){
        if(up[k]!=inf){
            num[ls]=up[k];
            num[rs]=up[k];
            up[ls]=up[rs]=up[k];
            up[k]=inf;
            add[k]=0;
        }
    }
    void P(int k){
        if(up[k]!=inf){
            num[ls]=up[k];
            num[rs]=up[k];
            up[ls]=up[rs]=up[k];
            up[k]=inf;
        }
    }
    void Modify(int k,int l,int r,int x,int y,int v){
        if(x<=l&&r<=y){
            num[k]=v;
            up[k]=v;
            add[k]=0;
            return;
        }
        int mid=l+r>>1;
        Pushdown(k);
        if(x<=mid)
            Modify(ls,l,mid,x,y,v);
        if(y>mid)
            Modify(rs,mid+1,r,x,y,v);
        num[k]=max(num[ls],num[rs]);
    }
    int query(int k,int l,int r,int x,int y){
        if(l>=x&&r<=y)
            return num[k];
        int mid=l+r>>1,res=inf;
        P(k);
        pushdown(k);
        if(x<=mid)
            res=max(res,query(ls,l,mid,x,y));
        if(mid<y)
            res=max(res,query(rs,mid+1,r,x,y));
        return res;
    }
}
using namespace Tree;
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    Build(1,1,n);
    while(m--){
        int op=read(),b=read(),c=read();
        if(op==1)
            Modify(1,1,n,b,c,read());
        else if(op==2)
            modify(1,1,n,b,c,read());
        else
            printf("%lld\n",query(1,1,n,b,c));
    }
    return 0;
}

by OldVagrant @ 2021-12-25 07:54:54

@_sto_pengzijunorz 你没照我说的改完啊，区间加之后是先下传强转标记再下传加法标记，你只下传了加法标记

by OldVagrant @ 2021-12-25 07:56:16

区间覆盖和查询的时候也是先下传强转标记再下传加法标记，下传强转标记的时候要把左右儿子的加法标记都清空