前言

MC 说可以 ODT 暴力草，但是菜鸡不会 ODT ，只会码线段树。

但是关于线段树……实名宣布楼下二位代码实在难看。

写这种题就应该好好用结构体嘛 /cy

正文

更好的阅读体验

Statement

给定一个长为 $n$ 的 01 序列，要求实现 $5$ 种操作：

• 0 a b 将 $[a,b]$ 全部设为 $0$ .
• 1 a b 将 $[a,b]$ 全部设为 $1$ .
• 2 a b 将区间所有数取反 。
• 3 a b 询问区间内 $1$ 的个数。
• 4 a b 询问区间内连续 $1$ 的个数。

Solution

顶风作案写DS.jpg

线段树恶心题，但是很经典，码得也算能看，就拿出来当板子了。

维护前缀 $0/1$ 、后缀 $0/1$ 、连续 $0/1$ 的个数，和区间中 $0/1$ 的个数。注意覆盖标记优先级高于翻转标记。

线段树恶心题，码就完了。实在不行，重构就是了

好在码得并不慢，调得也很快，调过样例之后一遍就过拍了（本地数据手动 diff ）。

你谷开 O2 跑进了第二页，BZOJ 没开 O2 卡在第一页底端/youl

希望下次写结构体函数的时候：

$\huge 真的不要再忘记return了$

Code

//Author: RingweEH
//菜鸡REH顶风作案
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define db double
using namespace std;
int min( int a,int b ) { return a<b ? a : b; }
int max( int a,int b ) { return a>b ? a : b; }
int read()
{
    int x=0,w=1; char ch=getchar();
    while ( ch>'9' || ch<'0' ) { if ( ch=='-' ) w=-1; ch=getchar(); }
    while ( ch<='9' && ch>='0' ) x=x*10+ch-'0',ch=getchar();
    return x*w;
}

const int N=1e5+10;
int n,q,a[N];
struct SegmentTree
{
    struct Node
    {
        int cntw,cntb,lcntw,rcntw,lcntb,rcntb,mxw,mxb;
        //w个数，b个数，左/右数w个数，左/右数b个数，连续w/b最大值
        Node( int _cntw=0,int _cntb=0,int _lcntw=0,int _lcntb=0,
            int _rcntw=0,int _rcntb=0,int _mxw=0,int _mxb=0 )
        {
            cntw=_cntw; cntb=_cntb; lcntw=_lcntw; lcntb=_lcntb;
            rcntb=_rcntb; rcntw=_rcntw; mxw=_mxw; mxb=_mxb;
        }
        Node operator + ( const Node &tmp ) const
        {
            Node res;
            res.cntw=cntw+tmp.cntw; res.cntb=cntb+tmp.cntb;
            res.lcntw=cntb ? lcntw : cntw+tmp.lcntw;
            res.lcntb=cntw ? lcntb : cntb+tmp.lcntb;
            res.rcntw=tmp.cntb ? tmp.rcntw : tmp.cntw+rcntw;
            res.rcntb=tmp.cntw ? tmp.rcntb : tmp.cntb+rcntb;
            res.mxw=max( max(mxw,tmp.mxw),rcntw+tmp.lcntw );
            res.mxb=max( max(mxb,tmp.mxb),rcntb+tmp.lcntb );
            return res;
        }
    }tr[N<<2];
    int len[N<<2],tag1[N<<2],tag2[N<<2];
    //区间长度，区间赋值标记(-1/0/1)，区间取反(0/1)
    void Operate( int pos,int opt ) 
    {
        Node &te=tr[pos];
        if ( opt==0 )   //reset( 0 )
        {
            tag2[pos]=tag1[pos]=0; int t=len[pos];
            te=Node( 0,t,0,t,0,t,0,t );
        }
        if ( opt==1 )   //reset( 1 )
        {
            tag2[pos]=0,tag1[pos]=1; int t=len[pos];
            te=Node( t,0,t,0,t,0,t,0 );
        }
        if ( opt==2 )   //flip
        {
            tag2[pos]^=1; 
            swap( te.cntw,te.cntb ); swap( te.mxb,te.mxw );
            swap( te.lcntw,te.lcntb ); swap( te.rcntw,te.rcntb );
        }
    }
    void Pushdown( int pos )
    {
        if ( tag1[pos]>-1 ) 
            Operate( pos<<1,tag1[pos] ),Operate( pos<<1|1,tag1[pos] );
        if ( tag2[pos] ) 
            Operate( pos<<1,2 ),Operate( pos<<1|1,2 );
        tag1[pos]=-1; tag2[pos]=0; 
    }
    void Modify( int pos,int L,int R,int l,int r,int val )
    {
        if ( r<L || R<l ) return;
        if ( l<=L && R<=r ) { Operate( pos,val ); return; }
        Pushdown( pos ); int mid=(L+R)>>1;
        Modify( pos<<1,L,mid,l,r,val ); Modify( pos<<1|1,mid+1,R,l,r,val );
        tr[pos]=tr[pos<<1]+tr[pos<<1|1];
    }
    Node Query( int pos,int L,int R,int l,int r )
    {
        if ( r<L || R<l ) return Node();
        if ( l<=L && R<=r ) return tr[pos];
        Pushdown( pos ); int mid=(L+R)>>1;
        Node lc=Query(pos<<1,L,mid,l,r),rc=Query(pos<<1|1,mid+1,R,l,r);
        return lc+rc;
    }
    void Build( int pos,int L,int R )
    {
        len[pos]=R-L+1; tag1[pos]=-1;
        if ( L==R )
        {
            int t=a[L]; tr[pos]=Node(t,t^1,t,t^1,t,t^1,t,t^1 );
            return;
        }
        int mid=(L+R)>>1;
        Build( pos<<1,L,mid ); Build( pos<<1|1,mid+1,R );
        tr[pos]=tr[pos<<1]+tr[pos<<1|1];
    }
    int Answer( int l,int r,int opt )
    {
        Node res=Query( 1,1,n,l,r );
        if ( opt==3 ) return res.cntw;
        else return res.mxw;
    }
    //w,b,lw,lb,rw,rb,mw,mb;
}Tr;

int main()
{
    n=read(); q=read();
    for ( int i=1; i<=n; i++ )
        a[i]=read();

    Tr.Build(1,1,n);
    while ( q-- )
    {
        int opt=read(),l=read()+1,r=read()+1;
        if ( opt<3 ) Tr.Modify( 1,1,n,l,r,opt );
        else printf( "%d\n",Tr.Answer(l,r,opt) );
    }

    return 0;
}