0pts求助

RT 过了样例和#11

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=100001;
struct node{
    int l,r,qcnt,hcnt,cnt,qcnt0,hcnt0,cnt0,sum;
    int g,f; 
}tr[N*4];
int a[N];
int n,m;
void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
    tr[u].cnt=max(max(tr[u<<1].cnt,tr[u<<1|1].cnt),tr[u<<1].hcnt+tr[u<<1|1].qcnt);
    tr[u].cnt0=max(max(tr[u<<1].cnt0,tr[u<<1|1].cnt0),tr[u<<1].hcnt0+tr[u<<1|1].qcnt0);
    tr[u].qcnt=(tr[u<<1].qcnt==(tr[u<<1].r-tr[u<<1].l+1))?tr[u<<1].qcnt+tr[u<<1|1].qcnt:tr[u<<1].qcnt;
    tr[u].hcnt=(tr[u<<1|1].hcnt==(tr[u<<1|1].r-tr[u<<1|1].l+1))?tr[u<<1].hcnt+tr[u<<1|1].hcnt:tr[u<<1|1].hcnt;
    tr[u].qcnt0=(tr[u<<1].qcnt0==(tr[u<<1].r-tr[u<<1].l+1))?tr[u<<1].qcnt0+tr[u<<1|1].qcnt0:tr[u<<1].qcnt0;
    tr[u].hcnt0=(tr[u<<1|1].hcnt0==(tr[u<<1|1].r-tr[u<<1|1].l+1))?tr[u<<1].hcnt0+tr[u<<1|1].hcnt0:tr[u<<1|1].hcnt0;
}
void pushdown_g(int u)
{
    if(tr[u].g!=-1)
    {
    //  cout<<-1;
        int z=u<<1,y=u<<1|1;
        if(tr[u].g==0)
        {
            tr[z].sum=tr[y].sum=0;
            tr[z].cnt=tr[y].cnt=tr[z].qcnt=tr[z].hcnt=tr[y].qcnt=tr[y].hcnt=0;
            tr[z].cnt0=tr[z].qcnt0=tr[z].hcnt0=(tr[z].r-tr[z].l+1);
            tr[y].cnt0=tr[y].qcnt0=tr[y].hcnt0=tr[y].r-tr[y].l+1;
            tr[z].g=tr[y].g=tr[u].g;
        }
        else
        {
            tr[z].sum=(tr[z].r-tr[z].l+1);
            tr[y].sum=(tr[y].r-tr[y].l+1);
            tr[z].cnt0=tr[y].cnt0=tr[z].qcnt0=tr[z].hcnt0=tr[y].qcnt0=tr[y].hcnt0=0;
            tr[z].cnt=tr[z].qcnt=tr[z].hcnt=(tr[z].r-tr[z].l+1);
            tr[y].cnt=tr[y].qcnt=tr[y].hcnt=tr[y].r-tr[y].l+1;
            tr[z].g=tr[y].g=tr[u].g;
        }
        tr[u].g=-1;tr[u].f=0;
    }
}
void pushdown_f(int u)
{
    if(tr[u].f)
    {
    //  cout<<1111111;
        int z=u<<1,y=u<<1|1;
        tr[z].sum=(tr[z].r-tr[z].l+1)-tr[z].sum;
        tr[y].sum=(tr[y].r-tr[y].l+1)-tr[y].sum;
        swap(tr[z].cnt,tr[z].cnt0);
        swap(tr[z].qcnt,tr[z].qcnt0);
        swap(tr[z].hcnt,tr[z].hcnt0);
        swap(tr[y].cnt,tr[y].cnt0);
        swap(tr[y].qcnt,tr[y].qcnt0);
        swap(tr[y].hcnt,tr[y].hcnt0);
        tr[z].f=tr[y].f=1;
        tr[u].f=0;
    }
}
void pushdown(int u)
{   
    pushdown_g(u);
    pushdown_f(u);
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        if(a[l])
            tr[u]={l,r,1,1,1,0,0,0,1,-1,0};
        else 
            tr[u]={l,r,0,0,0,1,1,1,0,-1,0};
        return;
    }
    tr[u]={l,r};
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
    //cout<<u<<' '<<tr[u].sum<<endl;
}
void modify_g(int u,int l,int r,int x)
{
    if(l<=tr[u].l&&r>=tr[u].r)
    {
        if(x==0)
        {
            tr[u].sum=0;
            tr[u].cnt=tr[u].qcnt=tr[u].hcnt=0;
            tr[u].cnt0=tr[u].qcnt0=tr[u].hcnt0=(tr[u].r-tr[u].l+1);
        }
        else
        {
            tr[u].sum=(tr[u].r-tr[u].l+1);
            tr[u].cnt0=tr[u].qcnt0=tr[u].hcnt0=0;
            tr[u].cnt=tr[u].qcnt=tr[u].hcnt=(tr[u].r-tr[u].l+1);
        }
        tr[u].g=x;
        //tr[u].f=0;
        return;
    }
    //cout<<tr[u].g<<endl;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    //cout<<tr[u].g<<' '<<u<<' '<<tr[5].sum<<endl;
    if(l<=mid) modify_g(u<<1,l,r,x);
    if(r>mid) modify_g(u<<1|1,l,r,x);
    pushup(u);
}
void modify_f(int u,int l,int r)
{
    if(l<=tr[u].l&&r>=tr[u].r)
    {
        int z=u;
        tr[z].sum=(tr[z].r-tr[z].l+1)-tr[z].sum;
        swap(tr[z].cnt,tr[z].cnt0);
        swap(tr[z].qcnt,tr[z].qcnt0);
        swap(tr[z].hcnt,tr[z].hcnt0);
        tr[z].f=1;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify_f(u<<1,l,r);
    if(r>mid) modify_f(u<<1|1,l,r);
    pushup(u);
}
int query_sum(int u,int l,int r)
{
    if(l<=tr[u].l&&r>=tr[u].r) 
    {
        //cout<<u<<' '<<tr[u].l<<' '<<tr[u].r<<' '<<tr[u].sum<<endl;
        return tr[u].sum;   
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1,sum=0;
    if(l<=mid) sum=query_sum(u<<1,l,r);
    if(r>mid) sum+=query_sum(u<<1|1,l,r);
//  cout<<u<<' '<<sum<<endl;
    return sum;
}
node query(int u,int l,int r)
{
    if(l<=tr[u].l&&r>=tr[u].r) return tr[u];
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    node a={0,0},b={0,0};
    if(l<=mid) a=query(u<<1,l,r);
    if(r>mid) b=query(u<<1|1,l,r);
    if(a.l!=0&&b.l!=0)
    {
        node c={a.l,b.r,(a.qcnt==(a.r-a.l+1)?a.qcnt+b.qcnt:a.qcnt),(b.hcnt==(b.r-b.l+1)?a.hcnt+b.hcnt:b.hcnt),max(max(a.cnt,b.cnt),a.hcnt+b.qcnt),0,0,0,0,0,0};
        return c;
    }
    if(b.l==0) return a;
    return b;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);   
    for(int i=1;i<=N*4;i++) tr[i].g=-1;
    //cout<<tr[5].sum<<endl;
    while(m--)
    {   //cout<<query_sum(1,1,6)<<endl<<endl;
        int opt,l,r;
        cin>>opt>>l>>r;
        //cout<<tr[5].sum<<endl<<endl;
        l++,r++;
        if(opt==0) modify_g(1,l,r,0);
        if(opt==1) modify_g(1,l,r,1);
        if(opt==2) modify_f(1,l,r);
        if(opt==3) cout<<query_sum(1,l,r)<<endl;
        if(opt==4) cout<<query(1,l,r).cnt<<endl;
    }
    return 0;
}