10pts求条（玄关）

P1253 扶苏的问题

AlanFong @ 2024-08-23 16:23:32

rt
下载数据在本地跑没有问题，到了洛谷上就MLE/TLE

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r,laz1,laz2,max;
};
node tree[4000005];
int a[1000005];
int upd(int p)
{
    tree[p].l=tree[2*p].l;
    tree[p].r=tree[2*p+1].r;
    tree[p].max=max(tree[2*p].max,tree[2*p+1].max);
}
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree[p].l=l;
        tree[p].r=r;
        tree[p].max=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    upd(p);
}
void pushd(int p)
{
    if(tree[p].laz1!=0)
    {
        tree[2*p].laz1=tree[p].laz1;
        tree[2*p+1].laz1=tree[p].laz1;
        tree[2*p].max=tree[p].laz1;
        tree[2*p+1].max=tree[p].laz1;
    }
    else{
        if(tree[2*p].laz1!=0)
        {
            tree[2*p].laz1+=tree[p].laz2;
            tree[2*p].max+=tree[p].laz2;
        }else{
            tree[2*p].laz2+=tree[p].laz2;
            tree[2*p].max+=tree[p].laz2;
        }
        if(tree[2*p+1].laz1!=0)
        {
            tree[2*p+1].laz1+=tree[p].laz2;
            tree[2*p+1].max+=tree[p].laz2;
        }else{
            tree[2*p+1].laz2+=tree[p].laz2;
            tree[2*p+1].max+=tree[p].laz2;
        }
    }
    tree[p].laz2=0;
    tree[p].laz1=0;
}
void cover(int p,int l,int r,int x)
{
    if(l>r)
    {
        return;
    }
    if(tree[p].l==l&&tree[p].r==r)
    {
        tree[p].laz1=x;
        tree[p].laz2=0;
        tree[p].max=x;
        return;
    }
    if(tree[p].laz1!=0||tree[p].laz2!=0)
    {
        pushd(p);
    }
    if(r<=tree[2*p].r)
    {
        cover(2*p,l,r,x);
    }else if(l>=tree[2*p+1].l)
    {
        cover(2*p+1,l,r,x);
    }else{
        cover(2*p,l,tree[2*p].r,x);
        cover(2*p+1,tree[2*p+1].l,r,x);
    }
    upd(p);
}
void change2(int p,int l,int r,int x)
{
    if(l>r)
    {
        return;
    }
    if(tree[p].l==l&&tree[p].r==r)
    {
        if(tree[p].laz1!=0)
        {
            tree[p].laz1+=x;
        }else{
            tree[p].laz2+=x;
        }
        tree[p].max+=x;
        return;
    }
    if(tree[p].laz1!=0||tree[p].laz2!=0)
    {
        pushd(p);
    }
    if(r<=tree[2*p].r)
    {
        change2(2*p,l,r,x);
    }else if(l>=tree[2*p+1].l)
    {
        change2(2*p+1,l,r,x);
    }else{
        change2(2*p,l,tree[2*p].r,x);
        change2(2*p+1,tree[2*p+1].l,r,x);
    }
    upd(p);
}
int search(int p,int l,int r)
{
    if(l==tree[p].l&&r==tree[p].r)
    {
        return tree[p].max;
    }
    if(tree[p].laz1!=0||tree[p].laz2!=0)
    {
        pushd(p);
    }
    if(r<=tree[2*p].r)
    {
        return search(2*p,l,r);
    }else if(l>=tree[2*p+1].l)
    {
        return search(2*p+1,l,r);
    }else{
        return max(search(2*p,l,tree[2*p].r),search(2*p+1,tree[2*p+1].l,r));
    }
}
signed main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            cover(1,l,r,x);
        }else if(op==2)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            change2(1,l,r,x);
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            cout<<search(1,l,r)<<endl;
        }
    }
    return 0;
}

by sunnycl @ 2024-08-23 19:33:56

你没开long long
你的样例2错了，原因是你的laz1的初始值为0，而样例中有修改为0的操作，建议设成无穷大

by sunnycl @ 2024-08-23 19:35:14

@AlanFong

by sunnycl @ 2024-08-23 19:40:07

你的码风有点抽象

by AlanFong @ 2024-08-23 19:42:45

laz是是否取反@sunnycl

by sunnycl @ 2024-08-23 19:46:18

是否取反是什么意思
我指的是laz1这个懒标记

by AlanFong @ 2024-08-23 20:00:47

哦，我弄混了

