线段树样例未过求dalao调

rt

#include<bits/stdc++.h>
#define ll long long
#define INF 1e9+7
#define lt u*2,l,mid
#define rt u*2+1,mid+1,r
#define ls u*2
#define rs u*2+1
using namespace std;
const int N=1e5+5;
int n,m,t[4*N],tl[4*N][2],tr[4*N][2],mt[4*N][2];
int a[N],lazy[4*N],lazyf[4*N];
void push_up(int u,int l,int r)
{
    t[u]=t[ls]+t[rs];
    int mid=(l+r)/2;
    if(t[ls]==mid-l+1)
    {
        tl[u][1]=mid-l+1+tl[rs][1];
    }
    else
    {
        tl[u][1]=tl[ls][1];
    }
    if(t[rs]==r-mid)
    {
        tr[u][1]=r-mid+tr[ls][1];
    }
    else
    {
        tr[u][1]=tr[rs][1];
    }
    mt[u][1]=max(tr[ls][1]+tl[rs][1],max(mt[ls][1],mt[rs][1]));
    if(t[ls]==0)
    {
        tl[u][0]=mid-l+1+tl[rs][0];
    }
    else
    {
        tl[u][0]=tl[ls][0];
    }
    if(t[rs]==0)
    {
        tr[u][0]=r-mid+tr[ls][0];
    }
    else
    {
        tr[u][0]=tr[rs][0];
    }
    mt[u][0]=max(tr[ls][0]+tl[rs][0],max(mt[ls][0],mt[rs][0]));
}
void push_down(int u,int l,int r)
{
    int mid=(l+r)/2;
    if(lazy[u]!=-1)
    {
        lazy[ls]=lazy[u];
        t[ls]=(mid-l+1)*lazy[u];
        tl[ls][lazy[u]]=mid-l+1;
        tr[ls][lazy[u]]=mid-l+1;
        mt[ls][lazy[u]]=mid-l+1;
        lazyf[ls]=0;
        lazy[rs]=lazy[u];
        t[rs]=(r-mid)*lazy[u];
        tl[rs][lazy[u]]=r-mid;
        tr[rs][lazy[u]]=r-mid;
        mt[rs][lazy[u]]=r-mid;
        lazyf[rs]=0;
        lazy[u]=-1;
    }
    if(lazyf[u])
    {
        t[ls]=mid-l+1-t[ls];
        swap(tl[ls][1],tl[ls][0]);
        swap(tr[ls][1],tr[ls][0]);
        swap(mt[ls][1],mt[ls][0]);
        if(lazy[ls]!=-1)
        {
            lazy[ls]^=1;
        }
        lazyf[ls]^=1;
        t[rs]=r-mid-t[rs];
        swap(tl[rs][1],tl[rs][0]);
        swap(tr[rs][1],tr[rs][0]);
        swap(mt[rs][1],mt[rs][0]);
        if(lazy[rs]!=-1)
        {
            lazy[rs]^=1;
        }
        lazyf[rs]^=1;
        lazyf[u]=0;
    }
}
void build(int u,int l,int r)
{
    lazy[u]=-1;
    if(l==r)
    {
        t[u]=a[l];
        tl[u][a[l]]=1;
        tr[u][a[l]]=1;
        mt[u][a[l]]=1;
        return ;
    }
    int mid=(l+r)/2;
    build(lt);
    build(rt);
    push_up(u,l,r);
}
void update(int u,int l,int r,int a,int b,int k)
{
    if(a<=l&&b>=r)
    {
        t[u]=(r-l+1)*k;
        tl[u][k]=r-l+1;
        tr[u][k]=r-l+1;
        mt[u][k]=r-l+1;
        lazy[u]=k;
        lazyf[u]=0;
        return ;
    }
    push_down(u,l,r);
    int mid=(l+r)/2;
    if(a<=mid)
    {
        update(lt,a,b,k);
    }
    if(b>mid)
    {
        update(rt,a,b,k);
    }
    push_up(u,l,r);
}
void updatef(int u,int l,int r,int a,int b)
{
    if(a<=l&&b>=r)
    {
        t[u]=r-l+1-t[u];
        swap(tl[u][1],tl[u][0]);
        swap(tr[u][1],tr[u][0]);
        swap(mt[u][1],mt[u][0]);
        lazyf[u]^=1;
        if(lazy[u]!=-1)
        {
            lazy[u]^=1;
        }
        return ;
    }
    push_down(u,l,r);
    int mid=(l+r)/2;
    if(a<=mid)
    {
        updatef(lt,a,b);
    }
    if(b>mid)
    {
        updatef(rt,a,b);
    }
    push_up(u,l,r);
}
int query1(int u,int l,int r,int a,int b)
{
    if(a<=l&&b>=r)
    {
        return t[u];
    }
    push_down(u,l,r);
    int mid=(l+r)/2;
    int ans=0;
    if(a<=mid)
    {
        ans+=query1(lt,a,b);
    }
    if(b>mid)
    {
        ans+=query1(rt,a,b);
    }
    return ans;
}
int query2(int u,int l,int r,int a,int b)
{
    if(a==l&&b==r)
    {
        return mt[u][1];
    }
    push_down(u,l,r);
    int mid=(l+r)/2;
    if(b<=mid)
    {
        return query2(lt,a,b);
    }
    else if(a>mid)
    {
        return query2(rt,a,b);
    }
    else
    {
        return max(max(query2(lt,a,mid),query2(rt,mid+1,b)),min(tl[rs][1],b-mid)+min(tr[ls][1],mid-a+1));
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        x++;
        y++;
        if(op==0)
        {
            update(1,1,n,x,y,0);
        }
        else if(op==1)
        {
            update(1,1,n,x,y,1);
        }
        else if(op==2)
        {
            updatef(1,1,n,x,y);
        }
        else if(op==3)
        {
            cout<<query1(1,1,n,x,y)<<endl;
        }
        else
        {
            cout<<query2(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}