519行优雅分块求调

rt，维护了 7 个东西

块内从左往右极大 1 串长度

块内从左往右极大 0 串长度

块内从右往左极大 1 串长度

块内从右往左极大 0 串长度

块内最大 1 串长度

块内最大 0 串长度

块内 1 的个数

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
template<typename T>inline T read(){
    T a=0;bool s=0;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')s^=1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        a=(a<<3)+(a<<1)+(ch^48);
        ch=getchar();
    }
    return s?-a:a;
}
const int mn=1e5+10;
int n,m,sqr,tot;
int a[mn],tag[mn],maxx1[mn],maxx0[mn],l[mn],r[mn],bel[mn],l0[mn],l1[mn],r0[mn],r1[mn],cnt1[mn];
inline void init(){
    tot=sqr=sqrt(n);
    if(n%sqr)tot++;
    for(int i=1;i<=tot;i++)
        l[i]=(i-1)*sqr+1,r[i]=i*sqr;
    r[tot]=n;
    for(int i=1;i<=n;i++)
        bel[i]=(i-1)/sqr+1;
    for(int i=1;i<=tot;i++){
        for(int j=l[i];j<=r[i];j++)
            if(a[i])l1[i]++;
            else break;
        for(int j=r[i];j>=l[i];j--)
            if(a[i])r1[i]++;
            else break;
        for(int j=l[i];j<=r[i];j++)
            if(!a[i])l0[i]++;
            else break;
        for(int j=r[i];j>=l[i];j--)
            if(!a[i])r0[i]++;
            else break;
        int cnt=0;
        for(int j=l[i];j<=r[i];j++){
            if(a[i])cnt++;
            else cnt=0;
            maxx1[i]=max(maxx1[i],cnt);
        }
        cnt=0;
        for(int j=l[i];j<=r[i];j++){
            if(!a[i])cnt++;
            else cnt=0;
            maxx0[i]=max(maxx0[i],cnt);
        }
        for(int j=l[i];j<=r[i];j++)
            cnt1[i]+=a[i];
    }
}
inline void cg0(int L,int R){
    int lx=bel[L],rx=bel[R];
    if(lx==rx){
        if(tag[lx])
            for(int i=l[lx];i<=r[lx];i++){
                if(tag[lx]==2)a[i]=0;
                if(tag[lx]==1)a[i]=1;
                if(tag[lx]==3)a[i]^=1;
            }
        tag[lx]=0;
        for(int i=L;i<=R;i++)
            a[i]=0;
        cnt1[lx]=0;
        l1[lx]=l0[lx]=r1[lx]=r0[lx]=maxx1[lx]=maxx0[lx]=0;
        for(int i=l[lx];i<=r[lx];i++)
            if(a[i])l1[lx]++;
            else break;
        for(int i=r[lx];i>=l[lx];i--)
            if(a[i])r1[lx]++;
            else break;
        for(int i=l[lx];i<=r[lx];i++)
            if(!a[i])l0[lx]++;
            else break;
        for(int i=r[lx];i>=l[lx];i--)
            if(!a[i])r0[lx]++;
            else break;
        int cnt=0;
        for(int i=l[lx];i<=r[lx];i++){
            if(a[i])cnt++;
            else cnt=0;
            maxx1[lx]=max(maxx1[lx],cnt);
        }
        cnt=0;
        for(int i=l[lx];i<=r[lx];i++){
            if(!a[i])cnt++;
            else cnt=0;
            maxx0[lx]=max(maxx0[lx],cnt);
        }
        for(int i=l[lx];i<=r[lx];i++)
            cnt1[lx]+=a[i];
        return;
    }
    if(tag[lx])
        for(int i=l[lx];i<=r[lx];i++){
            if(tag[lx]==2)a[i]=0;
            if(tag[lx]==1)a[i]=1;
            if(tag[lx]==3)a[i]^=1;
        }
    tag[lx]=0;
    for(int i=L;i<=r[lx];i++)
        a[i]=0;
    cnt1[lx]=0;
    l1[lx]=l0[lx]=r1[lx]=r0[lx]=maxx1[lx]=maxx0[lx]=0;
    for(int i=l[lx];i<=r[lx];i++)
        if(a[i])l1[lx]++;
        else break;
    for(int i=r[lx];i>=l[lx];i--)
        if(a[i])r1[lx]++;
        else break;
    for(int i=l[lx];i<=r[lx];i++)
        if(!a[i])l0[lx]++;
        else break;
    for(int i=r[lx];i>=l[lx];i--)
        if(!a[i])r0[lx]++;
        else break;
    int cnt=0;
    for(int i=l[lx];i<=r[lx];i++){
        if(a[i])cnt++;
        else cnt=0;
        maxx1[lx]=max(maxx1[lx],cnt);
    }
    cnt=0;
    for(int i=l[lx];i<=r[lx];i++){
        if(!a[i])cnt++;
        else cnt=0;
        maxx0[lx]=max(maxx0[lx],cnt);
    }
    for(int i=l[lx];i<=r[lx];i++)
        cnt1[lx]+=a[i];
    for(int i=lx+1;i<rx;i++)
        tag[i]=2,maxx1[i]=l1[i]=r1[i]=cnt1[i]=0,maxx0[i]=l0[i]=r0[i]=r[i]-l[i]+1;
    if(tag[rx])
        for(int i=l[rx];i<=r[rx];i++){
            if(tag[rx]==2)a[i]=0;
            if(tag[rx]==1)a[i]=1;
            if(tag[rx]==3)a[i]^=1;
        }
    tag[rx]=0;
    for(int i=l[rx];i<=R;i++)
        a[i]=0;
    cnt1[rx]=0;
    l1[rx]=l0[rx]=r1[rx]=r0[rx]=maxx1[rx]=maxx0[rx]=0;
    for(int i=l[rx];i<=r[rx];i++)
        if(a[i])l1[rx]++;
        else break;
    for(int i=r[rx];i>=l[rx];i--)
        if(a[i])r1[rx]++;
        else break;
    for(int i=l[rx];i<=r[rx];i++)
        if(!a[i])l0[rx]++;
        else break;
    for(int i=r[rx];i>=l[rx];i--)
        if(!a[i])r0[rx]++;
        else break;
    cnt=0;
    for(int i=l[rx];i<=r[rx];i++){
        if(a[i])cnt++;
        else cnt=0;
        maxx1[rx]=max(maxx1[rx],cnt);
    }
    cnt=0;
    for(int i=l[rx];i<=r[rx];i++){
        if(!a[i])cnt++;
        else cnt=0;
        maxx0[rx]=max(maxx0[rx],cnt);
    }
    for(int i=l[rx];i<=r[rx];i++)
        cnt1[rx]+=a[i];
}
inline void cg1(int L,int R){
    int lx=bel[L],rx=bel[R];
    if(lx==rx){
        if(tag[lx])
            for(int i=l[lx];i<=r[lx];i++){
                if(tag[lx]==2)a[i]=0;
                if(tag[lx]==1)a[i]=1;
                if(tag[lx]==3)a[i]^=1;
            }
        tag[lx]=0;
        for(int i=L;i<=R;i++)
            a[i]=1;
        cnt1[lx]=0;
        l1[lx]=l0[lx]=r1[lx]=r0[lx]=maxx1[lx]=maxx0[lx]=0;
        for(int i=l[lx];i<=r[lx];i++)
            if(a[i])l1[lx]++;
            else break;
        for(int i=r[lx];i>=l[lx];i--)
            if(a[i])r1[lx]++;
            else break;
        for(int i=l[lx];i<=r[lx];i++)
            if(!a[i])l0[lx]++;
            else break;
        for(int i=r[lx];i>=l[lx];i--)
            if(!a[i])r0[lx]++;
            else break;
        int cnt=0;
        for(int i=l[lx];i<=r[lx];i++){
            if(a[i])cnt++;
            else cnt=0;
            maxx1[lx]=max(maxx1[lx],cnt);
        }
        cnt=0;
        for(int i=l[lx];i<=r[lx];i++){
            if(!a[i])cnt++;
            else cnt=0;
            maxx0[lx]=max(maxx0[lx],cnt);
        }
        for(int i=l[lx];i<=r[lx];i++)
            cnt1[lx]+=a[i];
        return;
    }
    if(tag[lx])
        for(int i=l[lx];i<=r[lx];i++){
            if(tag[lx]==2)a[i]=0;
            if(tag[lx]==1)a[i]=1;
            if(tag[lx]==3)a[i]^=1;
        }
    tag[lx]=0;
    for(int i=L;i<=r[lx];i++)
        a[i]=1;
    cnt1[lx]=0;
    l1[lx]=l0[lx]=r1[lx]=r0[lx]=maxx1[lx]=maxx0[lx]=0;
    for(int i=l[lx];i<=r[lx];i++)
        if(a[i])l1[lx]++;
        else break;
    for(int i=r[lx];i>=l[lx];i--)
        if(a[i])r1[lx]++;
        else break;
    for(int i=l[lx];i<=r[lx];i++)
        if(!a[i])l0[lx]++;
        else break;
    for(int i=r[lx];i>=l[lx];i--)
        if(!a[i])r0[lx]++;
        else break;
    int cnt=0;
    for(int i=l[lx];i<=r[lx];i++){
        if(a[i])cnt++;
        else cnt=0;
        maxx1[lx]=max(maxx1[lx],cnt);
    }
    cnt=0;
    for(int i=l[lx];i<=r[lx];i++){
        if(!a[i])cnt++;
        else cnt=0;
        maxx0[lx]=max(maxx0[lx],cnt);
    }
    for(int i=l[lx];i<=r[lx];i++)
        cnt1[lx]+=a[i];
    for(int i=lx+1;i<rx;i++)
        tag[i]=1,maxx0[i]=l0[i]=r0[i]=0,maxx1[i]=l1[i]=r1[i]=cnt1[i]=r[i]-l[i]+1;
    if(tag[rx])
        for(int i=l[rx];i<=r[rx];i++){
            if(tag[rx]==2)a[i]=0;
            if(tag[rx]==1)a[i]=1;
            if(tag[rx]==3)a[i]^=1;
        }
    tag[rx]=0;
    for(int i=l[rx];i<=R;i++)
        a[i]=1;
    cnt1[rx]=0;
    l1[rx]=l0[rx]=r1[rx]=r0[rx]=maxx1[rx]=maxx0[rx]=0;
    for(int i=l[rx];i<=r[rx];i++)
        if(a[i])l1[rx]++;
        else break;
    for(int i=r[rx];i>=l[rx];i--)
        if(a[i])r1[rx]++;
        else break;
    for(int i=l[rx];i<=r[rx];i++)
        if(!a[i])l0[rx]++;
        else break;
    for(int i=r[rx];i>=l[rx];i--)
        if(!a[i])r0[rx]++;
        else break;
    cnt=0;
    for(int i=l[rx];i<=r[rx];i++){
        if(a[i])cnt++;
        else cnt=0;
        maxx1[rx]=max(maxx1[rx],cnt);
    }
    cnt=0;
    for(int i=l[rx];i<=r[rx];i++){
        if(!a[i])cnt++;
        else cnt=0;
        maxx0[rx]=max(maxx0[rx],cnt);
    }
    for(int i=l[rx];i<=r[rx];i++)
        cnt1[rx]+=a[i];
}
inline void cg2(int L,int R){
    int lx=bel[L],rx=bel[R];
    if(lx==rx){
        if(tag[lx])
            for(int i=l[lx];i<=r[lx];i++){
                if(tag[lx]==2)a[i]=0;
                if(tag[lx]==1)a[i]=1;
                if(tag[lx]==3)a[i]^=1;
            }
        tag[lx]=0;
        for(int i=L;i<=R;i++)
            a[i]^=1;
        cnt1[lx]=0;
        l1[lx]=l0[lx]=r1[lx]=r0[lx]=maxx1[lx]=maxx0[lx]=0;
        for(int i=l[lx];i<=r[lx];i++)
            if(a[i])l1[lx]++;
            else break;
        for(int i=r[lx];i>=l[lx];i--)
            if(a[i])r1[lx]++;
            else break;
        for(int i=l[lx];i<=r[lx];i++)
            if(!a[i])l0[lx]++;
            else break;
        for(int i=r[lx];i>=l[lx];i--)
            if(!a[i])r0[lx]++;
            else break;
        int cnt=0;
        for(int i=l[lx];i<=r[lx];i++){
            if(a[i])cnt++;
            else cnt=0;
            maxx1[lx]=max(maxx1[lx],cnt);
        }
        cnt=0;
        for(int i=l[lx];i<=r[lx];i++){
            if(!a[i])cnt++;
            else cnt=0;
            maxx0[lx]=max(maxx0[lx],cnt);
        }
        for(int i=l[lx];i<=r[lx];i++)
            cnt1[lx]+=a[i];
        return;
    }
    if(tag[lx])
        for(int i=l[lx];i<=r[lx];i++){
            if(tag[lx]==2)a[i]=0;
            if(tag[lx]==1)a[i]=1;
            if(tag[lx]==3)a[i]^=1;
        }
    tag[lx]=0;
    for(int i=L;i<=r[lx];i++)
        a[i]^=1;
    cnt1[lx]=0;
    l1[lx]=l0[lx]=r1[lx]=r0[lx]=maxx1[lx]=maxx0[lx]=0;
    for(int i=l[lx];i<=r[lx];i++)
        if(a[i])l1[lx]++;
        else break;
    for(int i=r[lx];i>=l[lx];i--)
        if(a[i])r1[lx]++;
        else break;
    for(int i=l[lx];i<=r[lx];i++)
        if(!a[i])l0[lx]++;
        else break;
    for(int i=r[lx];i>=l[lx];i--)
        if(!a[i])r0[lx]++;
        else break;
    int cnt=0;
    for(int i=l[lx];i<=r[lx];i++){
        if(a[i])cnt++;
        else cnt=0;
        maxx1[lx]=max(maxx1[lx],cnt);
    }
    cnt=0;
    for(int i=l[lx];i<=r[lx];i++){
        if(!a[i])cnt++;
        else cnt=0;
        maxx0[lx]=max(maxx0[lx],cnt);
    }
    for(int i=l[lx];i<=r[lx];i++)
        cnt1[lx]+=a[i];
    for(int i=lx+1;i<rx;i++){
        if(tag[i]==2)tag[i]=1,maxx1[i]=maxx0[i]=l1[i]=l0[i]=r1[i]=r0[i]=1;
        else if(tag[i]==1)tag[i]=2,maxx1[i]=maxx0[i]=l1[i]=l0[i]=r1[i]=r0[i]=0;
        else tag[i]=3,swap(maxx1[i],maxx0[i]),swap(l1[i],l0[i]),swap(r1[i],r0[i]);
        cnt1[i]=r[i]-l[i]+1-cnt1[i];
    }
    if(tag[rx])
        for(int i=l[rx];i<=r[rx];i++){
            if(tag[rx]==2)a[i]=0;
            if(tag[rx]==1)a[i]=1;
            if(tag[rx]==3)a[i]^=1;
        }
    tag[rx]=0;
    for(int i=l[rx];i<=R;i++)
        a[i]^=1;
    cnt1[rx]=0;
    l1[rx]=l0[rx]=r1[rx]=r0[rx]=maxx1[rx]=maxx0[rx]=0;
    for(int i=l[rx];i<=r[rx];i++)
        if(a[i])l1[rx]++;
        else break;
    for(int i=r[rx];i>=l[rx];i--)
        if(a[i])r1[rx]++;
        else break;
    for(int i=l[rx];i<=r[rx];i++)
        if(!a[i])l0[rx]++;
        else break;
    for(int i=r[rx];i>=l[rx];i--)
        if(!a[i])r0[rx]++;
        else break;
    cnt=0;
    for(int i=l[rx];i<=r[rx];i++){
        if(a[i])cnt++;
        else cnt=0;
        maxx1[rx]=max(maxx1[rx],cnt);
    }
    cnt=0;
    for(int i=l[rx];i<=r[rx];i++){
        if(!a[i])cnt++;
        else cnt=0;
        maxx0[rx]=max(maxx0[rx],cnt);
    }
    for(int i=l[rx];i<=r[rx];i++)
        cnt1[rx]+=a[i];
}
inline int ask3(int L,int R){
    int lx=bel[L],rx=bel[R];
    if(lx==rx){
        int ans=0;
        if(tag[lx])
            for(int i=l[lx];i<=r[lx];i++){
                if(tag[lx]==2)a[i]=0;
                if(tag[lx]==1)a[i]=1;
                if(tag[lx]==3)a[i]^=1;
            }
        tag[lx]=0;
        for(int i=L;i<=R;i++)
            ans+=a[i];
        return ans;
    }
    int ans=0;
    if(tag[lx])
        for(int i=l[lx];i<=r[lx];i++){
            if(tag[lx]==2)a[i]=0;
            if(tag[lx]==1)a[i]=1;
            if(tag[lx]==3)a[i]^=1;
        }
    tag[lx]=0;
    for(int i=L;i<=r[lx];i++)
        ans+=a[i];
    for(int i=lx+1;i<rx;i++)
        ans+=cnt1[i];
    if(tag[rx])
        for(int i=l[rx];i<=r[rx];i++){
            if(tag[rx]==2)a[i]=0;
            if(tag[rx]==1)a[i]=1;
            if(tag[rx]==3)a[i]^=1;
        }
    tag[rx]=0;
    for(int i=l[rx];i<=R;i++)
        ans+=a[i];
    return ans;
}
inline int ask4(int L,int R){
    int lx=bel[L],rx=bel[R];
    if(lx==rx){
        int ans=0;
        if(tag[lx])
            for(int i=l[lx];i<=r[lx];i++){
                if(tag[lx]==2)a[i]=0;
                if(tag[lx]==1)a[i]=1;
                if(tag[lx]==3)a[i]^=1;
            }
        tag[lx]=0;
        int cnt=0;
        for(int i=L;i<=R;i++)
            if(a[i])cnt++;
            else ans=max(ans,cnt),cnt=0;
        return ans;
    }
    int ans=0;
    if(tag[lx])
        for(int i=l[lx];i<=r[lx];i++){
            if(tag[lx]==2)a[i]=0;
            if(tag[lx]==1)a[i]=1;
            if(tag[lx]==3)a[i]^=1;
        }
    tag[lx]=0;
    int cnt=0;
    for(int i=L;i<=r[lx];i++)
        if(a[i])cnt++;
        else ans=max(ans,cnt),cnt=0;
    cnt=min(r[lx]-L+1,r1[lx]);
    for(int i=lx+1;i<rx;i++){
        ans=max(ans,maxx1[i]);
        if(maxx1[i]==r[i]-l[i]+1)
            cnt+=maxx1[i];
        else ans=max(ans,cnt+l1[i]),cnt=r1[i];
        ans=max(ans,cnt);
    }
    if(tag[rx])
        for(int i=l[rx];i<=r[rx];i++){
            if(tag[rx]==2)a[i]=0;
            if(tag[rx]==1)a[i]=1;
            if(tag[rx]==3)a[i]^=1;
        }
    tag[rx]=0;
    ans=max(ans,cnt+min(l1[rx],R-l[rx]+1));
    return ans;
}
int main(){
    n=read<int>();m=read<int>();
    for(int i=1;i<=n;i++)
        a[i]=read<int>();
    init();
    for(int i=1;i<=m;i++){
        int op=read<int>();
        int L=read<int>()+1,R=read<int>()+1;
        if(op==0)cg0(L,R);
        if(op==1)cg1(L,R);
        if(op==2)cg2(L,R);
        if(op==3)printf("%d\n",ask3(L,R));
        if(op==4)printf("%d\n",ask4(L,R));
    }
    // while(1)getchar();
    return 0;
}