P2572 [SCOI2010] 序列操作——复杂线段树之我的史山

· · 个人记录

复杂线段树基本框架

*带的操作涉及到pushdown**

合并merge

将两个节点的信息合并成一个节点

注意标记清空，pushdown传下去的标记不能再传上来

上传pushup

用子节点更新当前节点信息

下传pushdown

用当前标记更新子节点

注意标记之间的影响

建树build

就是建树...
感觉可以不要？

*查询query

常规查询，就是建议直接传一个节点上来
按我的写法，合并运算可能需要一个单位元

*修改revise

和下传类似，注意标记之间的影响

进入题目

关于merge

首先第一眼看的时候发现最难维护的部分是连续的 1 的长度

考虑两个区间拼在一起时答案时怎么来的
有三种情况

此时就要维护三个信息， L 表示包含左端点的最长 1 序列长度， R 表示包含右端点的最长1序列长度， res 表示答案

接下来考虑两种操作对这些信息的影响

也就是说我们同时还要维护 0 序列的对应信息

关于标记

本来想着两个标记的
但是当时根据我的不完全归纳认为两个标记之间是会相互覆盖的
于是我就只搞了一个标记......

为什么一个标记不行

现在来说为什么不行

假设将父亲节点进行一次赋值，在进行一次翻转
会发现传下来标记的时候赋值的标记被吃掉了
也就是说这条赋值的信息传不到我的后代了，于是就会出错

关于标记之间的影响

我们发现，当进行一次赋值时，这个节点以前的反转标记就被覆盖了

但是当进行一次翻转时，在这之前的赋值依旧是需要被保留的

所以说，翻转和赋值的顺序有影响

对于第二种情况需要先赋值再翻转
那末，第一种情况改怎么办呢，答案是在对一个节点进行赋值时就把它的翻转吃掉，这样当一个节点上同时有两个标记的时候它就肯定是第二种情况

AC Code:

#include <bits/stdc++.h>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid (l+r>>1)
#define REV -2
#define ONE 1
#define ZERO 2
#define NONE 0
using namespace std;

const int MAXN=1e5+5;

struct node{
    int L[2],R[2],res[2],tag1,tag2,cnt1,l,r;
}tree[MAXN<<2],I;//tag1赋值，tag2翻转 

int a[MAXN];
int n,m;

node merge(node x,node y){
    if(x.l==-1) return y;
    if(y.l==-1) return x;

    node result;
    for(int i=0;i<=1;++i){
        result.res[i]=max(max( x.res[i] , y.res[i] ), x.R[i]+y.L[i] );
        if(x.L[i]==x.r-x.l+1) result.L[i]=y.L[i]+x.r-x.l+1;
        else result.L[i]=x.L[i];
        if(y.R[i]==y.r-y.l+1) result.R[i]=x.R[i]+y.r-y.l+1;
        else result.R[i]=y.R[i];
    }
    result.l=x.l;result.r=y.r;
    result.cnt1=x.cnt1+y.cnt1;
    result.tag1=NONE;
    result.tag2=0;
//  printf("[%d,%d],res=%d\n",x.l,x.r,x.res[1]);
//  printf("[%d,%d],res=%d\n",y.l,y.r,y.res[1]);
//  printf(" => [%d,%d],res=%d\n",result.l,result.r,result.res[1]);
    return result;
}//

void pushup(int u,int l,int r){
    if(l==r) return ;
    tree[u]=merge(tree[ls(u)],tree[rs(u)]);
}//

void downtoson(int fa,int u,int l,int r){//儿子的l和r 
    int tp1=tree[fa].tag1,tp2=tree[fa].tag2;
    if(tp1==ONE){
        tree[u].L[1]=r-l+1;
        tree[u].R[1]=r-l+1;
        tree[u].L[0]=0;
        tree[u].R[0]=0;
        tree[u].res[1]=r-l+1;
        tree[u].res[0]=0;
        tree[u].cnt1=r-l+1;
        tree[u].tag1=ONE;
        tree[u].tag2=0;
    }else if(tp1==ZERO){
        tree[u].L[0]=r-l+1;
        tree[u].R[0]=r-l+1;
        tree[u].L[1]=0;
        tree[u].R[1]=0;
        tree[u].res[0]=r-l+1;
        tree[u].res[1]=0;
        tree[u].cnt1=0;
        tree[u].tag1=ZERO;
        tree[u].tag2=0;
    }if(tp2){
        swap(tree[u].L[0],tree[u].L[1]);
        swap(tree[u].R[0],tree[u].R[1]);
        swap(tree[u].res[0],tree[u].res[1]);
        tree[u].cnt1=r-l+1-tree[u].cnt1;
        tree[u].tag2^=1;
    }

}//

