线段树10pts求调

toolong114514 @ 2023-11-17 20:50:48

#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e6+10;
struct node{
    int l,r;
    int sum1,l1,r1,lgt1,sum0,l0,r0,lgt0;
    int laz1,laz2;
}tree[4*N];
int a[N];
int n,m;
void push_up(int pos){
    //对1 
    tree[pos].sum1=tree[pos*2].sum1+tree[pos*2+1].sum1;
    tree[pos].lgt1=max(max(tree[pos*2].lgt1,tree[pos*2+1].lgt1),tree[pos*2].r1+tree[pos*2+1].l1);
    tree[pos].l1=tree[pos*2].l1;
    if(tree[pos*2].sum1==tree[pos*2].r-tree[pos*2].l+1) tree[pos].l1=tree[pos*2].sum1+tree[pos*2+1].l1;
    tree[pos].r1=tree[pos*2+1].r1;
    if(tree[pos*2+1].sum1==tree[pos*2+1].r-tree[pos*2+1].l+1) tree[pos].r1=tree[pos*2+1].sum1+tree[pos*2].r1;
    //对0 
    tree[pos].sum0=tree[pos*2].sum0+tree[pos*2+1].sum0;
    tree[pos].lgt0=max(max(tree[pos*2].lgt0,tree[pos*2+1].lgt0),tree[pos*2].r0+tree[pos*2+1].l0);
    tree[pos].l0=tree[pos*2].l0;
    if(tree[pos*2].sum0==tree[pos*2].r-tree[pos*2].l+1) tree[pos].l0=tree[pos*2].sum0+tree[pos*2+1].l0;
    tree[pos].r0=tree[pos*2+1].r0;
    if(tree[pos*2+1].sum0==tree[pos*2+1].r-tree[pos*2+1].l+1) tree[pos].r0=tree[pos*2+1].sum0+tree[pos*2].r0;
}
void push_down(int pos){
    if(tree[pos].laz1==1){
        tree[pos*2].sum1=1;
        tree[pos*2].l1=1;
        tree[pos*2].r1=1;
        tree[pos*2].lgt1=1;
        tree[pos*2+1].sum1=1;
        tree[pos*2+1].l1=1;
        tree[pos*2+1].r1=1;
        tree[pos*2+1].lgt1=1;

        tree[pos*2].sum0=0;
        tree[pos*2].l0=0;
        tree[pos*2].r0=0;
        tree[pos*2].lgt0=0;
        tree[pos*2+1].sum0=0;
        tree[pos*2+1].l0=0;
        tree[pos*2+1].r0=0;
        tree[pos*2+1].lgt0=0;

        tree[pos*2].laz1=tree[pos*2+1].laz1=1;
    }
    if(tree[pos].laz1==0){
        tree[pos*2].sum1=0;
        tree[pos*2].l1=0;
        tree[pos*2].r1=0;
        tree[pos*2].lgt1=0;
        tree[pos*2+1].sum1=0;
        tree[pos*2+1].l1=0;
        tree[pos*2+1].r1=0;
        tree[pos*2+1].lgt1=0;

        tree[pos*2].sum0=1;
        tree[pos*2].l0=1;
        tree[pos*2].r0=1;
        tree[pos*2].lgt0=1;
        tree[pos*2+1].sum0=1;
        tree[pos*2+1].l0=1;
        tree[pos*2+1].r0=1;
        tree[pos*2+1].lgt0=1;

        tree[pos*2].laz1=0;
        tree[pos*2+1].laz1=0;
    }
    tree[pos].laz1=-1;
    if(tree[pos].laz2==-1){
        swap(tree[pos*2].l0,tree[pos*2].l1);
        swap(tree[pos*2].r0,tree[pos*2].r1);
        swap(tree[pos*2].lgt0,tree[pos*2].lgt1);
        swap(tree[pos*2].sum0,tree[pos*2].sum1);

        swap(tree[pos*2+1].l0,tree[pos*2+1].l1);
        swap(tree[pos*2+1].r0,tree[pos*2+1].r1);
        swap(tree[pos*2+1].lgt0,tree[pos*2+1].lgt1);
        swap(tree[pos*2+1].sum0,tree[pos*2+1].sum1);

        tree[pos*2].laz2*=-1;
        tree[pos*2+1].laz2*=-1;
    }
    tree[pos].laz2=1;
}
void build(int pos,int lft,int rgt){
    tree[pos].l=lft;
    tree[pos].r=rgt;
    tree[pos].laz1=-1;
    tree[pos].laz2=1; 
    if(lft==rgt){
        if(a[lft]==1){
            tree[pos].sum1=1;
            tree[pos].l1=1;
            tree[pos].r1=1;
            tree[pos].lgt1=1;
        }else{
            tree[pos].sum0=1;
            tree[pos].l0=1;
            tree[pos].r0=1;
            tree[pos].lgt0=1;
        }
        return;
    }
    int mid=(lft+rgt)/2;
    build(pos*2,lft,mid);
    build(pos*2+1,mid+1,rgt);
    push_up(pos);
}
void fill1(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt){
        tree[pos].sum1=tree[pos].r-tree[pos].l+1;
        tree[pos].l1=tree[pos].r-tree[pos].l+1;
        tree[pos].r1=tree[pos].r-tree[pos].l+1;
        tree[pos].lgt1=tree[pos].r-tree[pos].l+1;

        tree[pos].sum0=0;
        tree[pos].l0=0;
        tree[pos].r0=0;
        tree[pos].lgt0=0;

        tree[pos].laz1=1;
        tree[pos].laz2=1;
        return;
    }
    if(tree[pos].r<lft||rgt<tree[pos].l) return;
    push_down(pos);
    fill1(pos*2,lft,rgt);
    fill1(pos*2+1,lft,rgt);
    push_up(pos);
}
void fill0(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt){
        tree[pos].sum0=tree[pos].r-tree[pos].l+1;
        tree[pos].l0=tree[pos].r-tree[pos].l+1;
        tree[pos].r0=tree[pos].r-tree[pos].l+1;
        tree[pos].lgt0=tree[pos].r-tree[pos].l+1;

        tree[pos].sum1=0;
        tree[pos].l1=0;
        tree[pos].r1=0;
        tree[pos].lgt1=0;

        tree[pos].laz1=0;
        tree[pos].laz2=1;
        return;
    }
    if(tree[pos].r<lft||rgt<tree[pos].l) return;
    push_down(pos);
    fill0(pos*2,lft,rgt);
    fill0(pos*2+1,lft,rgt);
    push_up(pos);
}
void rev(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt){
        swap(tree[pos].l0,tree[pos].l1);
        swap(tree[pos].r0,tree[pos].r1);
        swap(tree[pos].lgt0,tree[pos].lgt1);
        swap(tree[pos].sum0,tree[pos].sum1);
        tree[pos].laz2*=-1;
        return;
    }
    if(tree[pos].r<lft||rgt<tree[pos].l) return;
    push_down(pos);
    rev(pos*2,lft,rgt);
    rev(pos*2+1,lft,rgt);
    push_up(pos);
}
int ask1(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].sum1;
    if(tree[pos].r<lft||rgt<tree[pos].l) return 0;
    push_down(pos);
    return ask1(pos*2,lft,rgt)+ask1(pos*2+1,lft,rgt);
}
node ask2(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos];
    push_down(pos);
    if(tree[pos*2].r<lft) return ask2(pos*2+1,lft,rgt);
    if(rgt<tree[pos*2+1].l) return ask2(pos*2,lft,rgt);
    int mid=(tree[pos].l+tree[pos].r)/2;
    node t1=ask2(pos*2,lft,rgt);
    node t2=ask2(pos*2+1,lft,rgt);
    node ans;
    ans.lgt1=max(t1.r1+t2.l1,max(t1.lgt1,t2.lgt1));
    ans.l1=t1.l1;
    ans.r1=t2.r1;
    if(t1.sum1==mid-tree[pos].l+1) ans.l1=t1.sum1+t2.l1;
    if(t2.sum1==tree[pos].r-mid) ans.r1=t2.sum1+t1.r1;
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        int op,ll,rr;
        cin>>op>>ll>>rr;
        ll++;
        rr++;
        if(op==0) fill0(1,ll,rr);
        if(op==1) fill1(1,ll,rr);
        if(op==2) rev(1,ll,rr);
        if(op==3) cout<<ask1(1,ll,rr)<<endl;
        if(op==4) cout<<ask2(1,ll,rr).lgt1<<endl;
    }
    return 0;
}

