0pts只过HACK求调

_H17_ @ 2024-10-04 20:40:54

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+1;
int n,q,a[N],rt,tot;
struct SegmentTreeNode{
    int l,r,ls,rs,pre0,suf0,val0,pre1,suf1,val1,sum,tag1,tag2;
    SegmentTreeNode(int l=0,int r=0,int ls=0,int rs=0,int pre0=0,int suf0=0,int val0=0,int pre1=0,int suf1=0,int val1=0,int sum=0,int tag1=-1,int tag2=0)
        :l(l),r(r),ls(ls),rs(rs),pre0(pre0),suf0(suf0),val0(val0),pre1(pre1),suf1(suf1),val1(val1),sum(sum),tag1(tag1),tag2(tag2){}
}f[N<<1];
void pushup(int cur){
    f[cur]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].rs].r,f[cur].ls,f[cur].rs,0,0,0,0,0,0,f[f[cur].ls].sum+f[f[cur].rs].sum,-1,0);
    if(f[f[cur].ls].pre0==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre0=f[f[cur].ls].pre0+f[f[cur].rs].pre0;
    else
        f[cur].pre0=f[f[cur].ls].pre0;
    if(f[f[cur].ls].pre1==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre1=f[f[cur].ls].pre1+f[f[cur].rs].pre1;
    else
        f[cur].pre1=f[f[cur].ls].pre1;
    if(f[f[cur].rs].suf0==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf0=f[f[cur].ls].suf0+f[f[cur].rs].suf0;
    else
        f[cur].suf0=f[f[cur].rs].suf0;
    if(f[f[cur].rs].suf1==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf1=f[f[cur].ls].suf1+f[f[cur].rs].suf1;
    else
        f[cur].suf1=f[f[cur].rs].suf1;
    f[cur].val0=max({f[cur].pre0,f[cur].suf0,f[f[cur].ls].suf0+f[f[cur].rs].pre0}),
    f[cur].val1=max({f[cur].pre1,f[cur].suf1,f[f[cur].ls].suf1+f[f[cur].rs].pre1});
    return;
}
SegmentTreeNode pushup(SegmentTreeNode a,SegmentTreeNode b){
    SegmentTreeNode ret=SegmentTreeNode(a.l,b.r,0,0,0,0,0,0,0,0,a.sum+b.sum,-1,0);
    if(a.pre0==a.r-a.l+1)
        ret.pre0=a.pre0+b.pre0;
    else
        ret.pre0=a.pre0;
    if(a.pre1==a.r-a.l+1)
        ret.pre1=a.pre1+b.pre1;
    else
        ret.pre1=a.pre1;
    if(b.suf0==b.r-b.l+1)
        ret.suf0=a.suf0+b.suf0;
    else
        ret.suf0=b.suf0;
    if(b.suf1==b.r-b.l+1)
        ret.suf1=a.suf1+b.suf1;
    else
        ret.suf1=b.suf1;
    ret.val0=max({ret.pre0,ret.suf0,a.suf0+b.pre0}),
    ret.val1=max({ret.pre1,ret.suf1,a.suf1+b.pre1});
    return ret;
}
void build(int l,int r,int&cur){
    cur=(++tot);
    if(l==r){
        f[cur]=SegmentTreeNode(l,r,0,0,(!a[l]),(!a[l]),(!a[l]),a[l],a[l],a[l],a[l],-1,0);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);
    return pushup(cur);
}
void pushdown(int cur){
    int tag=f[cur].tag1;
    if(tag!=-1){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag,0),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag,0);
        f[cur].tag1=-1;
    }
    tag=f[cur].tag2;
    if(tag){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,f[f[cur].ls].pre1,f[f[cur].ls].suf1,f[f[cur].ls].val1,f[f[cur].ls].pre0,f[f[cur].ls].suf0,f[f[cur].ls].val0,(f[f[cur].ls].r-f[f[cur].ls].l+1)-f[f[cur].ls].sum,-1,1),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,f[f[cur].rs].pre1,f[f[cur].rs].suf1,f[f[cur].rs].val1,f[f[cur].rs].pre0,f[f[cur].rs].suf0,f[f[cur].rs].val0,(f[f[cur].rs].r-f[f[cur].rs].l+1)-f[f[cur].rs].sum,-1,1);
        f[cur].tag2=0;
    }
    return;
}
void modify(int l,int r,int val,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val,0);
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        modify(l,r,val,f[cur].ls);
    else
        modify(l,r,val,f[cur].rs);
    return pushup(cur);
}
void reverse(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,f[cur].pre1,f[cur].suf1,f[cur].val1,f[cur].pre0,f[cur].suf0,f[cur].val0,(f[cur].r-f[cur].l+1)-f[cur].sum,f[cur].tag1,f[cur].tag2);
        if(f[cur].tag1!=-1)
            f[cur].tag1^=1;
        else
            f[cur].tag2^=1;
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        reverse(l,r,f[cur].ls);
    if(mid<r)
        reverse(l,r,f[cur].rs);
    return pushup(cur);
}
SegmentTreeNode query(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r)
        return f[cur];
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid&&mid<r)
        return pushup(query(l,r,f[cur].ls),query(l,r,f[cur].rs));
    if(l<=mid)
        return query(l,r,f[cur].ls);
    if(mid<r)
        return query(l,r,f[cur].rs);
    return SegmentTreeNode();
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,rt);
    for(int op,l,r;q;--q){
        cin>>op>>l>>r;
        l++,r++;
        if(op==0&&op==1)
            modify(l,r,op,1);
        else if(op==2)
            reverse(l,r,1);
        else if(op==3)
            cout<<query(l,r,1).sum<<'\n';
        else
            cout<<query(l,r,1).val1<<'\n';
    }
    return 0;
}

