sjzsd147 @ 2024-11-27 21:29:50
rt，自认码风良好（）
hack 和前两个点过了。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m;
int len[MAXN<<2][2],ren[MAXN<<2][2];
int men[MAXN<<2][2],cnt[MAXN<<2];
int lztag[MAXN<<2],rev[MAXN<<2];
int a[MAXN];
#define ls (o<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
void pushup(int o,int l,int r){
cnt[o]=cnt[ls]+cnt[rs];
for(int i=0;i<2;i++){
if(len[ls][i]==mid-l+1){
len[o][i]=len[ls][i]+len[rs][i];
}else{
len[o][i]=len[ls][i];
}
if(ren[rs][i]==r-mid){
ren[o][i]=ren[ls][i]+ren[rs][i];
}else{
ren[o][i]=ren[rs][i];
}
men[o][i]=max({men[ls][i],men[rs][i],ren[ls][i]+len[rs][i]});
}
}
void pushdown(int o,int l,int r){
if(lztag[o]!=-1){
lztag[ls]=lztag[rs]=lztag[o];
rev[ls]=rev[rs]=0;
len[ls][lztag[o]]=ren[ls][lztag[o]]=men[ls][lztag[o]]=mid-l+1;
len[rs][lztag[o]]=ren[rs][lztag[o]]=men[rs][lztag[o]]=r-mid;
len[ls][lztag[o]^1]=ren[ls][lztag[o]^1]=men[ls][lztag[o]^1]=0;
len[rs][lztag[o]^1]=ren[rs][lztag[o]^1]=men[rs][lztag[o]^1]=0;
if(lztag[o]==1){
cnt[ls]=mid-l+1;
cnt[rs]=r-mid;
}else{
cnt[ls]=cnt[rs]=0;
}
lztag[o]=-1;
}else if(rev[o]){
swap(len[ls][0],len[ls][1]);
swap(ren[ls][0],ren[ls][1]);
swap(men[ls][0],men[ls][1]);
swap(len[rs][0],len[rs][1]);
swap(ren[rs][0],ren[rs][1]);
swap(men[rs][0],men[rs][1]);
cnt[ls]=mid-l+1-cnt[ls];
cnt[rs]=r-mid-cnt[rs];
rev[ls]^=1;
rev[rs]^=1;
if(lztag[ls]!=-1){
lztag[ls]^=1;
}
if(lztag[rs]!=-1){
lztag[rs]^=1;
}
rev[o]=0;
}
}
void build(int o,int l,int r){
lztag[o]=-1;
if(l==r){
len[o][a[l]]=ren[o][a[l]]=men[o][a[l]]=1;
cnt[o]=a[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(o,l,r);
}
void modify(int o,int l,int r,int ll,int rr,int v){
if(l>=ll&&r<=rr){
rev[o]=0;
lztag[o]=v;
len[o][v]=ren[o][v]=men[o][v]=r-l+1;
len[o][v^1]=ren[o][v^1]=men[o][v^1]=0;
if(v){
cnt[o]=r-l+1;
}else{
cnt[o]=0;
}
return;
}
pushdown(o,l,r);
if(ll<=mid){
modify(ls,l,mid,ll,rr,v);
}
if(rr>mid){
modify(rs,mid+1,r,ll,rr,v);
}
pushup(o,l,r);
}
void reverse(int o,int l,int r,int ll,int rr){
if(l>=ll&&r<=rr){
rev[o]^=1;
if(lztag[o]!=-1){
lztag[o]^=1;
}
swap(len[o][0],len[o][1]);
swap(ren[o][0],ren[o][1]);
swap(men[o][0],men[o][1]);
cnt[o]=r-l+1-cnt[o];
return;
}
pushdown(o,l,r);
if(ll<=mid){
reverse(ls,l,mid,ll,rr);
}
if(rr>mid){
reverse(rs,mid+1,r,ll,rr);
}
pushup(o,l,r);
}
int query1(int o,int l,int r,int ll,int rr){
if(l>=ll&&r<=rr){
return cnt[o];
}
pushdown(o,l,r);
int res=0;
if(ll<=mid){
res+=query1(ls,l,mid,ll,rr);
}
if(rr>mid){
res+=query1(rs,mid+1,r,ll,rr);
}
return res;
}
tuple<int,int,int> query2(int o,int l,int r,int ll,int rr){
if(l>=ll&&r<=rr){
return {len[o][1],men[o][1],ren[o][1]};
}
pushdown(o,l,r);
if(ll<=mid&&rr>mid){
auto [ul,vl,wl]=query2(ls,l,mid,ll,rr);
auto [ur,vr,wr]=query2(rs,mid+1,r,ll,rr);
int u=0,v=0,w=0;
if(ul==mid-l+1){
u=ul+ur;
}else{
u=ul;
}
if(wr==r-mid){
w=wl+wr;
}else{
w=wr;
}
v=max({vl,vr,wl+ur});
return {u,v,w};
}else if(rr<=mid){
return query2(ls,l,mid,ll,rr);
}else if(ll>mid){
return query2(rs,mid+1,r,ll,rr);
}
}
void check(int o,int l,int r){
cout<<l<<" "<<r<<":\n";
cout<<cnt[o]<<"\n";
cout<<len[o][0]<<" "<<men[o][0]<<" "<<ren[o][0]<<"\n";
cout<<len[o][1]<<" "<<men[o][1]<<" "<<ren[o][1]<<"\n";
if(l==r) return;
pushdown(o,l,r);
check(ls,l,mid);
check(rs,mid+1,r);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
// check(1,1,n);
while(m--){
int op,l,r;
cin>>op>>l>>r;
l++;r++;
if(op==0){
modify(1,1,n,l,r,0);
}else if(op==1){
modify(1,1,n,l,r,1);
}else if(op==2){
reverse(1,1,n,l,r);
}else if(op==3){
cout<<query1(1,1,n,l,r)<<"\n";
}else if(op==4){
cout<<get<1>(query2(1,1,n,l,r))<<"\n";
}
// check(1,1,n);
}
}