只過了 HAck 秋條

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e5+5;
int n,m;
int op,l,r;
int a[N];
int tree[N<<2];
int tag1[N<<2],tag2[N<<2];
int max1[N<<2],l1[N<<2],r1[N<<2];
int max0[N<<2],l0[N<<2],r0[N<<2];
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
struct Tree
{
    int max1,l1,r1;
    int max0,l0,r0;
    int tree;
};
void push_up(int s,int t,int p)
{
    int mid=s+((t-s)>>1);
    tree[p]=tree[ls(p)]+tree[rs(p)];
    max1[p]=max(r1[ls(p)]+l1[rs(p)],max(max1[ls(p)],max1[rs(p)]));
    max0[p]=max(r0[ls(p)]+l0[rs(p)],max(max0[ls(p)],max0[rs(p)]));
    l1[p]=l1[ls(p)];
    r1[p]=r1[rs(p)];
    l0[p]=l0[ls(p)];
    r0[p]=r0[rs(p)];
    int lenl=mid-s+1,lenr=t-mid;
    if(lenl==tree[ls(p)]) l1[p]+=l1[rs(p)];
    if(tree[ls(p)]==0) l0[p]+=l0[rs(p)];
    if(lenr==tree[rs(p)]) r1[p]+=r1[ls(p)];
    if(tree[rs(p)]==0) r0[p]+=r0[ls(p)];
}
void build(int s,int t,int p)
{
    tag1[p]=-1;
    if(s==t)
    {
        tree[p]=max1[p]=l1[p]=r1[p]=a[s];
        max0[p]=l0[p]=r0[p]=!a[s];
        return;
    }
    int mid=s+((t-s)>>1);
    build(s,mid,ls(p));
    build(mid+1,t,rs(p));
    push_up(s,t,p);
}
void push_down(int s,int t,int p)
{
    int mid=s+((t-s)>>1);
    if(tag2[p])
    {
        tree[ls(p)]=mid-s+1-tree[ls(p)];
        tree[rs(p)]=t-mid-tree[rs(p)];
        swap(max1[ls(p)],max0[ls(p)]);
        swap(max1[rs(p)],max0[rs(p)]);
        swap(l1[ls(p)],l0[ls(p)]);
        swap(l1[rs(p)],l0[rs(p)]);
        swap(r1[ls(p)],r0[ls(p)]);
        swap(r1[rs(p)],r0[rs(p)]);
        tag2[ls(p)]=tag2[rs(p)]=1;
        tag2[p]=0;
    }
    if(tag1[p]!=-1)
    {
        if(tag1[p])
        {
            tree[ls(p)]=max1[ls(p)]=l1[ls(p)]=r1[ls(p)]=mid-s+1;
            tree[rs(p)]=max1[rs(p)]=l1[rs(p)]=r1[rs(p)]=t-mid;
            max0[ls(p)]=l0[ls(p)]=r0[ls(p)]=max0[rs(p)]=l0[rs(p)]=r0[rs(p)]=0;
            tag1[ls(p)]=tag1[rs(p)]=1;
            tag1[p]=-1;
        }
        else
        {
            tree[ls(p)]=tree[rs(p)]=max1[ls(p)]=max1[rs(p)]=l1[ls(p)]=l1[rs(p)]=r1[ls(p)]=r1[rs(p)]=0;
            max0[ls(p)]=l0[ls(p)]=r0[ls(p)]=mid-s+1;
            max0[rs(p)]=l0[rs(p)]=r0[rs(p)]=t-mid;
            tag1[ls(p)]=tag1[rs(p)]=0;
            tag1[p]=-1;
        }
    }
}
void update(int l,int r,int k,int s,int t,int p)
{
    if(l<=s and t<=r)
    {
        tree[p]=(t-s+1)*k;
        tag1[p]=k;
        if(k)
        {
            max1[p]=l1[p]=r1[p]=t-s+1;
            max0[p]=l0[p]=r0[p]=0;
        }
        else
        {
            max1[p]=l1[p]=r1[p]=0;
            max0[p]=l0[p]=r0[p]=t-s+1;
        }
        return;
    }
    int mid=s+((t-s)>>1);
    push_down(s,t,p);
    if(l<=mid) update(l,r,k,s,mid,ls(p));
    if(mid+1<=r) update(l,r,k,mid+1,t,rs(p));
    push_up(s,t,p);
}
void change(int l,int r,int s,int t,int p)
{
    if(l<=s and t<=r)
    {
        tag1[p]=-1;
        tag2[p]=!tag2[p];
        tree[p]=t-s+1-tree[p];
        swap(max1[p],max0[p]);
        swap(l1[p],l0[p]);
        swap(r1[p],r0[p]);
        return;
    }
    int mid=s+((t-s)>>1);
    push_down(s,t,p);
    if(l<=mid) change(l,r,s,mid,ls(p));
    if(mid+1<=r) change(l,r,mid+1,t,rs(p));
    push_up(s,t,p);
}
int query(int l,int r,int s,int t,int p)
{
    if(l<=s and t<=r) return tree[p];
    int mid=s+((t-s)>>1);
    push_down(s,t,p);
    int ans=0;
    if(l<=mid) ans+=query(l,r,s,mid,ls(p));
    if(mid+1<=r) ans+=query(l,r,mid+1,t,rs(p));
    return ans;
}
Tree query1(int l,int r,int s,int t,int p)
{
    if(l<=s and t<=r) return (Tree){max1[p],l1[p],r1[p],max0[p],l0[p],r0[p],tree[p]};
    int mid=s+((t-s)>>1);
    push_down(s,t,p);
    Tree ans;
    if(l<=mid and mid+1>r) return query1(l,r,s,mid,ls(p));
    if(mid+1<=r and l>mid) return query1(l,r,mid+1,r,rs(p));
    Tree ll=query1(l,r,s,mid,ls(p)),rr=query1(l,r,mid+1,t,rs(p));
    ans.tree=ll.tree+rr.tree;
    ans.max1=max(ll.r1+rr.l1,max(ll.max1,rr.max1));
    ans.max0=max(ll.r0+rr.l0,max(ll.max0,rr.max0));
    ans.l1=ll.l1;
    ans.r1=rr.r1;
    ans.l0=ll.l0;
    ans.r0=rr.r0;
    if(mid-s+1==ll.tree) ans.l1=ll.tree+rr.l1;
    if(ll.tree==0) ans.l0=mid-s+1+rr.l0;
    if(t-mid==rr.tree) ans.r1=rr.tree+ll.r1;
    if(rr.tree==0) ans.r0=t-mid+ll.r0;
    return ans;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,1);
    while(m--)
    {
        cin>>op>>l>>r;
        ++l,++r;
        if(op<=1) update(l,r,op,1,n,1);
        else if(op==2) change(l,r,1,n,1);
        else if(op==3) cout<<query(l,r,1,n,1)<<'\n';
        else cout<<query1(l,r,1,n,1).max1<<'\n';
    }
    return 0;
}
//10 3 0 0 0 0 0 0 0 0 0 0