lostxxx @ 2024-10-14 14:53:17
rt
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,q;
ll opt;
ll l,r;
ll a[200100];
struct node{
ll l,r,len;
ll l1max,l0max;
ll r1max,r0max;
ll sum1,sum0;
ll max1,max0;
ll lz1,lz2,lz3;
}tr[400100];
void pushup(ll x){
if (tr[x<<1].l1max==tr[x<<1].len)
tr[x].l1max=tr[x<<1].len+tr[x<<1|1].l1max;
else
tr[x].l1max=tr[x<<1].l1max;
if (tr[x<<1|1].r1max==tr[x<<1|1].len)
tr[x].r1max=tr[x<<1|1].len+tr[x<<1].r1max;
else
tr[x].r1max=tr[x<<1|1].r1max;
if (tr[x<<1].l0max==tr[x<<1].len)
tr[x].l0max=tr[x<<1].len+tr[x<<1|1].l0max;
else
tr[x].l0max=tr[x<<1].l0max;
if (tr[x<<1|1].r0max==tr[x<<1|1].len)
tr[x].r0max=tr[x<<1|1].len+tr[x<<1].r0max;
else
tr[x].r0max=tr[x<<1|1].r0max;
tr[x].sum1=tr[x<<1].sum1+tr[x<<1|1].sum1;
tr[x].sum0=tr[x<<1].sum0+tr[x<<1|1].sum0;
tr[x].max1=max(tr[x].l1max,max(max(tr[x<<1].max1,max(tr[x<<1|1].max1,tr[x].r1max)),tr[x<<1].r1max+tr[x<<1|1].l1max));
tr[x].max0=max(tr[x].l0max,max(max(tr[x<<1].max0,max(tr[x<<1|1].max0,tr[x].r0max)),tr[x<<1].r0max+tr[x<<1|1].l0max));
}
void pushdown(ll x){
if (tr[x].lz1){
tr[x<<1].sum0=tr[x<<1].len;
tr[x<<1].sum1=0;
tr[x<<1].l0max=tr[x<<1].r0max=tr[x<<1].len;
tr[x<<1].l1max=tr[x<<1].r1max=0;
tr[x<<1].max0=tr[x<<1].len;
tr[x<<1].max1=0;
tr[x<<1|1].sum0=tr[x<<1|1].len;
tr[x<<1|1].sum1=0;
tr[x<<1|1].l0max=tr[x<<1|1].r0max=tr[x<<1|1].len;
tr[x<<1|1].l1max=tr[x<<1|1].r1max=0;
tr[x<<1|1].max0=tr[x<<1|1].len;
tr[x<<1|1].max1=0;
tr[x<<1].lz1=tr[x<<1|1].lz1=1;
tr[x].lz1=0;
}
if (tr[x].lz2){
tr[x<<1].sum1=tr[x<<1].len;
tr[x<<1].sum0=0;
tr[x<<1].l1max=tr[x<<1].r1max=tr[x<<1].len;
tr[x<<1].l0max=tr[x<<1].r0max=0;
tr[x<<1].max1=tr[x<<1].len;
tr[x<<1].max0=0;
tr[x<<1|1].sum1=tr[x<<1|1].len;
tr[x<<1|1].sum0=0;
tr[x<<1|1].l1max=tr[x<<1|1].r1max=tr[x<<1|1].len;
tr[x<<1|1].l0max=tr[x<<1|1].r0max=0;
tr[x<<1|1].max1=tr[x<<1|1].len;
tr[x<<1|1].max0=0;
tr[x<<1].lz2=tr[x<<1|1].lz2=1;
tr[x].lz2=0;
}
if (tr[x].lz3){
swap(tr[x<<1].sum1,tr[x<<1].sum0);
swap(tr[x<<1].l1max,tr[x<<1].l0max);
swap(tr[x<<1].r1max,tr[x<<1].r0max);
swap(tr[x<<1].max1,tr[x<<1].max0);
swap(tr[x<<1|1].sum1,tr[x<<1|1].sum0);
swap(tr[x<<1|1].l1max,tr[x<<1|1].l0max);
swap(tr[x<<1|1].r1max,tr[x<<1|1].r0max);
swap(tr[x<<1|1].max1,tr[x<<1|1].max0);
tr[x<<1].lz3=tr[x<<1|1].lz3=1;
tr[x].lz3=0;
}
}
void build(ll x,ll l,ll r){
tr[x].l=l;
tr[x].r=r;
tr[x].len=r-l+1;
if (l==r){
if (a[l]==1){
tr[x].l1max=1,tr[x].l0max=0;
tr[x].r1max=1,tr[x].r0max=0;
tr[x].sum1=1,tr[x].sum0=0;
tr[x].max1=1,tr[x].max0=0;
}else{
tr[x].l1max=0,tr[x].l0max=1;
tr[x].r1max=0,tr[x].r0max=1;
tr[x].sum1=0,tr[x].sum0=1;
tr[x].max1=0,tr[x].max0=1;
}
return;
}
ll mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pushup(x);
}
void change1(ll x,ll l,ll r){
if (l<=tr[x].l && tr[x].r<=r){
tr[x].sum0=tr[x].len;
tr[x].sum1=0;
tr[x].l0max=tr[x].r0max=tr[x].len;
tr[x].l1max=tr[x].r1max=0;
tr[x].max0=tr[x].len;
tr[x].max1=0;
tr[x].lz1=1;
if (tr[x].lz2)
tr[x].lz2=0;
return;
}
pushdown(x);
ll mid=(tr[x].l+tr[x].r)>>1;
if (l<=mid)
change1(x<<1,l,r);
if (mid+1<=r)
change1(x<<1|1,l,r);
pushup(x);
}
void change2(ll x,ll l,ll r){
if (l<=tr[x].l && tr[x].r<=r){
tr[x].sum1=tr[x].len;
tr[x].sum0=0;
tr[x].l1max=tr[x].r1max=tr[x].len;
tr[x].l0max=tr[x].r0max=0;
tr[x].max1=tr[x].len;
tr[x].max0=0;
tr[x].lz2=1;
if (tr[x].lz1)
tr[x].lz1=0;
return;
}
pushdown(x);
ll mid=(tr[x].l+tr[x].r)>>1;
if (l<=mid)
change2(x<<1,l,r);
if (mid+1<=r)
change2(x<<1|1,l,r);
pushup(x);
}
void change3(ll x,ll l,ll r){
if (l<=tr[x].l && tr[x].r<=r){
// cout<<tr[x].l<<" "<<tr[x].r<<endl;
swap(tr[x].sum1,tr[x].sum0);
swap(tr[x].l1max,tr[x].l0max);
swap(tr[x].r1max,tr[x].r0max);
swap(tr[x].max1,tr[x].max0);
// cout<<"??? "<<tr[x].sum1<<" "<<tr[x].sum0<<endl;
tr[x].lz3=1;
tr[x].lz1^=1;
tr[x].lz2^=1;
return;
}
pushdown(x);
ll mid=(tr[x].l+tr[x].r)>>1;
if (l<=mid)
change3(x<<1,l,r);
if (mid+1<=r)
change3(x<<1|1,l,r);
pushup(x);
// cout<<x<<" "<<tr[x].max1<<endl;
}
ll ask1(ll x,ll l,ll r){
if (l<=tr[x].l && tr[x].r<=r){
return tr[x].sum1;
}
pushdown(x);
ll mid=(tr[x].l+tr[x].r)>>1;
ll res=0;
if (l<=mid)
res+=ask1(x<<1,l,r);
if (mid+1<=r)
res+=ask1(x<<1|1,l,r);
return res;
}
node ask2(ll x,ll l,ll r){
if (l<=tr[x].l && tr[x].r<=r){
return tr[x];
}
pushdown(x);
ll mid=(tr[x].l+tr[x].r)>>1;
if (r<=mid)
return ask2(x<<1,l,r);
else if (mid+1<=l)
return ask2(x<<1|1,l,r);
else{
node a=ask2(x<<1,l,r);
node b=ask2(x<<1|1,l,r);
node c;
c.l1max=c.r1max=c.l0max=c.r0max=0;
c.sum1=c.sum0=0;
c.max1=c.max0=0;
if (a.l1max==a.len)
c.l1max=a.len+b.l1max;
else
c.l1max=a.l1max;
if (b.r1max==b.len)
c.r1max=b.len+a.r1max;
else
c.r1max=b.r1max;
if (a.l0max==a.len)
c.l0max=a.len+b.l0max;
else
c.l0max=a.l0max;
if (b.r0max==b.len)
c.r0max=b.len+a.r0max;
else
c.r0max=b.r0max;
c.sum1=a.sum1+b.sum1;
c.sum0=a.sum0+b.sum0;
c.max1=max(c.l1max,max(max(a.max1,max(b.max1,c.r1max)),a.r1max+b.l1max));
c.max0=max(c.l0max,max(max(a.max0,max(b.max0,c.r0max)),a.r0max+b.l0max));
return c;
}
}
int main(){
cin>>n>>q;
for (int i=1;i<=n;i++)
cin>>a[i];
build(1,1,n);
// cout<<ask2(1,3,10).max1<<endl;
while(q--){
cin>>opt>>l>>r;
opt++;
l++;
r++;
if (opt==1){
change1(1,l,r);
}else if (opt==2){
change2(1,l,r);
}else if (opt==3){
change3(1,l,r);
}else if (opt==4){
cout<<ask1(1,l,r)<<endl;
}else{
cout<<ask2(1,l,r).max1<<endl;
}
// cout<<"TEST: "<<ask1(1,1,10)<<endl;
// cout<<ask2(1,1,5).max1<<endl;
}
}by Hurraciny @ 2024-10-14 14:57:38
建议重构代码