by _H17_ @ 2024-10-04 21:20:16

新代码

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+1;
int n,q,a[N],rt,tot;
struct SegmentTreeNode{
    int l,r,ls,rs,pre0,suf0,val0,pre1,suf1,val1,sum,tag1,tag2;
    SegmentTreeNode(int l=0,int r=0,int ls=0,int rs=0,int pre0=0,int suf0=0,int val0=0,int pre1=0,int suf1=0,int val1=0,int sum=0,int tag1=-1,int tag2=0)
        :l(l),r(r),ls(ls),rs(rs),pre0(pre0),suf0(suf0),val0(val0),pre1(pre1),suf1(suf1),val1(val1),sum(sum),tag1(tag1),tag2(tag2){}
}f[N<<1];
void pushup(int cur){
    f[cur]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].rs].r,f[cur].ls,f[cur].rs,0,0,0,0,0,0,f[f[cur].ls].sum+f[f[cur].rs].sum,-1,0);
    if(f[f[cur].ls].pre0==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre0=f[f[cur].ls].pre0+f[f[cur].rs].pre0;
    else
        f[cur].pre0=f[f[cur].ls].pre0;
    if(f[f[cur].ls].pre1==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre1=f[f[cur].ls].pre1+f[f[cur].rs].pre1;
    else
        f[cur].pre1=f[f[cur].ls].pre1;
    if(f[f[cur].rs].suf0==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf0=f[f[cur].ls].suf0+f[f[cur].rs].suf0;
    else
        f[cur].suf0=f[f[cur].rs].suf0;
    if(f[f[cur].rs].suf1==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf1=f[f[cur].ls].suf1+f[f[cur].rs].suf1;
    else
        f[cur].suf1=f[f[cur].rs].suf1;
    f[cur].val0=max({f[cur].pre0,f[cur].suf0,f[f[cur].ls].suf0+f[f[cur].rs].pre0,f[f[cur].ls].val0,f[f[cur].rs].val0}),
    f[cur].val1=max({f[cur].pre1,f[cur].suf1,f[f[cur].ls].suf1+f[f[cur].rs].pre1,f[f[cur].ls].val1,f[f[cur].rs].val1});
    return;
}
SegmentTreeNode pushup(SegmentTreeNode a,SegmentTreeNode b){
    SegmentTreeNode ret=SegmentTreeNode(a.l,b.r,0,0,0,0,0,0,0,0,a.sum+b.sum,-1,0);
    if(a.pre0==a.r-a.l+1)
        ret.pre0=a.pre0+b.pre0;
    else
        ret.pre0=a.pre0;
    if(a.pre1==a.r-a.l+1)
        ret.pre1=a.pre1+b.pre1;
    else
        ret.pre1=a.pre1;
    if(b.suf0==b.r-b.l+1)
        ret.suf0=a.suf0+b.suf0;
    else
        ret.suf0=b.suf0;
    if(b.suf1==b.r-b.l+1)
        ret.suf1=a.suf1+b.suf1;
    else
        ret.suf1=b.suf1;
    ret.val0=max({ret.pre0,ret.suf0,a.suf0+b.pre0,a.val0,b.val0}),
    ret.val1=max({ret.pre1,ret.suf1,a.suf1+b.pre1,a.val1,b.val1});
    return ret;
}
void build(int l,int r,int&cur){
    cur=(++tot);
    if(l==r){
        f[cur]=SegmentTreeNode(l,r,0,0,(!a[l]),(!a[l]),(!a[l]),a[l],a[l],a[l],a[l],-1,0);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);
    return pushup(cur);
}
void pushdown(int cur){
    int tag=f[cur].tag1;
    if(tag!=-1){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag,0),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag,0);
        f[cur].tag1=-1;
    }
    tag=f[cur].tag2;
    if(tag){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,f[f[cur].ls].pre1,f[f[cur].ls].suf1,f[f[cur].ls].val1,f[f[cur].ls].pre0,f[f[cur].ls].suf0,f[f[cur].ls].val0,(f[f[cur].ls].r-f[f[cur].ls].l+1)-f[f[cur].ls].sum,-1,1),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,f[f[cur].rs].pre1,f[f[cur].rs].suf1,f[f[cur].rs].val1,f[f[cur].rs].pre0,f[f[cur].rs].suf0,f[f[cur].rs].val0,(f[f[cur].rs].r-f[f[cur].rs].l+1)-f[f[cur].rs].sum,-1,1);
        f[cur].tag2=0;
    }
    return;
}
void modify(int l,int r,int val,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val,0);
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        modify(l,r,val,f[cur].ls);
    else
        modify(l,r,val,f[cur].rs);
    return pushup(cur);
}
void reverse(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,f[cur].pre1,f[cur].suf1,f[cur].val1,f[cur].pre0,f[cur].suf0,f[cur].val0,(f[cur].r-f[cur].l+1)-f[cur].sum,f[cur].tag1,f[cur].tag2);
        if(f[cur].tag1!=-1)
            f[cur].tag1^=1;
        else
            f[cur].tag2^=1;
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        reverse(l,r,f[cur].ls);
    if(mid<r)
        reverse(l,r,f[cur].rs);
    return pushup(cur);
}
SegmentTreeNode query(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r)
        return f[cur];
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid&&mid<r)
        return pushup(query(l,r,f[cur].ls),query(l,r,f[cur].rs));
    if(l<=mid)
        return query(l,r,f[cur].ls);
    if(mid<r)
        return query(l,r,f[cur].rs);
    return SegmentTreeNode();
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,rt);
    for(int op,l,r;q;--q){
        cin>>op>>l>>r;
        l++,r++;
        if(op==0&&op==1)
            modify(l,r,op,1);
        else if(op==2)
            reverse(l,r,1);
        else if(op==3)
            cout<<query(l,r,1).sum<<'\n';
        else
            cout<<query(l,r,1).val1<<'\n';
    }
    return 0;
}

