```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define Main main
#define Gc() getchar()
#define ls pt<<1
#define rs pt<<1|1
#define rint register int
#define iint inline int
#define void inline void
iint Read(){int x=0;char c=Gc();while(c<'0'||c>'9')c=Gc();while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=Gc();return x;}
void Writ(int x){if(x>9)Writ(x/10);putchar(x%10+'0');return;}
void Print(int x){Writ(x),putchar('\n');}
iint Max(int a,int b,int c){return max(a,max(b,c));}
struct Tree{int l,r,sum[2],llen[2],rlen[2],len[2],tg,re;}tr[800005];
int n,m,a[200005];
Tree Update(Tree pt,Tree le,Tree ri)
{
for(rint i=0;i<2;i++)
pt.len[i]=Max(le.len[i],ri.len[i],le.rlen[i]+ri.llen[i]),
pt.llen[i]=le.llen[i]+ri.llen[i]*(!le.sum[i^1]),
pt.rlen[i]=ri.rlen[i]+le.rlen[i]*(!ri.sum[i^1]),
pt.sum[i]=le.sum[i]+ri.sum[i];return pt;
}
void Spread(int pt)
{
Tree t=tr[pt],lt=tr[ls],rt=tr[rs];
int lsi=lt.r-lt.l+1,rsi=rt.r-rt.l+1;
if(t.tg!=-1)
{
int l1=lsi*(t.tg^1),l2=lsi*t.tg,r1=rsi*(t.tg^1),r2=rsi*t.tg;
lt=tr[ls]=(Tree){lt.l,lt.r,{l1,l2},{l1,l2},{l1,l2},{l1,l2},t.tg,0};
rt=tr[rs]=(Tree){rt.l,rt.r,{r1,r2},{r1,r2},{r1,r2},{r1,r2},t.tg,0};
t.tg=tr[pt].tg=-1;t.re=tr[pt].re=0;
}
if(t.re)
{
lt=tr[ls]=(Tree){lt.l,lt.r,{lt.sum[1],lt.sum[0]},{lt.llen[1],lt.llen[0]},{lt.rlen[1],lt.rlen[0]},{lt.len[1],lt.len[0]},lt.tg,lt.re};
rt=tr[rs]=(Tree){rt.l,rt.r,{rt.sum[1],rt.sum[0]},{rt.llen[1],rt.llen[0]},{rt.rlen[1],rt.rlen[0]},{rt.len[1],rt.len[0]},rt.tg,rt.re};
if(tr[ls].tg!=-1)tr[ls].tg^=1;else{tr[ls].re^=1;}if(tr[rs].tg!=-1)tr[rs].tg^=1;else{tr[rs].re^=1;}tr[pt].re=0;
}return;
}
void Build(int pt,int le,int ri)
{
tr[pt].l=le,tr[pt].r=ri;int mid=(le+ri)>>1;
if(le==ri){tr[pt]=(Tree){le,ri,{a[le]^1,a[le]},{a[le]^1,a[le]},{a[le]^1,a[le]},{a[le]^1,a[le]},-1,0};return;}
Build(ls,le,mid);Build(rs,mid+1,ri);tr[pt]=Update(tr[pt],tr[ls],tr[rs]);tr[pt].tg=-1;tr[pt].re=0;
}
void Memset(int pt,int le,int ri,int sg)
{
int l=tr[pt].l,r=tr[pt].r,si=r-l+1,s1=si*(sg^1),s2=si*sg;
if(le<=l&&ri>=r){tr[pt]=(Tree){l,r,{s1,s2},{s1,s2},{s1,s2},{s1,s2},sg,0};return;}
int mid=(l+r)>>1;Spread(pt);
if(mid>=le)Memset(ls,le,ri,sg);
if(mid<ri)Memset(rs,le,ri,sg);
tr[pt]=Update(tr[pt],tr[ls],tr[rs]);
}
void Reverse(int pt,int le,int ri)
{
Tree t=tr[pt];int l=t.l,r=t.r;
if(le<=l&&ri>=r)
{
tr[pt]=(Tree){l,r,{t.sum[1],t.sum[0]},{t.llen[1],t.llen[0]},{t.rlen[1],t.rlen[0]},{t.len[1],t.len[0]},t.tg,t.re};
if(t.tg!=-1)tr[pt].tg^=1;else{tr[pt].re^=1;}return;
}int mid=(l+r)>>1;Spread(pt);
if(mid>=le)Reverse(ls,le,ri);
if(mid<ri)Reverse(rs,le,ri);
tr[pt]=Update(tr[pt],tr[ls],tr[rs]);
}
Tree Query(int pt,int le,int ri)
{
Tree t=tr[pt],L,R,res;int l=t.l,r=t.r,mid=(l+r)>>1;
res=L=R=(Tree){0,0,{0,0},{0,0},{0,0},{0,0},-1,0};
if(le<=l&&ri>=r){return t;}Spread(pt);
if(mid>=le)L=Query(ls,le,ri);
if(mid<ri)R=Query(rs,le,ri);
return Update(res,L,R);
}
signed Main()
{
n=Read();m=Read();
for(rint i=1;i<=n;i++)
a[i]=Read();Build(1,1,n);
for(rint i=1;i<=m;i++)
{
int sg=Read(),l=Read()+1,r=Read()+1;
if(sg<2)Memset(1,l,r,sg);else
if(sg==2)Reverse(1,l,r);else
if(sg==3)Print(Query(1,l,r).sum[1]);else
if(sg==4)Print(Query(1,l,r).len[1]);
}return 0;
}
```
by 吴隐 @ 2019-12-03 15:02:11
测评记录[R28057749](https://www.luogu.com.cn/record/28057749)
bzoj RunID 3405554
by 吴隐 @ 2019-12-03 15:03:52
你个菜鸡
by 唐晨成 @ 2019-12-03 16:26:59
我用屁股都能打完这个代码
by 唐晨成 @ 2019-12-03 16:27:28
2333
by nkinclude @ 2019-12-06 12:57:41
@[吴隐](/user/41780) lz现在改对了吗？我也是bzojAC洛谷WA0
by Haishu @ 2019-12-06 19:47:18
我也是，错的一样
~~先打了一个线段树再打了个珂朵莉结果错的一样~~
~~当然珂朵莉恰了氧气也T了来着~~
[珂朵莉](https://www.luogu.com.cn/record/28168605) [线段树](https://www.luogu.com.cn/record/28165039)
by WrongAnwser @ 2019-12-06 21:43:37
# sg有可能大于四！！！
我**&%￥#￥&*……%￥%…￥…%&&
已AC
by 吴隐 @ 2019-12-07 09:42:51
@[吴隐](/user/41780) SG大于4该怎么处理呢
by STPGUY @ 2020-02-04 21:52:28