by toolong114514 @ 2023-11-17 20:57:23

现在的代码，修正了一些大的bug。

#include<algorithm>
#include<iostream>
using namespace std;
const int N=1e6+10;
struct node{
    int l,r;
    int sum1,l1,r1,lgt1,sum0,l0,r0,lgt0;
    int laz1,laz2;
}tree[4*N];
int a[N];
int n,m;
void push_up(int pos){
    //对1 
    tree[pos].sum1=tree[pos*2].sum1+tree[pos*2+1].sum1;
    tree[pos].lgt1=max(max(tree[pos*2].lgt1,tree[pos*2+1].lgt1),tree[pos*2].r1+tree[pos*2+1].l1);
    tree[pos].l1=tree[pos*2].l1;
    if(tree[pos*2].sum1==tree[pos*2].r-tree[pos*2].l+1) tree[pos].l1=tree[pos*2].sum1+tree[pos*2+1].l1;
    tree[pos].r1=tree[pos*2+1].r1;
    if(tree[pos*2+1].sum1==tree[pos*2+1].r-tree[pos*2+1].l+1) tree[pos].r1=tree[pos*2+1].sum1+tree[pos*2].r1;
    //对0 
    tree[pos].sum0=tree[pos*2].sum0+tree[pos*2+1].sum0;
    tree[pos].lgt0=max(max(tree[pos*2].lgt0,tree[pos*2+1].lgt0),tree[pos*2].r0+tree[pos*2+1].l0);
    tree[pos].l0=tree[pos*2].l0;
    if(tree[pos*2].sum0==tree[pos*2].r-tree[pos*2].l+1) tree[pos].l0=tree[pos*2].sum0+tree[pos*2+1].l0;
    tree[pos].r0=tree[pos*2+1].r0;
    if(tree[pos*2+1].sum0==tree[pos*2+1].r-tree[pos*2+1].l+1) tree[pos].r0=tree[pos*2+1].sum0+tree[pos*2].r0;
}
void push_down(int pos){
    if(tree[pos].laz1==1){
        tree[pos*2].sum1=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2].l1=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2].r1=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2].lgt1=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2+1].sum1=tree[pos*2+1].r-tree[pos*2+1].l+1;
        tree[pos*2+1].l1=tree[pos*2+1].r-tree[pos*2+1].l+1;
        tree[pos*2+1].r1=tree[pos*2+1].r-tree[pos*2+1].l+1;
        tree[pos*2+1].lgt1=tree[pos*2+1].r-tree[pos*2+1].l+1;

        tree[pos*2].sum0=0;
        tree[pos*2].l0=0;
        tree[pos*2].r0=0;
        tree[pos*2].lgt0=0;
        tree[pos*2+1].sum0=0;
        tree[pos*2+1].l0=0;
        tree[pos*2+1].r0=0;
        tree[pos*2+1].lgt0=0;

        tree[pos*2].laz1=1;
        tree[pos*2+1].laz1=1;
    }
    if(tree[pos].laz1==0){
        tree[pos*2].sum1=0;
        tree[pos*2].l1=0;
        tree[pos*2].r1=0;
        tree[pos*2].lgt1=0;
        tree[pos*2+1].sum1=0;
        tree[pos*2+1].l1=0;
        tree[pos*2+1].r1=0;
        tree[pos*2+1].lgt1=0;

        tree[pos*2].sum0=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2].l0=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2].r0=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2].lgt0=tree[pos*2].r-tree[pos*2].l+1;
        tree[pos*2+1].sum0=tree[pos*2+1].r-tree[pos*2+1].l+1;
        tree[pos*2+1].l0=tree[pos*2+1].r-tree[pos*2+1].l+1;
        tree[pos*2+1].r0=tree[pos*2+1].r-tree[pos*2+1].l+1;
        tree[pos*2+1].lgt0=tree[pos*2+1].r-tree[pos*2+1].l+1;

        tree[pos*2].laz1=0;
        tree[pos*2+1].laz1=0;
    }
    tree[pos].laz1=-1;
    if(tree[pos].laz2==-1){
        swap(tree[pos*2].l0,tree[pos*2].l1);
        swap(tree[pos*2].r0,tree[pos*2].r1);
        swap(tree[pos*2].lgt0,tree[pos*2].lgt1);
        swap(tree[pos*2].sum0,tree[pos*2].sum1);

        swap(tree[pos*2+1].l0,tree[pos*2+1].l1);
        swap(tree[pos*2+1].r0,tree[pos*2+1].r1);
        swap(tree[pos*2+1].lgt0,tree[pos*2+1].lgt1);
        swap(tree[pos*2+1].sum0,tree[pos*2+1].sum1);

        tree[pos*2].laz2*=-1;
        tree[pos*2+1].laz2*=-1;
    }
    tree[pos].laz2=1;
}
void build(int pos,int lft,int rgt){
    tree[pos].l=lft;
    tree[pos].r=rgt;
    tree[pos].laz1=-1;
    tree[pos].laz2=1; 
    if(lft==rgt){
        if(a[lft]==1){
            tree[pos].sum1=1;
            tree[pos].l1=1;
            tree[pos].r1=1;
            tree[pos].lgt1=1;
        }else{
            tree[pos].sum0=1;
            tree[pos].l0=1;
            tree[pos].r0=1;
            tree[pos].lgt0=1;
        }
        return;
    }
    int mid=(lft+rgt)/2;
    build(pos*2,lft,mid);
    build(pos*2+1,mid+1,rgt);
    push_up(pos);
}
void fill1(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt){
        tree[pos].sum1=tree[pos].r-tree[pos].l+1;
        tree[pos].l1=tree[pos].r-tree[pos].l+1;
        tree[pos].r1=tree[pos].r-tree[pos].l+1;
        tree[pos].lgt1=tree[pos].r-tree[pos].l+1;

        tree[pos].sum0=0;
        tree[pos].l0=0;
        tree[pos].r0=0;
        tree[pos].lgt0=0;

        tree[pos].laz1=1;
        tree[pos].laz2=1;
        return;
    }
    if(tree[pos].r<lft||rgt<tree[pos].l) return;
    push_down(pos);
    fill1(pos*2,lft,rgt);
    fill1(pos*2+1,lft,rgt);
    push_up(pos);
}
void fill0(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt){
        tree[pos].sum0=tree[pos].r-tree[pos].l+1;
        tree[pos].l0=tree[pos].r-tree[pos].l+1;
        tree[pos].r0=tree[pos].r-tree[pos].l+1;
        tree[pos].lgt0=tree[pos].r-tree[pos].l+1;

        tree[pos].sum1=0;
        tree[pos].l1=0;
        tree[pos].r1=0;
        tree[pos].lgt1=0;

        tree[pos].laz1=0;
        tree[pos].laz2=1;
        return;
    }
    if(tree[pos].r<lft||rgt<tree[pos].l) return;
    push_down(pos);
    fill0(pos*2,lft,rgt);
    fill0(pos*2+1,lft,rgt);
    push_up(pos);
}
void rev(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt){
        swap(tree[pos].l0,tree[pos].l1);
        swap(tree[pos].r0,tree[pos].r1);
        swap(tree[pos].lgt0,tree[pos].lgt1);
        swap(tree[pos].sum0,tree[pos].sum1);
        tree[pos].laz2*=-1;
        return;
    }
    if(tree[pos].r<lft||rgt<tree[pos].l) return;
    push_down(pos);
    rev(pos*2,lft,rgt);
    rev(pos*2+1,lft,rgt);
    push_up(pos);
}
int ask1(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].sum1;
    if(tree[pos].r<lft||rgt<tree[pos].l) return 0;
    push_down(pos);
    return ask1(pos*2,lft,rgt)+ask1(pos*2+1,lft,rgt);
}
node ask2(int pos,int lft,int rgt){
    if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos];
    push_down(pos);
    if(tree[pos*2].r<lft) return ask2(pos*2+1,lft,rgt);
    if(rgt<tree[pos*2+1].l) return ask2(pos*2,lft,rgt);
    int mid=(tree[pos].l+tree[pos].r)/2;
    node t1=ask2(pos*2,lft,rgt);
    node t2=ask2(pos*2+1,lft,rgt);
    node ans;
    ans.lgt1=max(t1.r1+t2.l1,max(t1.lgt1,t2.lgt1));
    ans.l1=t1.l1;
    ans.r1=t2.r1;
    if(t1.sum1==mid-tree[pos].l+1) ans.l1=t1.sum1+t2.l1;
    if(t2.sum1==tree[pos].r-mid) ans.r1=t2.sum1+t1.r1;
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        int op,ll,rr;
        cin>>op>>ll>>rr;
        ll++;
        rr++;
        if(op==0) fill0(1,ll,rr);
        if(op==1) fill1(1,ll,rr);
        if(op==2) rev(1,ll,rr);
        if(op==3) cout<<ask1(1,ll,rr)<<endl;
        if(op==4) cout<<ask2(1,ll,rr).lgt1<<endl;
    }
    return 0;
}

by toolong114514 @ 2023-11-21 16:39:40

wssb，线段树下传覆盖懒标记时忘记清空集结点的反转懒标记了。此贴结。

by yugen @ 2024-04-18 13:47:50

@toolong114514 太感谢了，我也在这里出错了，改了代码从10pts变100pts了。

by immerse_23 @ 2024-06-07 17:04:05

草。最不爱数据结构的一集。