//Accepted 14560 KB 1532 ms
//线段树 区间合并
/*
0 a b 把[a, b]区间内的所有数全变成0
1 a b 把[a, b]区间内的所有数全变成1
2 a b 把[a,b]区间内的所有数全部取反，也就是说把所有的0变成1，把所有的1变成0
3 a b 询问[a, b]区间内总共有多少个1
4 a b 询问[a, b]区间内最多有多少个连续的1
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
/**
* This is a documentation comment block
* 如果有一天你坚持不下去了，就想想你为什么走到这儿！
* @authr songt
*/
;
struct node
{
int l,r;
int L1,R1; //左右连续1
int L0,R0; //左右连续0
int change; //-1 无操作 2取反，0全0 1全1
int sum1,sum0; //最大连续1,0
int all1,all0; //所有1,0
}f[imax_n*];
int a[imax_n];
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
//由下向上合并
//f[t]的延迟标记是指延迟f[t]的两个孩子的操作,而f[t]已经完成该操作
void pushUp(int t)
{
//printf("pushUpt=%d\n",t);
*t].r-f[*t].l+;
*t+].r-f[*t+].l+;
f[t].L1=f[*t].L1;
*t].L1==lLen) f[t].L1+=f[*t+].L1;//左连续1的个数
f[t].R1=f[*t+].R1;
*t+].R1==rLen) f[t].R1+=f[*t].R1;//右连续1的个数
f[t].sum1=max(f[*t].sum1,f[*t+].sum1);
f[t].sum1=max(f[t].sum1,f[*t].R1+f[*t+].L1);//最大连续1=max(左边，右边，中间合并)
f[t].all1=f[*t].all1+f[*t+].all1; //所有1
f[t].L0=f[*t].L0;
*t].L0==lLen) f[t].L0+=f[*t+].L0;
f[t].R0=f[*t+].R0;
*t+].R0==rLen) f[t].R0+=f[*t].R0;
f[t].sum0=max(f[*t].sum0,f[*t+].sum0);
f[t].sum0=max(f[t].sum0,f[*t].R0+f[*t+].L0);
f[t].all0=f[*t].all0+f[*t+].all0;
}
void pushDown(int t)
{
)
{
//printf("pushDownt=%d\n",t);
*t].r-f[*t].l+;
*t+].r-f[*t+].l+;
) //set all 0
{
f[*t].change=f[*t+].change=;
f[t].change=-;
f[*t].L1=f[*t].R1=f[*t].sum1=f[*t].all1=;
f[*t].L0=f[*t].R0=f[*t].sum0=f[*t].all0=lLen;
f[*t+].L1=f[*t+].R1=f[*t+].sum1=f[*t+].all1=;
f[*t+].L0=f[*t+].R0=f[*t+].sum0=f[*t+].all0=rLen;
return ;
}
) //set all 1
{
f[*t].change=f[*t+].change=;
f[t].change=-;
f[*t].L1=f[*t].R1=f[*t].sum1=f[*t].all1=lLen;
f[*t].L0=f[*t].R0=f[*t].sum0=f[*t].all0=;
f[*t+].L1=f[*t+].R1=f[*t+].sum1=f[*t+].all1=rLen;
f[*t+].L0=f[*t+].R0=f[*t+].sum0=f[*t+].all0=;
return ;
}
) //0->1 1->0
{
f[t].change=-;
*t].change==-) //如果f[2*t]没有操作，则直接取反
{
f[*t].change=;
}
*t].change==) //如果f[2*t]已经标记为置0，取反后为置1
{
f[*t].change=;
}
*t].change==) //如果f[2*t]已经标记为置1，取反后为置0
{
f[*t].change=;
}
*t].change==) //如果f[2*t]已经取反，再次取反相当于没操作
{
f[*t].change=-;
}
swap(f[*t].L0,f[*t].L1); //f[2*t]进行取反操作，0,1的标记都要互换
swap(f[*t].R0,f[*t].R1);
swap(f[*t].sum0,f[*t].sum1);
swap(f[*t].all0,f[*t].all1);
//2*t+1 同 2*t
*t+].change==-)
{
f[*t+].change=;
}
*t+].change==)
{
f[*t+].change=;
}
*t+].change==)
{
f[*t+].change=;
}
*t+].change==)
{
f[*t+].change=-;
}
swap(f[*t+].L0,f[*t+].L1);
swap(f[*t+].R0,f[*t+].R1);
swap(f[*t+].sum0,f[*t+].sum1);
swap(f[*t+].all0,f[*t+].all1);
}
}
}
void build(int t,int l,int r)
{
f[t].l=l;
f[t].r=r;
f[t].change=-;
if (l==r)
{
f[t].L1=f[t].R1=f[t].sum1=f[t].all1=a[l];
f[t].L0=f[t].R0=f[t].sum0=f[t].all0=-a[l];
return ;
}
;
build(*t,l,mid);
build(*t+,mid+,r);
pushUp(t);
}
void update(int t,int l,int r,int op)
{
//printf("update l=%d r=%d\n",l,r);
if (f[t].l==l && f[t].r==r)
{
//如果是2号操作，需要考虑原来的操作
)
{
) f[t].change=;
) f[t].change=;
) f[t].change=;
) f[t].change=-;
}
else
{
//置0,1操作和原来的操作没关系
f[t].change=op;
}
) //该区间置0
{
f[t].L1=f[t].R1=f[t].sum1=f[t].all1=;
f[t].L0=f[t].R0=f[t].sum0=f[t].all0=f[t].r-f[t].l+;
}
) //该区间置1
{
f[t].L1=f[t].R1=f[t].sum1=f[t].all1=f[t].r-f[t].l+;
f[t].L0=f[t].R0=f[t].sum0=f[t].all0=;
}
) //该区间取反
{
swap(f[t].L0,f[t].L1);
swap(f[t].R0,f[t].R1);
swap(f[t].sum0,f[t].sum1);
swap(f[t].all0,f[t].all1);
}
return ;
}
pushDown(t); //如果操作的区间为当前区间的子区间，则要把当前区间的change传到子区间
;
*t,l,r,op);
else
{
*t+,l,r,op);
else
{
update(*t,l,mid,op);
update(*t+,mid+,r,op);
}
}
pushUp(t); //子区间修改完成后，要向父区间合并信息
}
//op==1 求所有1 op==0 求最大连续1
int query(int t,int l,int r,int op)
{
if (f[t].l==l && f[t].r==r)
{
) return f[t].all1;
return f[t].sum1;
}
pushDown(t);
;
*t,l,r,op);
else
{
*t+,l,r,op);
else
{
) *t,l,mid,op)+query(*t+,mid+,r,op);
int ans,ans1,ans2;
ans1=query(*t,l,mid,op);
ans2=query(*t+,mid+,r,op);
ans=max(ans1,ans2);
ans=max(ans,min(f[*t].R1,mid-l+)+min(f[*t+].L1,r-mid)); //r-mid=r-(mid+1)+1
return ans;
}
}
}
int n,Q;
int op,x,y;
void slove()
{
build(,,n);
;i<=Q;i++)
{
scanf("%d%d%d",&op,&x,&y);
x++;
y++;
)
{
update(,x,y,);
}
)
{
update(,x,y,);
}
)
{
update(,x,y,);
}
)
{
,x,y,);
printf("%d\n",t);
}
)
{
,x,y,);
printf("%d\n",t);
}
}
}
int main()
{
while (scanf("%d%d",&n,&Q)!=EOF)
{
;i<=n;i++)
scanf("%d",&a[i]);
slove();
}
;
}
