线段树求调

#include<bits/stdc++.h>
#define ll long long
#define ls(u) u<<1
#define rs(u) u<<1|1
using namespace std;
const int N=1e5+10;
int n,m;
int a[N];
struct tree
{
    ll mark[N<<2],rev[N<<2],sum[2][N<<2],ans[2][N<<2],ml[2][N<<2],mr[2][N<<2],L[N<<2],R[N<<2];
    void pushup(ll u)
    {
        for(int i=0;i<=1;i++)
        {
            ans[i][u]=max(ans[i][ls(u)],ans[i][rs(u)]);
            sum[i][u]=sum[i][ls(u)]+sum[i][rs(u)];
            ml[i][u]=ml[i][ls(u)];
            mr[i][u]=mr[i][rs(u)];
            ans[i][u]=max(ans[i][u],mr[i][ls(u)]+ml[i][rs(u)]);
            if(sum[i][ls(u)]=R[ls(u)]-L[ls(u)]+1)ml[i][u]=max(ml[i][u],ml[i][ls(u)]+ml[i][rs(u)]);
            if(sum[i][rs(u)]=R[rs(u)]-L[rs(u)]+1)mr[i][u]=max(mr[i][u],mr[i][rs(u)]+mr[i][ls(u)]);
        }
    }
    void down(ll u)
    {
        int op=mark[u];
        if(op!=-1)
        {
            ans[op][u]=sum[op][u]=ml[op][u]=mr[op][u]=R[u]-L[u]+1;
            ans[!op][u]=sum[!op][u]=ml[!op][u]=mr[!op][u]=0;
            ans[op][ls(u)]=sum[op][ls(u)]=ml[op][ls(u)]=mr[op][ls(u)]=R[ls(u)]-L[ls(u)]+1;
            ans[!op][ls(u)]=sum[!op][ls(u)]=ml[!op][ls(u)]=mr[!op][ls(u)]=0;
            ans[op][rs(u)]=sum[op][rs(u)]=ml[op][rs(u)]=mr[op][rs(u)]=R[rs(u)]-L[rs(u)]+1;
            ans[!op][rs(u)]=sum[!op][rs(u)]=ml[!op][rs(u)]=mr[!op][rs(u)]=0;
            rev[ls(u)]=rev[rs(u)]=rev[u]=0;
            mark[ls(u)]=mark[rs(u)]=op;
            mark[u]=-1;
        }
        if(rev[u])
        {
            swap(sum[0][u],sum[1][u]);
            swap(ans[0][u],ans[1][u]);
            swap(ml[0][u],ml[1][u]);
            swap(mr[0][u],mr[1][u]);
            int u2=u;
            u=ls(u);
            swap(sum[0][u],sum[1][u]);
            swap(ans[0][u],ans[1][u]);
            swap(ml[0][u],ml[1][u]);
            swap(mr[0][u],mr[1][u]);
            u=rs(u2);
            swap(sum[0][u],sum[1][u]);
            swap(ans[0][u],ans[1][u]);
            swap(ml[0][u],ml[1][u]);
            swap(mr[0][u],mr[1][u]);
            u=u2;
            if(mark[ls(u)]!=-1)mark[ls(u)]^=1;
            else rev[ls(u)]^=1;
            if(mark[rs(u)]!=-1)mark[rs(u)]^=1;
            else rev[rs(u)]^=1;
            rev[u]=0;
        }
    }
    void build(ll u,ll l,ll r)
    {
        L[u]=l;
        R[u]=r;
        if(l==r)
        {
            sum[a[l]][u]=ml[a[l]][u]=mr[a[l]][u]=a[l];
            sum[!a[l]][u]=ml[!a[l]][u]=mr[!a[l]][u]=!a[l];
            return;
        }
        if(l<r)
        {
            int mid=(l+r)>>1;
            build(ls(u),l,mid);
            build(rs(u),mid+1,r);
            pushup(u);
        }
    }
    void up(ll u,ll l,ll r,ll L,ll R,ll k)
    {
        if(L>r||l>R)return;
        if(L<=l&&r<=R)
        {
            sum[k][u]=ml[k][u]=mr[k][u]=ans[k][u]=r-l+1;
            sum[!k][u]=ml[!k][u]=mr[!k][u]=ans[!k][u]=0;
            mark[u]=k;
        }
        else
        {
            if(l<r)
            {
                int mid=(l+r)>>1;
                down(u);
                if(L<=mid)up(ls(u),l,mid,L,R,k);
                if(R>mid)up(rs(u),mid+1,r,L,R,k);
                pushup(u);
            }
        }
    }
    void up2(ll u,ll l,ll r,ll L,ll R)
    {
        if(L>r||l>R)return;
        if(L<=l&&r<=R)
        {
            swap(sum[0][u],sum[1][u]);
            swap(ans[0][u],ans[1][u]);
            swap(ml[0][u],ml[1][u]);
            swap(mr[0][u],mr[1][u]);
            rev[u]=2;
        }
        else
        {
            if(l<r)
            {
                int mid=(l+r)>>1;
                down(u);
                if(L<=mid)up2(ls(u),l,mid,L,R);
                if(R>mid)up2(rs(u),mid+1,r,L,R);
                pushup(u);
            }
        }
    }
    ll query1(ll u,ll l,ll r,ll L,ll R)
    {
        if(L>r||l>R)return 0;
        if(L<=l&&r<=R)return sum[1][u];
        if(l<r)
        {
            ll mid=(l+r)>>1,ans=0;
            down(u);
            if(L<=mid)ans+=query1(ls(u),l,mid,L,R);
            if(R>=mid)ans+=query1(rs(u),mid+1,r,L,R);
            return ans;
        }
    }
    ll query2(ll u,ll l,ll r,ll L,ll R)
    {
        if(L>r||l>R)return 0;
        if(L<=l&&r<=R)return ans[1][u];
        if(l<r)
        {
            ll mid=(l+r)>>1,ans=0;
            down(u);
            if(L<=mid)ans=max(ans,query2(ls(u),l,mid,L,R));
            if(R>=mid)ans=max(ans,query2(rs(u),mid+1,r,L,R));
            return ans;
        }
    }
}tr;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    memset(tr.mark,-1,sizeof(tr.mark));
    for(int i=1;i<=n;i++)cin>>a[i];
    tr.build(1,1,n);
    while(m--)
    {
        ll k,l,r;
        cin>>k>>l>>r;
        if(k==0||k==1)tr.up(1,1,n,l,r,k);
        if(k==2)tr.up2(1,1,n,l,r);
        if(k==3)cout<<tr.query1(1,1,n,l,r)<<"\n";
        if(k==4)cout<<tr.query2(1,1,n,l,r)<<"\n";
    }
    return 0;
}

样例没过