by _H17_ @ 2024-10-04 21:47:32

最新的：

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+1;
int n,q,a[N],rt,tot;
struct SegmentTreeNode{
    int l,r,ls,rs,pre0,suf0,val0,pre1,suf1,val1,sum,tag1,tag2;
    SegmentTreeNode(int l=0,int r=0,int ls=0,int rs=0,int pre0=0,int suf0=0,int val0=0,int pre1=0,int suf1=0,int val1=0,int sum=0,int tag1=-1,int tag2=0)
        :l(l),r(r),ls(ls),rs(rs),pre0(pre0),suf0(suf0),val0(val0),pre1(pre1),suf1(suf1),val1(val1),sum(sum),tag1(tag1),tag2(tag2){}
}f[N<<1];
void pushup(int cur){
    f[cur]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].rs].r,f[cur].ls,f[cur].rs,0,0,0,0,0,0,f[f[cur].ls].sum+f[f[cur].rs].sum,-1,0);
    if(f[f[cur].ls].pre0==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre0=f[f[cur].ls].pre0+f[f[cur].rs].pre0;
    else
        f[cur].pre0=f[f[cur].ls].pre0;
    if(f[f[cur].ls].pre1==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre1=f[f[cur].ls].pre1+f[f[cur].rs].pre1;
    else
        f[cur].pre1=f[f[cur].ls].pre1;
    if(f[f[cur].rs].suf0==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf0=f[f[cur].ls].suf0+f[f[cur].rs].suf0;
    else
        f[cur].suf0=f[f[cur].rs].suf0;
    if(f[f[cur].rs].suf1==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf1=f[f[cur].ls].suf1+f[f[cur].rs].suf1;
    else
        f[cur].suf1=f[f[cur].rs].suf1;
    f[cur].val0=max({f[cur].pre0,f[cur].suf0,f[f[cur].ls].suf0+f[f[cur].rs].pre0,f[f[cur].ls].val0,f[f[cur].rs].val0}),
    f[cur].val1=max({f[cur].pre1,f[cur].suf1,f[f[cur].ls].suf1+f[f[cur].rs].pre1,f[f[cur].ls].val1,f[f[cur].rs].val1});
    return;
}
SegmentTreeNode pushup(SegmentTreeNode a,SegmentTreeNode b){
    SegmentTreeNode ret=SegmentTreeNode(a.l,b.r,0,0,0,0,0,0,0,0,a.sum+b.sum,-1,0);
    if(a.pre0==a.r-a.l+1)
        ret.pre0=a.pre0+b.pre0;
    else
        ret.pre0=a.pre0;
    if(a.pre1==a.r-a.l+1)
        ret.pre1=a.pre1+b.pre1;
    else
        ret.pre1=a.pre1;
    if(b.suf0==b.r-b.l+1)
        ret.suf0=a.suf0+b.suf0;
    else
        ret.suf0=b.suf0;
    if(b.suf1==b.r-b.l+1)
        ret.suf1=a.suf1+b.suf1;
    else
        ret.suf1=b.suf1;
    ret.val0=max({ret.pre0,ret.suf0,a.suf0+b.pre0,a.val0,b.val0}),
    ret.val1=max({ret.pre1,ret.suf1,a.suf1+b.pre1,a.val1,b.val1});
    return ret;
}
void build(int l,int r,int&cur){
    cur=(++tot);
    if(l==r){
        f[cur]=SegmentTreeNode(l,r,0,0,(!a[l]),(!a[l]),(!a[l]),a[l],a[l],a[l],a[l],-1,0);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);
    return pushup(cur);
}
void pushdown(int cur){
    int tag=f[cur].tag1;
    if(tag!=-1){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag,0),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag,0);
        f[cur].tag1=-1;
    }
    tag=f[cur].tag2;
    if(tag){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,f[f[cur].ls].pre1,f[f[cur].ls].suf1,f[f[cur].ls].val1,f[f[cur].ls].pre0,f[f[cur].ls].suf0,f[f[cur].ls].val0,(f[f[cur].ls].r-f[f[cur].ls].l+1)-f[f[cur].ls].sum,-1,f[f[cur].ls].tag2^1),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,f[f[cur].rs].pre1,f[f[cur].rs].suf1,f[f[cur].rs].val1,f[f[cur].rs].pre0,f[f[cur].rs].suf0,f[f[cur].rs].val0,(f[f[cur].rs].r-f[f[cur].rs].l+1)-f[f[cur].rs].sum,-1,f[f[cur].rs].tag2^1);
        f[cur].tag2=0;
    }
    return;
}
void modify(int l,int r,int val,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val,0);
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        modify(l,r,val,f[cur].ls);
    else
        modify(l,r,val,f[cur].rs);
    return pushup(cur);
}
void reverse(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,f[cur].pre1,f[cur].suf1,f[cur].val1,f[cur].pre0,f[cur].suf0,f[cur].val0,(f[cur].r-f[cur].l+1)-f[cur].sum,f[cur].tag1,f[cur].tag2);
        if(f[cur].tag1!=-1)
            f[cur].tag1^=1,f[cur].tag2=0;
        else
            f[cur].tag2^=1;
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        reverse(l,r,f[cur].ls);
    if(mid<r)
        reverse(l,r,f[cur].rs);
    return pushup(cur);
}
SegmentTreeNode query(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r)
        return f[cur];
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid&&mid<r)
        return pushup(query(l,r,f[cur].ls),query(l,r,f[cur].rs));
    if(l<=mid)
        return query(l,r,f[cur].ls);
    if(mid<r)
        return query(l,r,f[cur].rs);
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,rt);
    for(int op,l,r;q;--q){
        cin>>op>>l>>r;
        l++,r++;
        if(op==0||op==1)
            modify(l,r,op,1);
        else if(op==2)
            reverse(l,r,1);
        else if(op==3)
            cout<<query(l,r,1).sum<<'\n';
        else
            cout<<query(l,r,1).val1<<'\n';
    }
    return 0;
}

