MoyunAllgorithm @ 2023-09-03 13:42:30
#include <cstdio>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <utility>
#include <unordered_map>
#include <cmath>
#define LL long long
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int MAXN=1e5+5;
int a[MAXN];
int N,Q;
struct SegTree
{
int c1,c0,l1,l0,r1,r0,s1,s0;
int tagv,tagr;
}tre[MAXN<<3];
void PushUp(int pos,int l,int r)
{
tre[pos].c1=tre[lson].c1+tre[rson].c1;
tre[pos].c0=tre[lson].c0+tre[rson].c0;
tre[pos].l1=tre[lson].l1;tre[pos].l0=tre[lson].l0;tre[pos].r1=tre[rson].r1;tre[pos].r0=tre[rson].r0;
int mid=(l+r)>>1;
if(tre[lson].s1==mid-l+1) tre[pos].l1=mid-l+1+tre[rson].l1;
if(tre[lson].s0==mid-l+1) tre[pos].l0=mid-l+1+tre[rson].l0;
if(tre[rson].s1==r-mid) tre[pos].r1=r-mid+tre[lson].r1;
if(tre[rson].s0==r-mid) tre[pos].r0=r-mid+tre[lson].r0;
tre[pos].s1=max(tre[lson].r1+tre[rson].l1,max(tre[lson].s1,tre[rson].s1));
tre[pos].s0=max(tre[lson].r0+tre[rson].l0,max(tre[lson].s0,tre[rson].s0));
}
void Build(int pos,int l,int r)
{
tre[pos].tagv=-1,tre[pos].tagr=1;
if(l==r)
{
if(a[l]==1) tre[pos]={1,0,1,0,1,0,1,0,-1,1};
else tre[pos]={0,1,0,1,0,1,0,1,-1,1};
return;
}
int mid=(l+r)>>1;
Build(lson,l,mid);
Build(rson,mid+1,r);
PushUp(pos,l,r);
return;
}
void PushDown(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(tre[pos].tagv!=-1)
{
if(tre[pos].tagv==1)
{
tre[lson]={mid-l+1,0,mid-l+1,0,mid+l-1,0,mid-l+1,0,1,1};
tre[rson]={r-mid,0,r-mid,0,r-mid,0,r-mid,0,1,1};
}
else
{
tre[lson]={0,mid-l+1,0,mid-l+1,0,mid-l+1,0,mid-l+1,0,1};
tre[rson]={0,r-mid,0,r-mid,0,r-mid,0,r-mid,0,1};
}
tre[pos].tagv=-1,tre[pos].tagr=1;
}
if(tre[pos].tagr==-1)
{
swap(tre[lson].c1,tre[lson].c0);
swap(tre[lson].l1,tre[lson].l0);
swap(tre[lson].r1,tre[lson].r0);
swap(tre[lson].s1,tre[lson].s0);
swap(tre[rson].c1,tre[rson].c0);
swap(tre[rson].l1,tre[rson].l0);
swap(tre[rson].r1,tre[rson].r0);
swap(tre[rson].s1,tre[rson].s0);
if(tre[lson].tagv!=-1) tre[lson].tagv^=1;
else tre[lson].tagr=-tre[lson].tagr;
if(tre[rson].tagv!=-1) tre[rson].tagv^=1;
else tre[rson].tagr=-tre[rson].tagr;
tre[pos].tagr=1;
}
return;
}
void Update(int pos,int l,int r,int ql,int qr,int v)
{
PushDown(pos,l,r);
if(ql<=l&&r<=qr)
{
if(v==1)
{
tre[pos]={r-l+1,0,r-l+1,0,r-l+1,0,r-l+1,0,1,1};
}
else tre[pos]={0,r-l+1,0,r-l+1,0,r-l+1,0,r-l+1,0,1};
return;
}
int mid=(l+r)>>1;
if(ql<=mid) Update(lson,l,mid,ql,qr,v);
if(mid<qr) Update(rson,mid+1,r,ql,qr,v);
PushUp(pos,l,r);
return;
}
void Reverse(int pos,int l,int r,int ql,int qr)
{
PushDown(pos,l,r);
if(ql<=l&&r<=qr)
{
// printf("REV%d %d %d %d %d %d %d %d\n",tre[pos].c1,tre[pos].c0,tre[pos].l1,tre[pos].l0,tre[pos].r1,tre[pos].r0,tre[pos].s1,tre[pos].s0);
swap(tre[pos].c1,tre[pos].c0);
swap(tre[pos].l1,tre[pos].l0);
swap(tre[pos].r1,tre[pos].r0);
swap(tre[pos].s1,tre[pos].s0);
// if(tre[pos].tagv!=-1) tre[pos].tagv^=1;
tre[pos].tagr=-tre[pos].tagr;
return;
}
int mid=(l+r)>>1;
if(ql<=mid) Reverse(lson,l,mid,ql,qr);
if(mid<qr) Reverse(rson,mid+1,r,ql,qr);
PushUp(pos,l,r);
return;
}
int QuerySum(int pos,int l,int r,int ql,int qr)
{
PushDown(pos,l,r);
if(ql<=l&&r<=qr)
{
return tre[pos].c1;
}
int res=0,mid=(l+r)>>1;
if(ql<=mid) res+=QuerySum(lson,l,mid,ql,qr);
if(mid<qr) res+=QuerySum(rson,mid+1,r,ql,qr);
// printf("SUM%d %d %d %d\n",pos,l,r,res);
return res;
}
void Test(int pos,int l,int r)
{
printf("seg%d %d %d %d %d %d %d %d %d\n",pos,l,r,tre[pos].c1,tre[pos].l1,tre[pos].r1,tre[pos].s1,tre[pos].tagv,tre[pos].tagr);
if(l==r) return;
int mid=(l+r)>>1;
Test(lson,l,mid); Test(rson,mid+1,r);
return;
}
SegTree QuerySeq(int pos,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return tre[pos];
SegTree res;
PushDown(pos,l,r);
int mid=(l+r)>>1;
if(ql>mid) return QuerySeq(rson,mid+1,r,ql,qr);
if(qr<=mid) return QuerySeq(lson,l,mid,ql,qr);
SegTree sl=QuerySeq(lson,l,mid,ql,qr);
SegTree sr=QuerySeq(rson,mid+1,r,ql,qr);
res.c1=sl.c1+sr.c1;
res.c0=sl.c0+sr.c0;
res.l1=sl.l1;res.l0=sl.l0;res.r1=sr.r1;res.r0=sr.r0;
if(sl.c0==0) res.l1=sl.c1+sr.l1;
if(sl.c1==0) res.l0=sl.c0+sr.l0;
if(sr.c0==0) res.r1=sr.c1+sl.r1;
if(sr.c1==0) res.r0=sr.c0+sl.r0;
res.s1=max(min(sl.r1,mid-ql+1)+min(sr.l1,qr-mid),max(sl.s1,sr.s1));
res.s0=max(min(sl.r0,mid-ql+1)+min(sr.l0,qr-mid),max(sl.s0,sr.s0));
return res;
}
int main()
{
scanf("%d %d",&N,&Q);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
Build(1,1,N);
while(Q--)
{
int opt,l,r;
scanf("%d %d %d",&opt,&l,&r);
l++,r++;
if(opt==0)
{
Update(1,1,N,l,r,0);
}
if(opt==1)
{
Update(1,1,N,l,r,1);
}
if(opt==2)
{
Reverse(1,1,N,l,r);
}
if(opt==3)
{
printf("%d\n",QuerySum(1,1,N,l,r));
}
if(opt==4)
{
printf("%d\n",QuerySeq(1,1,N,l,r).s1);
}
// Test(1,1,N);
// puts("- - - - - -");
}
return 0;
}