取反的标记和翻转的标记为什么不能使用同一变量?

P2572 [SCOI2010] 序列操作

h1910819075 @ 2021-10-27 11:21:22

rt,我的线段树中的懒标记就是取反和翻转的标记,事实告诉我这样是不行的,可是我想不通为什么不能使用同一个变量,在我看来,因为翻转的标记的一定是优先取反标记的,所以在有翻转的标记的时候直接覆盖就好了,有取反标记的时候就也会覆盖翻转的标记。使用同一个变量有什么不对的吗?QAQ,求解。


by SSerxhs @ 2021-10-27 11:25:54

  1. 什么是翻转,题目没这东西
  2. 理论上当然啥都是可以合并的,只要最终信息量相等

by h1910819075 @ 2021-10-27 11:34:15

@SSerxhs 翻转就是全部变为0或者1


by h1910819075 @ 2021-10-27 11:48:04

应该用推翻来形容?反正大概意思就是全部变为0或1的状态。唉~为什么不能同一个变量,现在我还没有弄清,QAQ


by h1910819075 @ 2021-10-27 11:50:43

重点是我使用同一个变量,要是全WA,我还能理解,TLE是什么鬼!


by zhiyangfan @ 2021-10-27 11:57:05

@h1910819075 能放一下代码吗?这道题属于是码农题,细节比较多,光靠您这样说可能不是很清楚qwq


by h1910819075 @ 2021-10-27 17:15:38

这是代码:


#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
struct point{
    int L,R;
    int lcnt,rcnt,sum,ma,lz;
    int flcnt,frcnt,fsum,fma;
    //sum是一段区间1的个数,ma是一段区间最长连续的1的个数; 
}tree[N*4];
int n,m,a[N];

inline void push_up(int node)
{
    int L=tree[node].L,R=tree[node].R;
    int mid=(L+R)>>1;
    int L_node=node<<1,R_node=node<<1|1;

    tree[node].sum=tree[L_node].sum+tree[R_node].sum;
    tree[node].ma=max(tree[L_node].rcnt+tree[R_node].lcnt,max(tree[L_node].ma,tree[R_node].ma));
    if(tree[L_node].ma==mid-L+1)
        tree[node].lcnt=tree[L_node].ma+tree[R_node].lcnt;
    else
        tree[node].lcnt=tree[L_node].lcnt;
    if(tree[R_node].ma==R-mid)
        tree[node].rcnt=tree[L_node].rcnt+tree[R_node].ma;
    else
        tree[node].rcnt=tree[R_node].rcnt;

    //取反的区间 
    tree[node].fsum=tree[L_node].fsum+tree[R_node].fsum;
    tree[node].fma=max(tree[L_node].frcnt+tree[R_node].flcnt,max(tree[L_node].fma,tree[R_node].fma));
    if(tree[L_node].fma==mid-L+1)
        tree[node].flcnt=tree[L_node].fma+tree[R_node].flcnt;
    else
        tree[node].flcnt=tree[L_node].flcnt;
    if(tree[R_node].fma==R-mid)
        tree[node].frcnt=tree[L_node].frcnt+tree[R_node].fma;
    else
        tree[node].frcnt=tree[R_node].frcnt;
}

inline void build(int node,int L,int R)
{
    tree[node].L=L,tree[node].R=R;
    tree[node].lz=-1;
    if(L==R)
    {
        tree[node].lcnt=tree[node].rcnt=tree[node].sum=tree[node].ma=a[L];
        tree[node].flcnt=tree[node].frcnt=tree[node].fsum=tree[node].fma=a[L]^1;
        return ;
    }

    int mid=(L+R)>>1;
    int L_node=node<<1,R_node=node<<1|1;
    build(L_node,L,mid);
    build(R_node,mid+1,R);
    push_up(node);
}

