求助 10 分线段树

_lfxxx_ @ 2022-05-03 15:30:08

by _lfxxx_ @ 2022-05-03 15:30:17

#include<bits/stdc++.h>
using namespace std;
namespace solution{
constexpr int N=1e5+5;
int n;
struct node{
    int sum,l1,l0,r1,r0,sum1,sum0,co,lazy;
}t[N<<2];
#define ls k<<1
#define rs k<<1|1
#define push_up(k)\
    t[k].sum=t[ls].sum+t[rs].sum,\
    t[k].l1=t[ls].l1+t[rs].l1*(t[ls].l1==mid-l+1),t[k].l0=t[ls].l0+t[rs].l0*(t[ls].l0==mid-l+1),\
    t[k].r1=t[rs].r1+t[ls].r1*(t[rs].r1==r-mid),t[k].r0=t[rs].r0+t[ls].r0*(t[rs].r0==r-mid),\
    t[k].sum0=max({t[ls].sum0,t[rs].sum0,t[ls].r0+t[rs].l0}),\
    t[k].sum1=max({t[ls].sum1,t[rs].sum1,t[ls].r1+t[rs].l1})
#define push_down(k)\
    if(t[k].co!=-1)\
        t[ls].sum=t[ls].l1=t[ls].r1=t[ls].sum1=t[k].co?l-mid+1:0,\
        t[ls].l0=t[ls].r0=t[ls].sum0=t[k].co?0:l-mid+1,\
        t[rs].sum=t[rs].l1=t[rs].r1=t[rs].sum1=t[k].co?r-mid:0,\
        t[rs].l0=t[rs].r0=t[rs].sum0=t[k].co?0:r-mid,\
        t[ls].co=t[rs].co=t[k].co,t[k].co=-1,t[k].lazy=0;\
    if(t[k].lazy)\
        t[ls].sum=mid-l+1-t[ls].sum,t[rs].sum=r-mid-t[rs].sum,\
        swap(t[ls].l0,t[ls].l1),swap(t[ls].r0,t[ls].r1),swap(t[ls].sum0,t[ls].sum1),\
        swap(t[rs].l0,t[rs].l1),swap(t[rs].r0,t[rs].r1),swap(t[rs].sum0,t[rs].sum1),\
        t[ls].lazy^=1,t[rs].lazy^=1,t[k].lazy=0
void build(const int&k=1,const int&l=1,const int&r=n){
    t[k].co=-1;
    if(l==r){
        cin>>t[k].sum,t[k].l1=t[k].r1=t[k].sum1=t[k].sum,t[k].l0=t[k].r0=t[k].sum0=!t[k].sum;
        return;
    }
    int mid=l+r>>1; 
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(k);
}
void update(const int&L,const int&R,const int&co,const int&k=1,const int&l=1,const int&r=n){
    if(L<=l&&r<=R){
        t[k].sum=t[k].l1=t[k].r1=t[k].sum1=co?r-l+1:0;
        t[k].l0=t[k].r0=t[k].sum0=co?0:r-l+1;
        t[k].co=co,t[k].lazy=0;
        return;
    }
    int mid=l+r>>1;
    push_down(k);
    if(L<=mid)
        update(L,R,co,ls,l,mid);
    if(R>mid)
        update(L,R,co,rs,mid+1,r);
    push_up(k);
}
void updatex(const int&L,const int&R,const int&k=1,const int&l=1,const int&r=n){
    if(L<=l&&r<=R){
        t[k].sum=r-l+1-t[k].sum;
        swap(t[k].l1,t[k].l0),swap(t[k].r1,t[k].r0),swap(t[k].sum1,t[k].sum0);
        t[k].lazy^=1;
        if(t[k].co!=-1)
            t[k].co^=1;
        return;
    }
    int mid=l+r>>1;
    push_down(k);
    if(L<=mid)
        updatex(L,R,ls,l,mid);
    if(R>mid)
        updatex(L,R,rs,mid+1,r);
    push_up(k);
}
int query_sum(const int&L,const int&R,const int&k=1,const int&l=1,const int&r=n){
    if(L<=l&&r<=R)
        return t[k].sum;
    int res=0,mid=l+r>>1;
    push_down(k);
    if(L<=mid)
        res+=query_sum(L,R,ls,l,mid);
    if(R>mid)
        res+=query_sum(L,R,rs,mid+1,r);
    return res;
}
node query(const int&L,const int&R,const int&k=1,const int&l=1,const int&r=n){
    if(L<=l&&r<=R)
        return t[k];
    int mid=l+r>>1;
    push_down(k);
    if(L>mid)
        return query(L,R,rs,mid+1,r);
    if(R<=mid)
        return query(L,R,ls,l,mid);
    node res,ln=query(L,R,ls,l,mid),rn=query(L,R,rs,mid+1,r);
    res.sum=ln.sum+rn.sum;
    res.l1=ln.l1+rn.l1*(ln.l1==mid-l+1),res.l0=ln.l0+rn.l0*(ln.l0==mid-l+1);
    res.r1=rn.r1+ln.r1*(rn.r1==r-mid),res.r0=rn.r0+ln.r0*(rn.r0==r-mid);
    res.sum0=max({ln.sum0,rn.sum0,ln.r0+rn.l0});
    res.sum1=max({ln.sum1,rn.sum1,ln.r1+rn.l1});
    return res;
}
void main(){
#ifdef IAKIOI
    freopen("5.in","r",stdin);
//  freopen("out.txt","w",stdout);
#endif
    int m,op,l,r;
    cin>>n>>m;
    build();
    while(m--){
        cin>>op>>l>>r,++l,++r;
        if(op<=1)
            update(l,r,op);
        else if(op==2)
            updatex(l,r);
        else if(op==3)
            cout<<query_sum(l,r)<<'\n';
        else
            cout<<query(l,r).sum1<<'\n';
    }
}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return solution::main(),0;
}

by Tx_Lcy @ 2022-05-03 15:36:45

@lfxxx 您的 pushdown 没有问题吗？

by _lfxxx_ @ 2022-05-03 16:10:31

@Lucky_Colorful_Youth 我看看，刚才我没注意看。

by _lfxxx_ @ 2022-05-03 16:35:58

已经 D 出 pushdown 一个锅了。（l-mid+1-->mid-l+1），但还是只有 10 分。

by _lfxxx_ @ 2022-05-03 16:58:10

A 了！push_down 中 lazy 的更新没有更新 co，谢谢大佬！