为什么需要两个懒人标记呢,我感觉一个也可以,但是错了,求大佬指点

P2572 [SCOI2010] 序列操作

wownmsl1 @ 2024-11-07 16:16:47

我在settag里设置了:变1的tag是1,变0的tag是2,取反的tag是3。
这个tag我理解的是:遇到要对孩子节点进行修改或者查询时才使用。
所以都是先对这个点进行修改后,再看tag修改成什么。
所以我在对本节点进行取反操作(即op==3)时:先修改该节点,再修改tag,
如果tag==1,即本来要全变成1,那么取反就是全变成0,于是我把这个点的tag=2(变0的tag是2)。
如果tag==2,即本来要全变成0,那么取反就是全变成1,于是我把这个点的tag=1(变1的tag是1)。
如果tag==3,即本来要全取反,那么取反再取反就是什么也没有做,于是我把这个点的tag=0。
如果tag==0,即本来什么也没有做,那么就进行取反,于是我把这个点的tag=3(取反的tag是3)。

这个方法有什么问题吗?还是我的其他地方写错了?

代码只过了Subtask #1和Subtask #0的#1两个测试点

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
    int sum,z0,y0,m0,z1,y1,m1,cd;
};
node tree[400010];
int tag[400005],num[400005];
int ls(int p)
{
    return p*2;
}
int rs(int p)
{
    return p*2+1;
}
void push_up(int p)
{
    tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
    tree[p].m0=max(tree[ls(p)].m0,max(tree[rs(p)].m0,tree[ls(p)].y0+tree[rs(p)].z0));
    tree[p].m1=max(tree[ls(p)].m1,max(tree[rs(p)].m1,tree[ls(p)].y1+tree[rs(p)].z1));
    if(tree[ls(p)].cd==tree[ls(p)].z0)
        tree[p].z0=tree[ls(p)].cd+tree[rs(p)].z0;
    else
        tree[p].z0=tree[ls(p)].z0;
    if(tree[ls(p)].cd==tree[ls(p)].z1)
        tree[p].z1=tree[ls(p)].cd+tree[rs(p)].z1;
    else
        tree[p].z1=tree[ls(p)].z1;
    if(tree[rs(p)].y0==tree[rs(p)].cd)
        tree[p].y0=tree[rs(p)].y0+tree[ls(p)].y0;
    else
        tree[p].y0=tree[rs(p)].y0;
    if(tree[rs(p)].y1==tree[rs(p)].cd)
        tree[p].y1=tree[rs(p)].y1+tree[ls(p)].y1;
    else
        tree[p].y1=tree[rs(p)].y1;
}   
void build(int p,int z,int y)
{
    if(z==y)
    {
        tree[p].cd=1;
        tree[p].sum=num[z];
        if(tree[p].sum)
        {
            tree[p].m0=0;
            tree[p].z0=0;
            tree[p].y0=0;
            tree[p].m1=1;
            tree[p].z1=1;
            tree[p].y1=1;
        }
        else
        {
            tree[p].m0=1;
            tree[p].z0=1;
            tree[p].y0=1;
            tree[p].m1=0;
            tree[p].z1=0;
            tree[p].y1=0;
        }
        return ;
    }
    tree[p].cd=y-z+1;
    int mid=(z+y)/2;
    build(ls(p),z,mid);
    build(rs(p),mid+1,y);
    push_up(p);
}
void settag(int p,int z,int y,int op)
{
    if(op==1)
    {
        tree[p].sum=tree[p].cd;
        tree[p].m0=0;
        tree[p].z0=0;
        tree[p].y0=0;
        tree[p].m1=tree[p].cd;
        tree[p].z1=tree[p].cd;
        tree[p].y1=tree[p].cd;
        tag[p]=op;
    }
    else if(op==2)
    {
        tree[p].sum=0;
        tree[p].m0=tree[p].cd;
        tree[p].z0=tree[p].cd;
        tree[p].y0=tree[p].cd;
        tree[p].m1=0;
        tree[p].z1=0;
        tree[p].y1=0;
        tag[p]=op;
    }
    else if(op==3)
    {
        tree[p].sum=tree[p].cd-tree[p].sum;
        swap(tree[p].m0,tree[p].m1); 
        swap(tree[p].z0,tree[p].z1);
        swap(tree[p].y0,tree[p].y1);
        if(tag[p]==0)
            tag[p]=3;
        else if(tag[p]==1)
            tag[p]=2;
        else if(tag[p]==2)
            tag[p]=1;
        else if(tag[p]==3)
            tag[p]=0;
    }
}
void push_down(int p,int z,int y)
{
    if(tag[p])
    {
        int mid=(z+y)/2;
        settag(ls(p),z,mid,tag[p]);
        settag(rs(p),mid+1,y,tag[p]);
        tag[p]=0;
    }
}
void update(int p,int z,int y,int l,int r,int op)
{
    if(z>=l&&y<=r)
    {
        settag(p,z,y,op);
        return ;
    }
    push_down(p,z,y);
    int mid=(z+y)/2;
    if(mid>=l)
        update(ls(p),z,mid,l,r,op);
    if(mid+1<=r)
        update(rs(p),mid+1,y,l,r,op);
    push_up(p);
}
int search1(int p,int z,int y,int l,int r)
{
    if(z>=l&&y<=r)
        return tree[p].sum;
    push_down(p,z,y);
    int mid=(z+y)/2;
    int sum=0;
    if(mid>=l)
        sum+=search1(ls(p),z,mid,l,r);
    if(mid+1<=r)
        sum+=search1(rs(p),mid+1,y,l,r);
    return sum;
}
node search2(int p,int z,int y,int l,int r)
{
    node l1={0,0,0,0,0,0,0,0},l2,l3;
    l2=l1;
    if(z>=l&&y<=r)
        return tree[p];
    push_down(p,z,y);
    int mid=(z+y)/2;
    if(mid>=l)
        l1=search2(ls(p),z,mid,l,r);
    if(mid+1<=r)
        l2=search2(rs(p),mid+1,y,l,r);
    if(mid<l)
        return l2;
    if(mid+1>r)
        return l1;
    l3.cd=l1.cd+l2.cd;
    if(l1.z1==l1.cd)
        l3.z1=l1.z1+l2.z1;
    else
        l3.z1=l1.z1;
    if(l2.y1==l2.cd)
        l3.y1=l2.y1+l1.y1;
    else
        l3.y1=l1.y1;
    l3.m1=max(l1.m1,max(l2.m1,l1.y1+l2.z1));
    return l3;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",num+i);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        x++;
        y++;
        if(op==0)
        {
            update(1,1,n,x,y,2);
        }
        else if(op==1)
            update(1,1,n,x,y,1);
        else if(op==2)
            update(1,1,n,x,y,3);
        else if(op==3)
            printf("%d\n",search1(1,1,n,x,y));
        else if(op==4)
        {
            node ans;
            ans=search2(1,1,n,x,y);
            printf("%d\n",max(ans.z1,max(ans.y1,ans.m1)));//
        }
    }
}

by MYLHF @ 2024-11-07 17:36:06

本来一个就能过


by wownmsl1 @ 2024-11-12 14:10:23

@MYLHF 大佬,那我的代码是哪里出问题了呢?


|