void pushdown(int u,int l,int r){
    if(tree[u].tag1==NONE && !tree[u].tag2) return ;
    if(l==r) return ;
    downtoson(u,ls(u),l,mid);
    downtoson(u,rs(u),mid+1,r);
    tree[u].tag1=NONE;
    tree[u].tag2=0;
}//

node query(int u,int l,int r,int L,int R){
    if(r<L || l>R) return I;
    if(l>=L && r<=R) return tree[u];
    pushdown(u,l,r);
    return merge(query(ls(u),l,mid,L,R),query(rs(u),mid+1,r,L,R));
}//

void revise(int u,int l,int r,int L,int R,int tp){
    if(r<L || l>R) return ;
    pushdown(u,l,r);
    if(l>=L && r<=R){
        if(tp==ONE){
            tree[u].L[1]=r-l+1;
            tree[u].R[1]=r-l+1;
            tree[u].L[0]=0;
            tree[u].R[0]=0;
            tree[u].res[1]=r-l+1;
            tree[u].res[0]=0;
            tree[u].cnt1=r-l+1;
            tree[u].tag1=tp;
            tree[u].tag2=0;
        }else if(tp==ZERO){
            tree[u].L[0]=r-l+1;
            tree[u].R[0]=r-l+1;
            tree[u].L[1]=0;
            tree[u].R[1]=0;
            tree[u].res[0]=r-l+1;
            tree[u].res[1]=0;
            tree[u].cnt1=0;
            tree[u].tag1=tp;
            tree[u].tag2=0;
        }else{
            swap(tree[u].L[0],tree[u].L[1]);
            swap(tree[u].R[0],tree[u].R[1]);
            swap(tree[u].res[0],tree[u].res[1]);
            tree[u].cnt1=r-l+1-tree[u].cnt1;
            tree[u].tag2^=1;
        }
        return ;
    }
    revise(ls(u),l,mid,L,R,tp);
    revise(rs(u),mid+1,r,L,R,tp);
    pushup(u,l,r);
}//

void build(int u,int l,int r){
    tree[u].l=l;tree[u].r=r;
    tree[u].tag1=NONE;
    tree[u].tag2=0;
//  printf("[%d]-[%d,%d]\n",u,tree[u].l,tree[u].r);
    if(l==r){
        int x=a[l];
        tree[u].L[x]=1;tree[u].R[x]=1;tree[u].res[x]=1;
        tree[u].L[x^1]=0;tree[u].R[x^1]=0;tree[u].res[x^1]=0;
        tree[u].cnt1=x;
//      printf("1[%d]-[%d,%d],L=%d,R=%d,res=%d,cnt=%d\n",u,tree[u].l,tree[u].r,tree[u].L[1],tree[u].R[1],tree[u].res[1],tree[u].cnt1);
//      printf("0[%d]-[%d,%d],L=%d,R=%d,res=%d\n",u,tree[u].l,tree[u].r,tree[u].L[0],tree[u].R[0],tree[u].res[0]);
        return ;
    }
    build(ls(u),l,mid);
    build(rs(u),mid+1,r);
    pushup(u,l,r);
}//

void print(int u,int l,int r){
    pushdown(u,l,r);
//  printf("1[%d]-[%d,%d],L=%d,R=%d,res=%d,cnt=%d\n",u,tree[u].l,tree[u].r,tree[u].L[1],tree[u].R[1],tree[u].res[1],tree[u].cnt1);
//  printf("0[%d]-[%d,%d],L=%d,R=%d,res=%d\n",u,tree[u].l,tree[u].r,tree[u].L[0],tree[u].R[0],tree[u].res[0]);
    if(l==r) return ;
    print(ls(u),l,mid);
    print(rs(u),mid+1,r);
} 

void init(){
    I.l=-1;
}//

void work(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    build(1,1,n);
    int op,l,r;
    init();
    while(m--){
        scanf("%d%d%d",&op,&l,&r);
        l++;r++;
        if(op==0){
            revise(1,1,n,l,r,ZERO);
        }else if(op==1){
            revise(1,1,n,l,r,ONE);
        }else if(op==2){
            revise(1,1,n,l,r,REV);
        }else if(op==3){
            auto res=query(1,1,n,l,r);
            printf("%d\n",res.cnt1);
        }else{
            printf("%d\n",query(1,1,n,l,r).res[1]);
        }
//      print(1,1,n);
    }
}

int main(){
    work();
    return 0;
}

194行的史山......