MnZn20分求调

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n,m,a[N];
struct T{
    int l;
    int r;
    int cnt;
    int cntl;
    int cntm;
    int cntr;
    int cntl_2;
    int cntm_2;
    int cntr_2;
    int lazy; 
    int lazy2;
}t[N*4];
void pushup(int i){
    t[i].cnt=t[i*2].cnt+t[i*2+1].cnt;
    if(t[i*2].cnt==(t[i*2].r-t[i*2].l+1)){
        t[i].cntl=t[i*2].cnt+t[i*2+1].cntl;
    }
    else t[i].cntl=t[i*2].cntl;
    if(t[i*2+1].cnt==(t[i*2+1].r-t[i*2+1].l+1)){
        t[i].cntr=t[i*2+1].cnt+t[i*2].cntr; 
    }
    else t[i].cntr=t[i*2+1].cntr;
    t[i].cntm=max(max(t[i*2].cntm,t[i*2+1].cntm),t[i*2].cntr+t[i*2+1].cntl);
    if(t[i*2].cnt==0){
        t[i].cntl_2=(t[i*2].r-t[i*2].l+1)+t[i*2+1].cntl_2;
    }
    else t[i].cntl_2=t[i*2].cntl_2;
    if(t[i*2+1].cnt==0){
        t[i].cntr_2=(t[i*2+1].r-t[i*2+1].l+1)+t[i*2].cntr_2; 
    }
    else t[i].cntr_2=t[i*2+1].cntr_2;
    t[i].cntm_2=max(max(t[i*2].cntm_2,t[i*2+1].cntm_2),t[i*2].cntr_2+t[i*2+1].cntl_2);
}
void pushdown(int i){
    if(t[i].lazy!=-1){
        t[i].lazy2=0; 
        t[i*2].lazy=t[i].lazy;
        t[i*2+1].lazy=t[i].lazy;
        t[i*2].lazy2=0;
        t[i*2+1].lazy2=0;
        t[i*2].cntl=t[i*2].cntr=t[i*2].cntm=t[i*2].cnt=t[i].lazy*(t[i*2].r-t[i*2].l+1);
        t[i*2].cntl_2=t[i*2].cntm_2=t[i*2].cntr_2=(1-t[i].lazy)*(t[i*2].r-t[i*2].l+1);
        t[i*2+1].cntl=t[i*2+1].cntr=t[i*2+1].cntm=t[i*2+1].cnt=t[i].lazy*(t[i*2+1].r-t[i*2+1].l+1);
        t[i*2+1].cntl_2=t[i*2+1].cntm_2=t[i*2+1].cntr_2=(1-t[i].lazy)*(t[i*2+1].r-t[i*2+1].l+1);
        t[i].lazy=-1;
    }
    if(t[i].lazy2!=0){
        t[i*2].cnt=(t[i*2].r-t[i*2].l+1)-t[i*2].cnt;
        t[i*2+1].cnt=(t[i*2+1].r-t[i*2+1].l+1)-t[i*2+1].cnt;
        if(t[i*2].lazy!=-1){
            t[i*2].lazy^=1; 
        }
        else t[i*2].lazy2^=1;
        if(t[i*2+1].lazy!=-1){
            t[i*2+1].lazy^=1;
        }
        else t[i*2+1].lazy2^=1;
        swap(t[i*2].cntl,t[i*2].cntl_2);
        swap(t[i*2].cntm,t[i*2].cntm_2);
        swap(t[i*2].cntr,t[i*2].cntr_2);
        swap(t[i*2+1].cntl,t[i*2+1].cntl_2);
        swap(t[i*2+1].cntm,t[i*2+1].cntm_2);
        swap(t[i*2+1].cntr,t[i*2+1].cntr_2);
        t[i].lazy2=0;
    }
}
void build(int i,int l,int r){
    t[i].l=l;
    t[i].r=r;
    t[i].lazy=-1;
    t[i].lazy2=0;
    if(l==r){
        t[i].cnt=t[i].cntl=t[i].cntm=t[i].cntr=a[l];
        t[i].cntl_2=t[i].cntm_2=t[i].cntr_2=(1-a[l]);
        return;
    }
    int mid=(l+r)/2;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    pushup(i);
}
void update(int i,int l,int r,int x){
    if(t[i].l==l&&t[i].r==r){
        if(x==0||x==1){
            t[i].cnt=t[i].cntl=t[i].cntr=t[i].cntm=x*(t[i].r-t[i].l+1);
            t[i].cntl_2=t[i].cntm_2=t[i].cntr_2=(1-x)*(t[i].r-t[i].l+1);
            t[i].lazy=x;
        }
        else{
            t[i].cnt=(t[i].r-t[i].l+1)-t[i].cnt;
            swap(t[i].cntl,t[i].cntl_2);
            swap(t[i].cntm,t[i].cntm_2);
            swap(t[i].cntr,t[i].cntr_2);
            t[i].lazy2^=1;
        }
        return;
    }
    pushdown(i);
    int mid=(t[i].l+t[i].r)/2;
    if(r<=mid){
        update(i*2,l,r,x);
    }
    else if(l>mid){
        update(i*2+1,l,r,x);
    }
    else{
        update(i*2,l,mid,x);
        update(i*2+1,mid+1,r,x);
    }
    pushup(i);
}
int query(int i,int l,int r){
    if(t[i].l==l&&t[i].r==r){
        return t[i].cnt;
    }   
    pushdown(i);
    int mid=(t[i].l+t[i].r)/2;
    if(r<=mid){
        return query(i*2,l,r);
    }
    else if(l>mid){
        return query(i*2+1,l,r);
    }
    else{
        return query(i*2,l,mid)+query(i*2+1,mid+1,r);
    }
}
T query2(int i,int l,int r){
    if(t[i].l==l&&t[i].r==r){
        return t[i];
    }
    pushdown(i);
    T ans;
    int mid=(t[i].l+t[i].r)/2;
    if(r<=mid){
        return query2(i*2,l,r);
    }
    else if(l>mid){
        return query2(i*2+1,l,r);
    }
    else{
        T left=query2(i*2,l,mid);
        T right=query2(i*2+1,mid+1,r);
        ans.cnt=left.cnt+right.cnt;
        if(left.cnt==(left.r-left.l+1)){
            ans.cntl=left.cnt+right.cntl;
        }
        else ans.cntl=left.cntl;
        if(right.cnt==(right.r-right.l+1)){
            ans.cntr=right.cnt+left.cntr; 
        }
        else ans.cntr=right.cntr;
        ans.cntm=max(max(left.cntm,right.cntm),left.cntr+right.cntl);
        if(left.cnt==0){
            ans.cntl_2=(left.r-left.l+1)+right.cntl_2;
        }
        else ans.cntl_2=left.cntl_2;
        if(right.cnt==0){
            ans.cntr_2=(right.r-right.l+1)+left.cntr_2; 
        }
        else ans.cntr_2=right.cntr_2;
        ans.cntm_2=max(max(left.cntm_2,right.cntm_2),left.cntr_2+right.cntl_2);
        return ans;
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int op,x,y;
        cin>>op>>x>>y;
        if(x>y){
            swap(x,y);
        }
        if(op==0){
            update(1,x+1,y+1,0);
        }
        else if(op==1){
            update(1,x+1,y+1,1);
        }
        else if(op==2){
            update(1,x+1,y+1,2);
        }
        else if(op==3){
            cout<<query(1,x+1,y+1)<<endl;
        }
        else{
            cout<<query2(1,x+1,y+1).cntm<<endl;
        }
    }
    return 0;
}