萌新求调线段树

RT，只有 10 分，只有 #2 和 #11 过了

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
//#define LL_inf 1145141919810
#define ull unsigned long long
#define ll long long
using namespace std;
//#define int long long
const int Maxn=1e5+10;
int Ar[Maxn];
int n,m;
//bool debug;
//#define cout if(debug) cout
struct SegmentTree{
    struct Segtree{
        int sum;
        int ans0,ans1;
        int lmax0,rmax0;
        int lmax1,rmax1;
        int len;
        int tag1,tag2;
    }t[Maxn<<2];
    #define ls node<<1
    #define rs node<<1|1
    void pushup(int node)
    {
        t[node].sum=t[ls].sum+t[rs].sum;
        t[node].len=t[ls].len+t[rs].len;
        t[node].ans0=max(max(t[ls].ans0,t[rs].ans0),t[ls].rmax0+t[rs].lmax0);
        t[node].ans1=max(max(t[ls].ans1,t[rs].ans1),t[ls].rmax1+t[rs].lmax1);

        t[node].lmax0=t[ls].lmax0;
        if(t[ls].lmax0==t[ls].len)
        {
            t[node].lmax0=t[ls].len+t[rs].lmax0;
        }

        t[node].lmax1=t[ls].lmax1;
        if(t[ls].lmax1==t[ls].len)
        {
            t[node].lmax1=t[ls].len+t[rs].lmax1;
        }

        t[node].rmax0=t[rs].rmax0;
        if(t[rs].rmax0==t[rs].len)
        {
            t[node].rmax0=t[rs].len+t[ls].rmax0;
        }

        t[node].rmax1=t[rs].rmax1;
        if(t[rs].rmax1==t[rs].len)
        {
            t[node].rmax1=t[rs].len+t[ls].rmax1;
        }
    }
    void pushdown(int node)
    {
        if(t[node].tag1!=-1)
        {
            t[ls].tag1=t[rs].tag1=t[node].tag1;
            t[ls].tag2=t[rs].tag2=0;
            if(t[node].tag1==0)
            {
                t[ls].ans0=t[ls].lmax0=t[ls].rmax0=t[ls].len;
                t[rs].ans0=t[rs].lmax0=t[rs].rmax0=t[rs].len;
                t[ls].ans1=t[rs].ans1=0;
                t[ls].lmax1=t[rs].lmax1=t[ls].rmax1=t[rs].rmax1=0;
                t[ls].sum=t[rs].sum=0;
            }else{
                t[ls].sum=t[ls].ans1=t[ls].lmax1=t[ls].rmax1=t[ls].len;
                t[rs].sum=t[rs].ans1=t[rs].lmax1=t[rs].rmax1=t[rs].len;
                t[ls].ans0=t[rs].ans0=0;
                t[ls].lmax0=t[rs].lmax0=t[ls].rmax0=t[rs].rmax0=0;
            }

            t[node].tag1=-1;
        }

        if(t[node].tag2)
        {
            t[ls].sum=t[ls].len-t[ls].sum;
            t[rs].sum=t[rs].len-t[rs].sum;
            swap(t[ls].ans0,t[ls].ans1);
            swap(t[rs].ans0,t[rs].ans1);
            swap(t[ls].lmax0,t[ls].lmax1);
            swap(t[rs].lmax0,t[rs].lmax1);
            swap(t[ls].rmax0,t[ls].rmax1);
            swap(t[rs].rmax0,t[rs].rmax1);

            if(t[ls].tag1==-1)
            {
                t[ls].tag2^=1;
            }else{
                t[ls].tag1^=1;
            }

            if(t[rs].tag1==-1)
            {
                t[rs].tag2^=1;
            }else{
                t[rs].tag1^=1;
            }

            t[node].tag2=0;
        }
    }

