Steven_Meng's Blog

洛谷

BZOJ

线段树维护，每个节点上面记录$6$个值$l0,l1,r0,r1,m0,m1$（套路），代表从左开始最长$0$的序列长度，最长$1$的序列的长度，从右开始的......，中间的......（懒）

翻转就是把他们两两交换，$\rm pushup$也都是套路。

注意覆盖标记比翻转标记优先级高，于是区间覆盖的时候会把翻转标记设成$0$，$\rm pushdown$的时候也是先判断区间覆盖标记。

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN];
namespace SegmentTree{
    struct node{
        int l,r;
        int l0,r0,l1,r1,m0,m1;
        int sum,tag;
        bool rev;
        inline int len(){return r-l+1;}
    }tree[MAXN<<2];
    #define lc i<<1
    #define rc i<<1|1
    inline void Rev(int i){
        tree[i].sum=tree[i].len()-tree[i].sum;
        swap(tree[i].l0,tree[i].l1);
        swap(tree[i].r0,tree[i].r1);
        swap(tree[i].m0,tree[i].m1);
        tree[i].rev^=1;
    }
    inline void Cover(int i,int val){
        tree[i].tag=val;
        tree[i].sum=val*tree[i].len();
        tree[i].l0=tree[i].r0=tree[i].m0=(1-val)*tree[i].len();
        tree[i].r1=tree[i].l1=tree[i].m1=val*tree[i].len();
        tree[i].rev=0;
    }
    inline void pushdown(int i){
        if (tree[i].l==tree[i].r) return ;
        if (tree[i].tag!=-1){
            Cover(lc,tree[i].tag),Cover(rc,tree[i].tag);
            tree[i].tag=-1;
        }
        if (tree[i].rev){
            Rev(lc),Rev(rc);
            tree[i].rev=0;
        }
    }
    node operator + (node a,node b){
        node c;
        c.l=a.l,c.r=b.r;
        c.l0=a.l0;
        if (a.sum==0) c.l0=max(c.l0,a.len()+b.l0);
        c.l1=a.l1;
        if (a.sum==a.len()) c.l1=max(c.l1,a.len()+b.l1);
        c.r0=b.r0;
        if (b.sum==0) c.r0=max(c.r0,b.len()+a.r0);
        c.r1=b.r1;
        if (b.sum==b.len()) c.r1=max(c.r1,b.len()+a.r1);
        c.m0=max(max(a.m0,b.m0),a.r0+b.l0);
        c.m1=max(max(a.m1,b.m1),a.r1+b.l1);
        c.sum=a.sum+b.sum;
        return c;
    }
    inline void pushup(int i){
        int temp1=tree[i].rev,temp2=tree[i].tag;
        tree[i]=tree[lc]+tree[rc];
        tree[i].rev=temp1,tree[i].tag=temp2;
    }
    void Build(int i,int l,int r){
        tree[i].l=l,tree[i].r=r;
        tree[i].tag=-1;
        if (l==r){
            Cover(i,a[l]);
            return ;
        }
        int mid=(l+r)>>1;
        Build(lc,l,mid);
        Build(rc,mid+1,r);
        pushup(i);
    }
    void Update(int i,int L,int R,int val){
        if (L<=tree[i].l&&tree[i].r<=R){
            Cover(i,val);
            return ;
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (L<=mid) Update(lc,L,R,val);
        if (mid<R) Update(rc,L,R,val);
        pushup(i);
    }
    void Reverse(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            Rev(i);
            return ;
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (L<=mid) Reverse(lc,L,R);
        if (mid<R) Reverse(rc,L,R);
        pushup(i);
    }
    int QuerySum(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            return tree[i].sum;
        }
        int mid=(tree[i].l+tree[i].r)>>1,ans=0;
        pushdown(i);
        if (L<=mid) ans+=QuerySum(lc,L,R);
        if (mid<R) ans+=QuerySum(rc,L,R);
        return ans;
    }
    node QueryMax(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            return tree[i];
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (mid>=R) return QueryMax(lc,L,R);
        else if (L>mid) return QueryMax(rc,L,R);
        else return QueryMax(lc,L,R)+QueryMax(rc,L,R);
    }
}
using namespace SegmentTree;
int main(){
    int n=read(),m=read();
    for (register int i=1;i<=n;++i){
        a[i]=read();
    }
    Build(1,1,n);
    while (m--){
        int opr=read(),l=read()+1,r=read()+1;
        if (opr==0) Update(1,l,r,0);
        if (opr==1) Update(1,l,r,1);
        if (opr==2) Reverse(1,l,r);
        if (opr==3) printf("%d\n",QuerySum(1,l,r));
        if (opr==4) printf("%d\n",QueryMax(1,l,r).m1);
    }
}