caojc @ 2023-12-12 18:56:27
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define db(x) cout<<x<<' ';
#define ls tr[u*2]
#define rs tr[u*2+1]
const int N = 1e5+10;
struct nd {int L = 0,len1 = 0,l1 = 0,r1=0,len0=0,l0=0,r0=0,lz=0,cnt1=0,cnt0=0;}tr[N<<2];
int n,m,t,a[N];
nd push_up(const nd lson,const nd rson){
nd res;
res.cnt1 = lson.cnt1 + rson.cnt1;
res.len1 = max({rson.len1,lson.len1,lson.r1 + rson.l1});
if(lson.l1 == lson.L)res.l1 = lson.L + rson.l1;
else res.l1 = lson.l1;
if(rson.r1 == rson.L)res.r1 = rson.L + lson.r1;
else res.r1 = rson.r1;
res.cnt0 = lson.cnt0 + rson.cnt0;
res.len0 = max({rson.len0,lson.len0,lson.r0 + rson.l0});
if(lson.l0 == lson.L)res.l0 = lson.L + rson.l0;
else res.l0 = lson.l0;
if(rson.r0 == rson.L)res.r0 = rson.L + lson.r0;
else res.r0 = rson.r0;
res.L = lson.L + rson.L;
return res;
}
void build(int u,int ul,int ur){
if(ul == ur){
if(a[ur] == 1){
tr[u].len1 = tr[u].l1 = tr[u].r1 = tr[u].cnt1 = 1;
tr[u].len0 = tr[u].l0 = tr[u].r0 = tr[u].cnt0 = 0;
}else{
tr[u].len1 = tr[u].l1 = tr[u].r1 = tr[u].cnt1 = 0;
tr[u].len0 = tr[u].l0 = tr[u].r0 = tr[u].cnt0 = 1;
}
tr[u].L = 1;
//db(u);db(ur);db(tr[u].cnt1);cout<<'\n';
return;
}
int mid = (ul+ur)>>1;
build(u*2,ul,mid);build(u*2+1,mid+1,ur);
tr[u] = push_up(tr[u*2],tr[u*2+1]);
tr[u].lz = -1;
//db(ul);db(ur);db(tr[u].cnt1);cout<<'\n';
}
void push_down(int u,int ul, int ur){
if(tr[u].lz == -1)return;
int lz = tr[u].lz;
if(lz!=2)ls.lz = rs.lz = lz;
else {
if(ls.lz == 2)ls.lz = -1;
else if(ls.lz == 1)ls.lz = 0;
else if(ls.lz == 0)ls.lz = 1;
else ls.lz = 2;
if(rs.lz == 2)rs.lz = -1;
else if(rs.lz == 1)rs.lz = 0;
else if(rs.lz == 0)rs.lz = 1;
else rs.lz = 2;
}
if(lz == 0){
ls.cnt0 = ls.l0 = ls.r0 = ls.len0 = ls.L;
ls.cnt1 = ls.l1 = ls.r1 = ls.len1 = 0;
rs.cnt0 = rs.l0 = rs.r0 = rs.len0 = rs.L;
rs.cnt1 = rs.l1 = rs.r1 = rs.len1 = 0;
}else if(lz == 1){
ls.cnt0 = ls.l0 = ls.r0 = ls.len0 = 0;
ls.cnt1 = ls.l1 = ls.r1 = ls.len1 = ls.L;
rs.cnt0 = rs.l0 = rs.r0 = rs.len0 = 0;
rs.cnt1 = rs.l1 = rs.r1 = rs.len1 = rs.L;
}else if (lz == 2){
swap(ls.cnt0,ls.cnt1);swap(ls.l0,ls.l1);swap(ls.r0,rs.r1);swap(ls.len1,ls.len0);
swap(rs.cnt0,rs.cnt1);swap(rs.l0,rs.l1);swap(rs.r0,rs.r1);swap(rs.len1,rs.len0);
}
tr[u].lz = -1;
}
nd q(int u,int l,int r,int ul,int ur){
if(l <= ul && r >= ur){
//db(ul);db(ur);db(tr[u].cnt1);cout<<'\n';
return tr[u];
}
push_down(u,ul,ur);
int mid = (ul + ur)>>1;
nd res ;
if(r<=mid)res = q(u*2,l,r,ul,mid);
else if(l>=mid+1)res = q(u*2+1,l,r,mid+1,ur);
else res = push_up(q(u*2,l,r,ul,mid),q(u*2+1,l,r,mid+1,ur));
db(l);db(r);db(res.L);cout<<'\n';
return res;
}
void change(int u,int l,int r,int x,int ul,int ur){
if(l<=ul && r>= ur){
if(x == 0){
tr[u].cnt0 = tr[u].l0 = tr[u].r0 = tr[u].len0 = tr[u].L;
tr[u].cnt1 = tr[u].l1 = tr[u].r1 = tr[u].len1 = 0;
}else if(x == 1){
tr[u].cnt0 = tr[u].l0 = tr[u].r0 = tr[u].len0 = 0;
tr[u].cnt1 = tr[u].l1 = tr[u].r1 = tr[u].len1 = tr[u].L;
}else{
swap(tr[u].l0,tr[u].l1);swap(tr[u].r0,tr[u].r1);
swap(tr[u].cnt0,tr[u].cnt1);swap(tr[u].len0,tr[u].len1);
}
if(x == 2){
if(tr[u].lz == -1)tr[u].lz = 2;
else if(tr[u].lz == 1)tr[u].lz = 0;
else if(tr[u].lz == 0)tr[u].lz = 1;
else if(tr[u].lz == 2)tr[u].lz = -1;
}else{
tr[u].lz = x;
}
return;
}
int mid = (ul + ur) >> 1;
push_down(u,ul,ur);
if(l <= mid)change(u*2,l,r,x,ul,mid);
if(r >= mid+1)change(u*2+1,l,r,x,mid+1,ur);
int lz = tr[u].lz;
tr[u] = push_up(ls,rs);
tr[u].lz = lz;
}
signed main(){
ios::sync_with_stdio(1);cout.tie(0);cin.tie(0);
cin>>n>>m;
for(int i = 1 ; i <= n;i++)cin>>a[i];
build(1,1,n);
while(m--){
int f,l,r;
cin>>f>>l>>r;
l++,r++;
if(f <= 2){
change(1,l,r,f,1,n);
}else{
nd res = q(1,l,r,1,n);
if(f == 3)cout<<res.cnt1;
else cout<<res.len1;
cout<<'\n';
}
}
return 0;
}