by Hog_Dawa_IOI @ 2024-08-23 20:32:57

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l,r;long long laz1,laz2,max;
};
node tree[4000005];
long long a[1000005];
void upd(int p)//没返回值不要加int
{
    tree[p].l=tree[2*p].l;
    tree[p].r=tree[2*p+1].r;//建议在build就记录好l和r的信息
    if(tree[p].l!=tree[p].r) tree[p].max=max(tree[2*p].max,tree[2*p+1].max);
    //如果本身不是叶子节点才读取儿子的信息，有的时候问题不大有的时候问题很大，建议以后都写上
}
void build(int p,int l,int r)
{
    if(l==r)
    {
        tree[p].l=l;
        tree[p].r=r;
        tree[p].max=a[l]+1000000000000005;//见主函数，后面细讲
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    upd(p);
}
void pushd(int p)
{
    if(tree[p].laz1) tree[2*p].max=tree[2*p+1].max=tree[2*p].laz1=tree[2*p+1].laz1=tree[p].laz1,
    tree[2*p].laz2=tree[2*p+1].laz2=tree[p].laz1=0;
    if(tree[p].laz2) tree[2*p].max+=tree[p].laz2,tree[2*p].laz2+=tree[p].laz2,tree[2*p+1].max+=tree[p].laz2,
    tree[2*p+1].laz2+=tree[p].laz2,tree[p].laz2=0;//你的pushdown抽象炸了，感觉你对优先级的理解都有点问题
    //在这里是cover的优先级大于add的优先级，但是在cover之后也是需要add的，要不然down不干净
    //注意这里的laz我给它设了0的初值，后面细讲，如果不用到后面的改法，这里是不能设0的
    /*if(tree[p].laz1!=0)
    {
        tree[2*p].laz1=tree[p].laz1;
        tree[2*p+1].laz1=tree[p].laz1;
        tree[2*p].max=tree[p].laz1;
        tree[2*p+1].max=tree[p].laz1;
    }
    else{
        if(tree[2*p].laz1!=0)
        {
            tree[2*p].laz1+=tree[p].laz2;
            tree[2*p].max+=tree[p].laz2;
        }else{
            tree[2*p].laz2+=tree[p].laz2;
            tree[2*p].max+=tree[p].laz2;
        }
        if(tree[2*p+1].laz1!=0)
        {
            tree[2*p+1].laz1+=tree[p].laz2;
            tree[2*p+1].max+=tree[p].laz2;
        }else{
            tree[2*p+1].laz2+=tree[p].laz2;
            tree[2*p+1].max+=tree[p].laz2;
        }
    }
    tree[p].laz2=0;
    tree[p].laz1=0;*/
}
void cover(int p,int l,int r,long long x)
{
// printf("%d %d %d %d\n",tree[p].l,tree[p].r,l,r);
pushd(p);
    if(l>r)//这句话有没有都一样
    {
        return;
    }if(r<tree[p].l||tree[p].r<l) return;
    if(tree[p].l>=l&&tree[p].r<=r)//不是哥们儿你这是纯粗心了吧
    {
        tree[p].laz1=x;
        tree[p].laz2=0;
        tree[p].max=x;
        return;
    }
    if(tree[p].laz1!=0||tree[p].laz2!=0)
    {
        pushd(p);
    }
    cover(p<<1,l,r,x),cover(p<<1|1,l,r,x);
    /*if(r<=tree[2*p].r)
    {
        cover(2*p,l,r,x);
    }if(l>=tree[2*p+1].l)//建议学习主流线段树写法，你这样有大错，万一2个都满足呢
    //我还是给你改成主流写法算了
    {
        cover(2*p+1,l,r,x);
    }*/
    upd(p);
}
void change2(int p,int l,int r,long long x)
{
pushd(p);
    /*if(l>r)//同上
    {
        return;
    }*/
    if(r<tree[p].l||tree[p].r<l) return;
    if(tree[p].l>=l&&tree[p].r<=r)//同上
    {
        /*if(tree[p].laz1!=0)
        {
            tree[p].laz1+=x;
        }else{
            tree[p].laz2+=x;
        }*/
        tree[p].laz2+=x;//这里也错了
        //结合上下文，laz1维护的是覆盖的标记，laz2维护的是加的标记，二者不要混用
        //直接laz2+=x就可以了
        tree[p].max+=x;
        return;
    }
    /*if(tree[p].laz1!=0||tree[p].laz2!=0)
    {
        pushd(p);
    }*/change2(p<<1,l,r,x),change2(p<<1|1,l,r,x);
    /*if(r<=tree[2*p].r)
    {
        change2(2*p,l,r,x);
    }if(l>=tree[2*p+1].l)
    {
        change2(2*p+1,l,r,x);
    }*///同上
    upd(p);
}
long long search(int p,int l,int r)
{
pushd(p);
    if(r<tree[p].l||tree[p].r<l) return -1;
    if(l<=tree[p].l&&r>=tree[p].r)//同上
    {
        return tree[p].max;
    }
    /*if(tree[p].laz1!=0||tree[p].laz2!=0)
    {
        pushd(p);
    }*/return max(search(p<<1,l,r),search(p<<1|1,l,r));
    /*if(r<=tree[2*p].r)
    {
        ans=max(ans, search(2*p,l,r));
    }if(l>=tree[2*p+1].l)
    {
        ans=max(ans,search(2*p+1,l,r));
    }return ans;*///同上
}
signed main()
{
    int n,q;scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(q--)
    {
        int op;
        scanf("%d",&op);
        if(op==1)
        {
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            cover(1,l,r,x+1000000000000005);
            //这里sunnycl也说过了，因为有负数，所以不能直接用0代表懒标记的初值
            //但是特判太麻烦怎么办？
            //可以对值域整体往上移，只需要对数字整体加上一个初值就可以了
            //但是不能单纯加上1e9，因为如果10^6次加法全是+1e9，那么最大值会变为1e15，所以我们需要整体平移1e15
            //此时需要开long long
        }else if(op==2)
        {
            long long l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            change2(1,l,r,x);
        }else{
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%lld\n",search(1,l,r)-1000000000000005);
        }
    }
    return 0;
}

by Hog_Dawa_IOI @ 2024-08-23 20:33:39

目前是RE 90pts，现在还在探究为什么会RE

by Hog_Dawa_IOI @ 2024-08-23 20:35:31

（哦我因故开完隐了，翻不到我代码抱歉）

by zhaomumu1218 @ 2024-08-23 20:42:17


#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int l,r,laz1,laz2,max;
};
node tree[4000005];
int a[1000005];
void upd(int p)
{
    tree[p].l=tree[2*p].l;
    tree[p].r=tree[2*p+1].r;
    tree[p].max=max(tree[2*p].max,tree[2*p+1].max);
}
void build(int p,int l,int r)
{
    tree[p].laz1=-LLONG_MAX;
    if(l==r)
    {
        tree[p].l=l;
        tree[p].r=r;
        tree[p].max=a[l];
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    upd(p);
}
void pushd(int p)
{
    if(tree[p].laz1!=-LLONG_MAX)
    {
        tree[2*p].laz1=tree[p].laz1;
        tree[2*p+1].laz1=tree[p].laz1;
        tree[2*p].max=tree[p].laz1;
        tree[2*p+1].max=tree[p].laz1;
    }
    else{ 
        if(tree[2*p].laz1!=-LLONG_MAX)
        {
            tree[2*p].laz1+=tree[p].laz2;
            tree[2*p].max+=tree[p].laz2;
        }else{
            tree[2*p].laz2+=tree[p].laz2;
            tree[2*p].max+=tree[p].laz2;
        }
        if(tree[2*p+1].laz1!=-LLONG_MAX)
        {
            tree[2*p+1].laz1+=tree[p].laz2;
            tree[2*p+1].max+=tree[p].laz2;
        }else{
            tree[2*p+1].laz2+=tree[p].laz2;
            tree[2*p+1].max+=tree[p].laz2;
        }
    }
    tree[p].laz2=0;
    tree[p].laz1=-LLONG_MAX;
}
void cover(int p,int l,int r,int x)
{
    if(l>r)
    {
        return;
    }
    if(tree[p].l>=l&&tree[p].r<=r)
    {
        tree[p].laz1=x;
        tree[p].laz2=0;
        tree[p].max=x;
        return;
    }
    if(tree[p].laz1!=-LLONG_MAX||tree[p].laz2!=0)
    {
        pushd(p);
    }
    if(r<=tree[2*p].r)
    {
        cover(2*p,l,r,x);
    }else if(l>=tree[2*p+1].l)
    {
        cover(2*p+1,l,r,x);
    }else{
        cover(2*p,l,r,x);
        cover(2*p+1,l,r,x);
    }
    upd(p);
}
void change2(int p,int l,int r,int x)
{
    if(l>r)
    {
        return;
    }
    if(tree[p].l>=l&&tree[p].r<=r)
    {
        if(tree[p].laz1!=-LLONG_MAX)
        {
            tree[p].laz1+=x;
        }else{
            tree[p].laz2+=x;
        }
        tree[p].max+=x;
        return;
    }
    if(tree[p].laz1!=-LLONG_MAX||tree[p].laz2!=0)
    {
        pushd(p);
    }
    if(r<=tree[2*p].r)
    {
        change2(2*p,l,r,x);
    }else if(l>=tree[2*p+1].l)
    {
        change2(2*p+1,l,r,x);
    }else{
        change2(2*p,l,r,x);
        change2(2*p+1,l,r,x);
    }
    upd(p);
}
int search(int p,int l,int r)
{
    if(l<=tree[p].l&&r>=tree[p].r)
    {
        return tree[p].max;
    }
    if(tree[p].laz1!=-LLONG_MAX||tree[p].laz2!=0)
    {
        pushd(p);
    }
    if(r<=tree[2*p].r)
    {
        return search(2*p,l,r);
    }else if(l>=tree[2*p+1].l)
    {
        return search(2*p+1,l,r);
    }else{
        return max(search(2*p,l,r),search(2*p+1,l,r));
    }
}
signed main()
{
    // freopen(".in","r",stdin);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            cover(1,l,r,x);
        }else if(op==2)
        {
            int l,r,x;
            scanf("%lld%lld%lld",&l,&r,&x);
            change2(1,l,r,x);
        }else{
            int l,r;
            scanf("%lld%lld",&l,&r);
            int ans=search(1,l,r);
            cout<<ans<<endl;
        }
    }
    return 0;
}

| 下一页