    void build(int node,int l,int r)
    {
        t[node].tag1=-1;
        t[node].tag2=0;
        if(l==r)
        {
            t[node].sum=Ar[l];
            if(Ar[l]==0)
            {
                t[node].ans0=t[node].lmax0=t[node].rmax0=1;
                t[node].ans1=t[node].lmax1=t[node].rmax1=0;
            }else{
                t[node].ans0=t[node].lmax0=t[node].rmax0=0;
                t[node].ans1=t[node].lmax1=t[node].rmax1=1;
            }
            t[node].len=1; 
            return ;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r); 
        pushup(node);
    }
    void assign(int node,int l,int r,int ql,int qr,int val)
    {
        if(ql<=l && r<=qr)
        {
            t[node].tag1=val;
            if(val==0)
            {
                t[node].ans0=t[node].lmax0=t[node].rmax0=t[node].len;
                t[node].ans1=0;
                t[node].sum=0;
                t[node].lmax1=t[node].rmax1=0;
            }else{
                t[node].sum=t[node].ans1=t[node].lmax1=t[node].rmax1=t[node].len;
                t[node].ans0=0;
                t[node].lmax0=t[node].rmax0=0;
            }
            return ;
        }
        pushdown(node);
        int mid=(l+r)>>1;
        if(ql<=mid)
        {
            assign(ls,l,mid,ql,qr,val);
        }
        if(qr>mid)
        {
            assign(rs,mid+1,r,ql,qr,val);
        }
        pushup(node);
    }

    void rever(int node,int l,int r,int ql,int qr)
    {
        if(ql<=l && r<=qr)
        {
            t[node].sum=t[node].len-t[node].sum;
            swap(t[node].ans0,t[node].ans1);
            swap(t[node].lmax0,t[node].lmax1);
            swap(t[node].rmax0,t[node].rmax1);
            t[node].tag2^=1;
            return ;
        }

        int mid=(l+r)>>1;
        pushdown(node);
        if(ql<=mid)
        {
            rever(ls,l,mid,ql,qr);
        }
        if(qr>mid)
        {
            rever(rs,mid+1,r,ql,qr);
        }

        pushup(node);
    }

    int querysum(int node,int l,int r,int ql,int qr)
    {
//      if(debug) cout<<node<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl; 
        if(ql<=l && r<=qr)
        {
//          if(debug) cout<<"sum="<<t[node].sum<<endl;
            return t[node].sum;
        }
        int mid=(l+r)>>1;
        pushdown(node);
        int ans=0;
        if(ql<=mid)
        {
            ans+=querysum(ls,l,mid,ql,qr);
        }
        if(qr>mid)
        {
            ans+=querysum(rs,mid+1,r,ql,qr);
        }
        return ans;
    }
    Segtree query(int node,int l,int r,int ql,int qr)
    {
//      cout<<node<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl;
        if(ql<=l && r<=qr)
        {
            return t[node];
        }
        int mid=(l+r)>>1;
//      cout<<"mid="<<mid<<endl;
        pushdown(node);
        if(qr<=mid)
        {
            return query(ls,l,mid,ql,qr);
        }else if(ql>mid){
            return query(rs,mid+1,r,ql,qr);
        }else{
            Segtree a=query(ls,l,mid,ql,qr);
            Segtree b=query(rs,mid+1,r,ql,qr);
            Segtree c; 
            c.sum=a.sum+b.sum;
            c.len=a.len+b.len;
            c.ans0=max(max(a.ans0,b.ans0),a.rmax0+b.lmax0);
            c.ans1=max(max(a.ans1,b.ans1),a.rmax1+b.lmax1);

            c.lmax0=a.lmax0;
            if(a.lmax0==a.len)
            {
                c.lmax0=a.len+b.lmax0;
            }

            c.lmax1=a.lmax1;
            if(a.lmax1==a.len)
            {
                c.lmax1=a.len+b.lmax1;
            }

            c.rmax0=b.rmax0;
            if(b.rmax0==b.len)
            {
                c.rmax0=b.len+a.rmax0;
            }

            c.rmax1=b.rmax1;
            if(b.rmax1==b.len)
            {
                c.rmax1=b.len+a.rmax1;
            }

            return c;
        }
    }   

    int Query(int l,int r)
    {
        return query(1,1,n,l,r).ans1;
    }
}seg;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&Ar[i]);
    }
    seg.build(1,1,n);
    while(m--)
    {
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        l++,r++;
        if(opt==0)
        {
            seg.assign(1,1,n,l,r,0);
        }else if(opt==1){
            seg.assign(1,1,n,l,r,1);
        }else if(opt==2){
            seg.rever(1,1,n,l,r);
        }else if(opt==3){
            printf("%d\n",seg.querysum(1,1,n,l,r));
        }else{
            printf("%d\n",seg.Query(l,r));
        }
//      debug=0;
//      for(int i=1;i<=n;i++)
//      {
//          cout<<seg.querysum(1,1,n,i,i)<<" ";
//      }
//      putchar('\n');
//      debug=1;
    }
    return 0;
}