萌新求助

#include <cstring>
using namespace std;
struct TREE{
    int sum0,sum1;
    int lsum0,lsum1;
    int rsum0,rsum1;
    int maxsum0,maxsum1;
    int cov,rev;
}Tree[400005];
int n,m;
TREE uni;
int a[100005];
inline void input(int &x){
    x=0;char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
}
void write(int x){
    if (x<10){
        putchar((char)(x+'0'));return;
    }
    write(x/10);
    putchar((char)(x%10+'0'));
}
inline void output(int x,char c){
    write(x);putchar(c);
}
inline int max(int a,int b){
    return a>b?a:b;
}
inline void swap(int &x,int &y){
    int t=x;x=y;y=t;
}
inline void init(){
    uni.sum0=uni.sum1=uni.lsum0=uni.lsum1=uni.rsum0=uni.rsum1=uni.maxsum0=uni.maxsum1=0;
    uni.cov=uni.rev=-1;
}
inline void pushup(int l,int r,int id){
    int mid=(l+r)>>1;
    Tree[id].sum0=Tree[id<<1].sum0+Tree[id<<1|1].sum0;
    Tree[id].sum1=Tree[id<<1].sum1+Tree[id<<1|1].sum1;
    if (Tree[id<<1].lsum0){
        Tree[id].lsum1=0;
        Tree[id].lsum0=Tree[id<<1].lsum0;
        if (Tree[id<<1].sum0==mid-l+1) Tree[id].lsum0+=Tree[id<<1|1].lsum0;
    }
    else{
        Tree[id].lsum0=0;
        Tree[id].lsum1=Tree[id<<1].lsum1;
        if (Tree[id<<1].sum1==mid-l+1) Tree[id].lsum1+=Tree[id<<1|1].lsum1;
    }
    if (Tree[id<<1|1].rsum0){
        Tree[id].rsum1=0;
        Tree[id].rsum0=Tree[id<<1|1].rsum0;
        if (Tree[id<<1|1].sum0==r-mid) Tree[id].rsum0+=Tree[id<<1].rsum0;
    }
    else{
        Tree[id].rsum0=0;
        Tree[id].rsum1=Tree[id<<1|1].rsum1;
        if (Tree[id<<1|1].sum1==r-mid) Tree[id].rsum1+=Tree[id<<1].rsum1;
    }
    Tree[id].maxsum0=max(max(Tree[id<<1].maxsum0,Tree[id<<1|1].maxsum0),Tree[id<<1].rsum0+Tree[id<<1|1].lsum0);
    Tree[id].maxsum1=max(max(Tree[id<<1].maxsum1,Tree[id<<1|1].maxsum1),Tree[id<<1].rsum1+Tree[id<<1|1].lsum1);
}
inline void pushdown(int l,int r,int id){
    int mid=(l+r)>>1;
    if (Tree[id].cov!=-1){
        Tree[id<<1].cov=Tree[id<<1|1].cov=Tree[id].cov;
        Tree[id<<1].rev=Tree[id<<1|1].rev=-1;
        if (!Tree[id].cov){
            Tree[id<<1].sum0=Tree[id<<1].lsum0=Tree[id<<1].rsum0=Tree[id<<1].maxsum0=mid-l+1;
            Tree[id<<1].sum1=Tree[id<<1].lsum1=Tree[id<<1].rsum1=Tree[id<<1].maxsum1=0;
            Tree[id<<1|1].sum0=Tree[id<<1|1].lsum0=Tree[id<<1|1].rsum0=Tree[id<<1|1].maxsum0=r-mid;
            Tree[id<<1|1].sum1=Tree[id<<1|1].lsum1=Tree[id<<1|1].rsum1=Tree[id<<1|1].maxsum1=0;
        }
        else{
            Tree[id<<1].sum0=Tree[id<<1].lsum0=Tree[id<<1].rsum0=Tree[id<<1].maxsum0=0;
            Tree[id<<1].sum1=Tree[id<<1].lsum1=Tree[id<<1].rsum1=Tree[id<<1].maxsum1=mid-l+1;
            Tree[id<<1|1].sum0=Tree[id<<1|1].lsum0=Tree[id<<1|1].rsum0=Tree[id<<1|1].maxsum0=0;
            Tree[id<<1|1].sum1=Tree[id<<1|1].lsum1=Tree[id<<1|1].rsum1=Tree[id<<1|1].maxsum1=r-mid;
        }
        Tree[id].cov=Tree[id].rev=-1;
    }
    if (Tree[id].rev!=-1){
        Tree[id<<1].rev*=-1;
        Tree[id<<1|1].rev*=-1;
        if (Tree[id<<1].cov!=-1) Tree[id<<1].cov^=1;
        if (Tree[id<<1|1].cov!=-1) Tree[id<<1|1].cov^=1;
        swap(Tree[id<<1].sum0,Tree[id<<1].sum1);
        swap(Tree[id<<1|1].sum0,Tree[id<<1|1].sum1);
        swap(Tree[id<<1].lsum0,Tree[id<<1].lsum1);
        swap(Tree[id<<1|1].lsum0,Tree[id<<1|1].lsum1);
        swap(Tree[id<<1].rsum0,Tree[id<<1].rsum1);
        swap(Tree[id<<1|1].rsum0,Tree[id<<1|1].rsum1);
        swap(Tree[id<<1].maxsum0,Tree[id<<1].maxsum1);
        swap(Tree[id<<1|1].maxsum0,Tree[id<<1|1].maxsum1);
        Tree[id].rev=-1;
    }
}
void build(int l,int r,int id){
    Tree[id]=uni;
    if (l==r){
        if (!a[l]){
            Tree[id].sum0=Tree[id].lsum0=Tree[id].rsum0=Tree[id].maxsum0=1;
        }
        else{
            Tree[id].sum1=Tree[id].lsum1=Tree[id].rsum1=Tree[id].maxsum1=1;
        }
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);
    pushup(l,r,id);
} 
void update1(int x,int y,int k,int l,int r,int id){
    if (x<=l&&r<=y){
        Tree[id].cov=k;Tree[id].rev=-1;
        if (!k) {
            Tree[id].sum0=Tree[id].lsum0=Tree[id].rsum0=Tree[id].maxsum0=r-l+1;
            Tree[id].sum1=Tree[id].lsum1=Tree[id].rsum1=Tree[id].maxsum1=0;
        }
        else{
            Tree[id].sum0=Tree[id].lsum0=Tree[id].rsum0=Tree[id].maxsum0=0;
            Tree[id].sum1=Tree[id].lsum1=Tree[id].rsum1=Tree[id].maxsum1=r-l+1;
        }
        return;
    }
    pushdown(l,r,id);
    int mid=(l+r)>>1;
    if (x<=mid) update1(x,y,k,l,mid,id<<1);
    if (y>mid) update1(x,y,k,mid+1,r,id<<1|1);
    pushup(l,r,id);
}
void update2(int x,int y,int l,int r,int id){
    if (x<=l&&r<=y){
        Tree[id].rev*=-1;
        swap(Tree[id].sum0,Tree[id].sum1);
        swap(Tree[id].lsum0,Tree[id].lsum1);
        swap(Tree[id].rsum0,Tree[id].rsum1);
        swap(Tree[id].maxsum0,Tree[id].maxsum1);
        return;
    }
    pushdown(l,r,id);
    int mid=(l+r)>>1;
    if (x<=mid) update2(x,y,l,mid,id<<1);
    if (y>mid) update2(x,y,mid+1,r,id<<1|1);
    pushup(l,r,id);
}
int query1(int x,int y,int l,int r,int id){
    if (x<=l&&r<=y){
        return Tree[id].sum1;
    }
    pushdown(l,r,id);
    int mid=(l+r)>>1,res=0;
    if (x<=mid) res+=query1(x,y,l,mid,id<<1);
    if (y>mid) res+=query1(x,y,mid+1,r,id<<1|1);
    return res;
}
TREE query2(int x,int y,int l,int r,int id){
    if (x<=l&&r<=y){
        return Tree[id];
    }
    pushdown(l,r,id);
    int mid=(l+r)>>1;
    TREE res=uni,res1=uni,res2=uni;
    if (x<=mid) res1=query2(x,y,l,mid,id<<1);
    if (y>mid) res2=query2(x,y,mid+1,r,id<<1|1);
    res.sum1=res1.sum1+res2.sum1;
    res.lsum1=res1.lsum1;
    if (res1.sum1==mid-l+1) res.lsum1+=res2.lsum1;
    res.rsum1=res2.rsum1;
    if (res2.sum1==r-mid) res.rsum1+=res1.rsum1;
    res.maxsum1=max(max(res1.maxsum1,res2.maxsum1),res1.rsum1+res2.lsum1);
    return res;
}
int main(){
    init();
    input(n);input(m);
    for (int i=1;i<=n;i++){
        input(a[i]);
    }
    build(1,n,1);
    while(m--){
        int opt,l,r;
        input(opt);input(l);input(r);
        ++l;++r;
        switch(opt){
            case 0:
                update1(l,r,0,1,n,1);break;
            case 1:
                update1(l,r,1,1,n,1);break;
            case 2:
                update2(l,r,1,n,1);break;
            case 3:
                output(query1(l,r,1,n,1),'\n');break;
            case 4:
                output(query2(l,r,1,n,1).maxsum1,'\n');break;
        }
    }
    return 0;
}