tamamocross @ 2023-10-10 18:36:56
#include<iostream>
const int Max=1e5+1,INF=0x3f3f3f3f;
using namespace std;
struct node{
int cov;
bool rev;
int l,r;
int l1,r1;
int l0,r0;
int sum_1;
int m_0,m_1;
}T[4*Max];
bool a[Max];
void push_up(node &a,node b,node c){
a.sum_1=b.sum_1+c.sum_1;
a.l0=b.l0==(b.r-b.l+1)?c.l0+b.l0:b.l0;
a.r0=c.r0==(c.r-c.l+1)?b.r0+c.r0:c.r0;
a.l1=(b.l1==(b.r-b.l+1))?c.l1+b.l1:b.l1;
a.r1=(c.r1==(c.r-c.l+1))?b.r1+c.r1:c.r1;
a.m_0=max(max(b.m_0,c.m_0),b.r0+c.l0);
a.m_1=max(max(b.m_1,c.m_1),b.r1+c.l1);
}
void push_up(int p){
push_up(T[p],T[2*p],T[2*p+1]);
}
void Build(int p,int l,int r){
T[p].l=l;T[p].r=r;T[p].cov=INF;
if(l==r){
if(a[l]==1){
T[p].m_1=1;T[p].l1=1;T[p].r1=1;T[p].sum_1=1;
}else{
T[p].m_0=1;T[p].l0=1;T[p].r0=1;
}
return;
}
int mid=(l+r)/2;
Build(2*p,l,mid);Build(2*p+1,mid+1,r);
push_up(p);
}
void push_down(int p){
if(T[p].l==T[p].r){
return;
}
int len1=T[2*p].r-T[2*p].l+1,len2=T[2*p+1].r-T[2*p+1].l+1;
if(T[p].cov!=INF){
bool opt=T[p].cov;
T[2*p].l0=len1*!opt;T[2*p+1].l0=len2*!opt;
T[2*p].l1=len1*opt;T[2*p+1].l1=len2*opt;
T[2*p].m_0=len1*!opt;T[2*p+1].m_0=len2*!opt;
T[2*p].m_1=len1*opt;T[2*p+1].m_1=len2*opt;
T[2*p].r0=len1*!opt;T[2*p+1].r0=len2*!opt;
T[2*p].r1=len1*opt;T[2*p+1].r1=len2*opt;
T[2*p].sum_1=len1*opt;T[2*p+1].sum_1=len2*opt;
T[2*p].rev=0;T[2*p+1].rev=0;
}if(T[p].rev){
swap(T[2*p].l0,T[2*p].l1);swap(T[2*p+1].l0,T[2*p+1].l1);
swap(T[2*p].m_0,T[2*p].m_1);swap(T[2*p+1].m_0,T[2*p+1].m_1);
swap(T[2*p].r0,T[2*p].r1);swap(T[2*p+1].r0,T[2*p+1].r1);
T[2*p].sum_1=len1-T[2*p].sum_1;T[2*p+1].sum_1=len2-T[2*p+1].sum_1;
T[2*p].rev^=1;T[2*p+1].rev^=1;
}
T[p].rev=0;
T[p].cov=INF;
}
void COV(int p,int l,int r,bool val){
int len=T[p].r-T[p].l+1;
if(l<=T[p].l&&T[p].r<=r){
T[p].cov=val;
T[p].l0=len*!val;
T[p].l1=len*val;
T[p].m_0=len*!val;
T[p].m_1=len*val;
T[p].r0=len*!val;
T[p].r1=len*val;
T[p].sum_1=len*val;
T[p].rev=0;
return;
}
push_down(p);
int mid=(T[p].l+T[p].r)/2;
if(l<=mid){
COV(2*p,l,r,val);
}
if(r>mid){
COV(2*p+1,l,r,val);
}
push_up(p);
}
void REV(int p,int l,int r){
int len=T[p].r-T[p].l+1;
bool val=T[p].rev;
if(l<=T[p].l&&T[p].r<=r){
swap(T[p].l0,T[p].l1);
swap(T[p].m_0,T[p].m_1);
swap(T[p].r0,T[p].r1);
T[p].sum_1=len-T[p].sum_1;
T[p].rev^=1;
return;
}
push_down(p);
int mid=(T[p].l+T[p].r)/2;
if(l<=mid){
REV(2*p,l,r);
}
if(r>mid){
REV(2*p+1,l,r);
}
push_up(p);
}
node query(int p,int l,int r){
push_down(p);
if(l<=T[p].l&&T[p].r<=r){
return T[p];
}
node tmp;
//cout<<l<<" "<<r<<" "<<T[p].l<<" "<<T[p].r<<" "<<T[p].sum_1<<endl;
int mid=(T[p].l+T[p].r)/2;
if(l>mid){
tmp=query(2*p+1,l,r);
}else if(r<=mid){
tmp=query(2*p,l,r);
}else{
push_up(tmp,query(2*p,l,r),query(2*p+1,l,r));
}
push_up(p);
return tmp;
}
void print(int p){
cout<<T[p].l<<" "<<T[p].r<<" "<<T[p].l0<<" "<<T[p].r0<<" "<<T[p].l1<<" "<<T[p].r1<<" "<<T[p].m_1<<;
if(T[p].l==T[p].r){
return;
}
print(2*p);
print(2*p+1);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
Build(1,1,n);
//print(1);cout<<endl;
for(int i=1;i<=m;i++){
int opt;cin>>opt;
int x,y;
cin>>x>>y;x++;y++;
if(opt==0||opt==1){
COV(1,x,y,opt);
}else if(opt==2){
REV(1,x,y);
}else if(opt==3){
cout<<query(1,x,y).sum_1<<'\n';
}else{
cout<<query(1,x,y).m_1<<'\n';
}
//print(1);cout<<endl;
}
}
/*
10 2
0 0 0 1 1 0 1 0 1 1
1 0 2
3 0 5
/*8 1
0 1 0 1 0 1 0 0
2 1 5
*/
// 0 0 0 1 1 0 1 0 1 1
// 1 1 1 1 1 0 1 0 1 1 102
// 1 1 1 1 1 0 1 0 1 1 305
// 1 1 0 1 1 0 1 0 1 1 222
// 1 1 0 1 1 0 1 0 1 1 404
// 1 1 0 0 0 0 0 0 1 1 036
// 1 1 0 1 1 1 1 1 1 1 237
by tamamocross @ 2023-10-11 00:25:43
已过,忘下传标记了