by _H17_ @ 2024-10-04 22:48:00

最最新的：

#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e5+1;
int n,q,a[N],rt,tot;
struct SegmentTreeNode{
    int l,r,ls,rs,pre0,suf0,val0,pre1,suf1,val1,sum,tag1,tag2;
    SegmentTreeNode(int l=0,int r=0,int ls=0,int rs=0,int pre0=0,int suf0=0,int val0=0,int pre1=0,int suf1=0,int val1=0,int sum=0,int tag1=-1,int tag2=0)
        :l(l),r(r),ls(ls),rs(rs),pre0(pre0),suf0(suf0),val0(val0),pre1(pre1),suf1(suf1),val1(val1),sum(sum),tag1(tag1),tag2(tag2){}
}f[N<<1];
void pushup(int cur){
    f[cur]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].rs].r,f[cur].ls,f[cur].rs,0,0,0,0,0,0,f[f[cur].ls].sum+f[f[cur].rs].sum,-1,0);
    if(f[f[cur].ls].pre0==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre0=f[f[cur].ls].pre0+f[f[cur].rs].pre0;
    else
        f[cur].pre0=f[f[cur].ls].pre0;
    if(f[f[cur].ls].pre1==f[f[cur].ls].r-f[f[cur].ls].l+1)
        f[cur].pre1=f[f[cur].ls].pre1+f[f[cur].rs].pre1;
    else
        f[cur].pre1=f[f[cur].ls].pre1;
    if(f[f[cur].rs].suf0==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf0=f[f[cur].ls].suf0+f[f[cur].rs].suf0;
    else
        f[cur].suf0=f[f[cur].rs].suf0;
    if(f[f[cur].rs].suf1==f[f[cur].rs].r-f[f[cur].rs].l+1)
        f[cur].suf1=f[f[cur].ls].suf1+f[f[cur].rs].suf1;
    else
        f[cur].suf1=f[f[cur].rs].suf1;
    f[cur].val0=max({f[cur].pre0,f[cur].suf0,f[f[cur].ls].suf0+f[f[cur].rs].pre0,f[f[cur].ls].val0,f[f[cur].rs].val0}),
    f[cur].val1=max({f[cur].pre1,f[cur].suf1,f[f[cur].ls].suf1+f[f[cur].rs].pre1,f[f[cur].ls].val1,f[f[cur].rs].val1});
    return;
}
SegmentTreeNode pushup(SegmentTreeNode a,SegmentTreeNode b){
    SegmentTreeNode ret=SegmentTreeNode(a.l,b.r,0,0,0,0,0,0,0,0,a.sum+b.sum,-1,0);
    if(a.pre0==a.r-a.l+1)
        ret.pre0=a.pre0+b.pre0;
    else
        ret.pre0=a.pre0;
    if(a.pre1==a.r-a.l+1)
        ret.pre1=a.pre1+b.pre1;
    else
        ret.pre1=a.pre1;
    if(b.suf0==b.r-b.l+1)
        ret.suf0=a.suf0+b.suf0;
    else
        ret.suf0=b.suf0;
    if(b.suf1==b.r-b.l+1)
        ret.suf1=a.suf1+b.suf1;
    else
        ret.suf1=b.suf1;
    ret.val0=max({ret.pre0,ret.suf0,a.suf0+b.pre0,a.val0,b.val0}),
    ret.val1=max({ret.pre1,ret.suf1,a.suf1+b.pre1,a.val1,b.val1});
    return ret;
}
void build(int l,int r,int&cur){
    cur=(++tot);
    if(l==r){
        f[cur]=SegmentTreeNode(l,r,0,0,(!a[l]),(!a[l]),(!a[l]),a[l],a[l],a[l],a[l],-1,0);
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,f[cur].ls),build(mid+1,r,f[cur].rs);
    return pushup(cur);
}
void pushdown(int cur){
    int tag=f[cur].tag1;
    if(tag!=-1){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),(!tag)*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag*(f[f[cur].ls].r-f[f[cur].ls].l+1),tag,0),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),(!tag)*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag*(f[f[cur].rs].r-f[f[cur].rs].l+1),tag,0);
        f[cur].tag1=-1;
        return;
    }
    tag=f[cur].tag2;
    if(tag){
        f[f[cur].ls]=SegmentTreeNode(f[f[cur].ls].l,f[f[cur].ls].r,f[f[cur].ls].ls,f[f[cur].ls].rs,f[f[cur].ls].pre1,f[f[cur].ls].suf1,f[f[cur].ls].val1,f[f[cur].ls].pre0,f[f[cur].ls].suf0,f[f[cur].ls].val0,(f[f[cur].ls].r-f[f[cur].ls].l+1)-f[f[cur].ls].sum,f[f[cur].ls].tag1,f[f[cur].ls].tag2),
        f[f[cur].rs]=SegmentTreeNode(f[f[cur].rs].l,f[f[cur].rs].r,f[f[cur].rs].ls,f[f[cur].rs].rs,f[f[cur].rs].pre1,f[f[cur].rs].suf1,f[f[cur].rs].val1,f[f[cur].rs].pre0,f[f[cur].rs].suf0,f[f[cur].rs].val0,(f[f[cur].rs].r-f[f[cur].rs].l+1)-f[f[cur].rs].sum,f[f[cur].rs].tag1,f[f[cur].rs].tag2);
        if(f[f[cur].ls].tag1!=-1)
            f[f[cur].ls].tag1^=1;
        else
            f[f[cur].ls].tag2^=1;
        if(f[f[cur].rs].tag1!=-1)
            f[f[cur].rs].tag1^=1;
        else
            f[f[cur].rs].tag2^=1;
        f[cur].tag2=0;
    }
    return;
}
void modify(int l,int r,int val,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),(!val)*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val*(f[cur].r-f[cur].l+1),val,0);
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        modify(l,r,val,f[cur].ls);
    else
        modify(l,r,val,f[cur].rs);
    return pushup(cur);
}
void reverse(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r){
        f[cur]=SegmentTreeNode(f[cur].l,f[cur].r,f[cur].ls,f[cur].rs,f[cur].pre1,f[cur].suf1,f[cur].val1,f[cur].pre0,f[cur].suf0,f[cur].val0,(f[cur].r-f[cur].l+1)-f[cur].sum,f[cur].tag1,f[cur].tag2);
        if(f[cur].tag1!=-1)
            f[cur].tag1^=1;
        else
            f[cur].tag2^=1;
        return;
    }
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(l<=mid)
        reverse(l,r,f[cur].ls);
    if(mid<r)
        reverse(l,r,f[cur].rs);
    return pushup(cur);
}
SegmentTreeNode query(int l,int r,int cur){
    if(l<=f[cur].l&&f[cur].r<=r)
        return f[cur];
    pushdown(cur);
    int mid=(f[cur].l+f[cur].r)>>1;
    if(mid<l)
        return query(l,r,f[cur].rs);
    if(r<=mid)
        return query(l,r,f[cur].ls);
    return pushup(query(l,r,f[cur].ls),query(l,r,f[cur].rs));
}
void debug(){
    for(int i=1;i<=tot;i++)
        cerr<<"# "<<i<<": "<<f[i].l<<' '<<f[i].r<<' '<<f[i].ls<<' '<<f[i].rs<<' '<<f[i].pre0<<' '<<f[i].suf0<<' '<<f[i].val0<<' '<<f[i].pre1<<' '<<f[i].suf1<<' '<<f[i].val1<<' '<<f[i].sum<<' '<<f[i].tag1<<' '<<f[i].tag2<<'\n';
    return;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,n,rt);
//    debug();
    for(int op,l,r;q;--q){
        cin>>op>>l>>r;
        l++,r++;
        if(op==0||op==1)
            modify(l,r,op,1);
        else if(op==2)
            reverse(l,r,1);
        else if(op==3)
            cout<<query(l,r,1).sum<<'\n';
        else
            cout<<query(l,r,1).val1<<'\n';
//        debug();
    }
    return 0;
}