inline void push_down(int node)
{
    int L_node=node<<1,R_node=node<<1|1;
    int mid=(tree[node].L+tree[node].R)>>1;

    if(tree[node].lz==0)//下面的子节点要置为空房间 
    {
        tree[L_node].lz=tree[R_node].lz=0;
        tree[L_node].sum=tree[L_node].lcnt=tree[L_node].rcnt=tree[L_node].ma=0;
        tree[R_node].sum=tree[R_node].lcnt=tree[R_node].rcnt=tree[R_node].ma=0;

        tree[L_node].fsum=tree[L_node].flcnt=tree[L_node].frcnt=tree[L_node].fma=mid-tree[node].L+1;
        tree[R_node].fsum=tree[R_node].flcnt=tree[R_node].frcnt=tree[R_node].fma=tree[node].R-mid;
    }
    else if(tree[node].lz==1)//对下面的字节点要置为满房间; 
    {
        tree[L_node].lz=tree[R_node].lz=1;
        tree[L_node].sum=tree[L_node].lcnt=tree[L_node].rcnt=tree[L_node].ma=mid-tree[node].L+1;
        tree[R_node].sum=tree[R_node].lcnt=tree[R_node].rcnt=tree[R_node].ma=tree[node].R-mid;

        tree[L_node].fsum=tree[L_node].flcnt=tree[L_node].frcnt=tree[L_node].fma=0;
        tree[R_node].fsum=tree[R_node].flcnt=tree[R_node].frcnt=tree[R_node].fma=0;
    }
    else if(tree[node].lz==2)
    {
        tree[L_node].lz=tree[R_node].lz=2;

        int tlcnt=tree[L_node].lcnt,trcnt=tree[L_node].rcnt,tma=tree[L_node].ma,tsum=tree[L_node].sum;
        tree[L_node].lcnt=tree[L_node].flcnt;tree[L_node].rcnt=tree[L_node].frcnt;
        tree[L_node].ma=tree[L_node].fma,tree[L_node].sum=tree[L_node].fsum;
        tree[L_node].flcnt=tlcnt;tree[L_node].frcnt=trcnt;
        tree[L_node].fma=tma,tree[L_node].fsum=tsum;

        tlcnt=tree[R_node].lcnt,trcnt=tree[R_node].rcnt,tma=tree[R_node].ma,tsum=tree[R_node].sum;
        tree[R_node].lcnt=tree[R_node].flcnt;tree[R_node].rcnt=tree[R_node].frcnt;
        tree[R_node].ma=tree[R_node].fma,tree[R_node].sum=tree[R_node].fsum;
        tree[R_node].flcnt=tlcnt;tree[R_node].frcnt=trcnt;
        tree[R_node].fma=tma,tree[R_node].fsum=tsum;
    }
    tree[node].lz=-1;
}

inline void modify(int node,int L,int R,int x)
{
    if(L<=tree[node].L&&tree[node].R<=R)
    {
        if(x==0)//全部置为0
        {
            tree[node].lcnt=tree[node].rcnt=tree[node].ma=tree[node].sum=0;

            tree[node].flcnt=tree[node].frcnt=tree[node].fma=tree[node].fsum=tree[node].R-tree[node].L+1;
        }
        else if(x==1)//全部置为1 
        {
            tree[node].lcnt=tree[node].rcnt=tree[node].ma=tree[node].sum=tree[node].R-tree[node].L+1;

            tree[node].flcnt=tree[node].frcnt=tree[node].fma=tree[node].fsum=0;
        }
        else if(x==2)//全部取反 
        {
            int tlcnt=tree[node].lcnt,trcnt=tree[node].rcnt,tma=tree[node].ma,tsum=tree[node].sum;

            tree[node].lcnt=tree[node].flcnt;tree[node].rcnt=tree[node].frcnt;
            tree[node].ma=tree[node].fma,tree[node].sum=tree[node].fsum;

            tree[node].flcnt=tlcnt;tree[node].frcnt=trcnt;
            tree[node].fma=tma,tree[node].fsum=tsum;    
        }
        tree[node].lz=x;
        return ;
    }
    push_down(node);

    int mid=(tree[node].L+tree[node].R)>>1;
    int L_node=node<<1,R_node=node<<1|1;
    if(L<=mid)
        modify(L_node,L,R,x);
    if(R>mid)
        modify(R_node,L,R,x);
    push_up(node);
}

inline int query1(int node,int L,int R)
{
    if(tree[node].L>=L&&tree[node].R<=R)
        return tree[node].sum;
    push_down(node);//父节点的内容传下去!!! 

    int mid=(tree[node].L+tree[node].R)>>1;
    int ans=0;
    if(L<=mid)
        ans+=query1(node<<1,L,R);
    if(R>mid)
        ans+=query1(node<<1|1,L,R);
    return ans;
}

inline int query2(int node,int L,int R)
{
    if(tree[node].L<=L&&tree[node].R<=R)
        return tree[node].ma;
    push_down(node);//父节点的内容传下去!!! 

    int mid=(tree[node].L+tree[node].R)>>1;
    if(L<=mid&&R>mid)
    {
        int ans=max(query2(node<<1,L,R),query2(node<<1|1,L,R));
        int ans1=min(tree[node<<1].rcnt,mid-L+1)+min(tree[node<<1|1].rcnt,R-mid);
        return max(ans,ans1);
    }
    else if(L<=mid)
        return query2(node<<1,L,R);
    else if(R>mid)
        return query2(node<<1|1,L,R);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);

    while(m--)
    {
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        l++,r++;
        if(op<=2)
            modify(1,l,r,op);
        else if(op==3)
            printf("%d\n",query1(1,l,r));
        else
            printf("%d\n",query2(1,l,r));

        //for(int i=1;i<=3*n;i++)
        //  printf("i=%d sum=%d lcnt=%d rcnt=%d ma=%d   fsum=%d flcnt=%d frcnt=%d fma=%d \n",i,tree[i].sum,tree[i].lcnt,tree[i].rcnt,tree[i].ma,tree[i].fsum,tree[i].flcnt,tree[i].frcnt,tree[i].fma);
    }
    return 0;
}

by h1910819075 @ 2021-10-27 18:15:25

我明白为什么不能使用同一个变量了,为什么我的代码会TLE了,QAQ,太艰难了!


|