线段树求条有简要注释 玄关

iranai @ 2024-11-28 10:30:42

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100000+10];
struct NODE{
    int l,r;
    int add1;//全变成1 
    int add0;//全变成0 
    int add;//反转次数 
    int sum;
    int maxl;//1
    int maxr;
    int maxz;
    int ma;
    int max_l;//0
    int max_r;
    int max_z;
    int ma_;
};
NODE tr[400000+10];
void pushup(NODE &root,NODE &zuo,NODE &you){
    root.sum=zuo.sum+you.sum;
    root.maxl=(zuo.maxl==zuo.r-zuo.l+1?zuo.maxl+you.maxl:zuo.maxl); 
    root.maxr=(you.maxr==you.r-you.l+1?you.maxr+zuo.maxr:you.maxr);
    root.maxz=zuo.maxr+you.maxl;
    root.ma=max(root.maxl,max(root.maxz,root.maxr));

    root.max_l=(zuo.max_l==zuo.r-zuo.l+1?zuo.max_l+you.max_l:zuo.max_l);
    root.max_r=(you.max_r==you.r-you.l+1?you.max_r+zuo.max_r:you.max_r);
    root.max_z=zuo.max_r+you.max_l;
    root.ma_=max(root.max_l,max(root.max_z,root.max_r));
}
void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
    if(l==r){
        if(a[l]==1) tr[u]=(NODE){l,r,0,0,0,1,1,1,1,1,0,0,0,0};
        else tr[u]=(NODE){l,r,0,0,0,0,0,0,0,0,1,1,1,1};
        return ;
    }
    tr[u]=(NODE){l,r,0,0,0};
    int mid=(l+r)/2;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void pushdown(int u){
    if(tr[u].add1==1){
        tr[u<<1].add1=1;
        tr[u<<1].add+=tr[u].add;
        tr[u<<1|1].add1=1;
        tr[u<<1|1].add+=tr[u].add;
        if(tr[u].add%2==0){//全是1 
            tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1;
            tr[u<<1].maxl=tr[u<<1].sum;
            tr[u<<1].maxr=tr[u<<1].sum;
            tr[u<<1].maxz=tr[u<<1].sum;
            tr[u<<1].ma=tr[u<<1].sum;
            tr[u<<1].max_l=0;
            tr[u<<1].max_r=0;
            tr[u<<1].max_z=0;
            tr[u<<1].ma_=0;

            tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1;
            tr[u<<1|1].maxl=tr[u<<1|1].sum;
            tr[u<<1|1].maxr=tr[u<<1|1].sum;
            tr[u<<1|1].maxz=tr[u<<1|1].sum;
            tr[u<<1|1].ma=tr[u<<1|1].sum;
            tr[u<<1|1].max_l=0;
            tr[u<<1|1].max_r=0;
            tr[u<<1|1].max_z=0;
            tr[u<<1|1].ma_=0;
        }else{// 全是0 
            tr[u<<1].sum=0;
            tr[u<<1].maxl=0;
            tr[u<<1].maxr=0;
            tr[u<<1].maxz=0;
            tr[u<<1].ma=0;
            tr[u<<1].max_l=tr[u<<1].r-tr[u<<1].l+1;
            tr[u<<1].max_r=tr[u<<1].max_l;
            tr[u<<1].max_z=tr[u<<1].max_l;
            tr[u<<1].ma_=tr[u<<1].max_l;

            tr[u<<1|1].sum=0;
            tr[u<<1|1].maxl=0;
            tr[u<<1|1].maxr=0;
            tr[u<<1|1].maxz=0;
            tr[u<<1|1].ma=0;
            tr[u<<1|1].max_l=tr[u<<1|1].r-tr[u<<1|1].l+1;
            tr[u<<1|1].max_r=tr[u<<1|1].max_l;
            tr[u<<1|1].max_z=tr[u<<1|1].max_l;
            tr[u<<1|1].ma_=tr[u<<1|1].max_l;
        }
    }else if(tr[u].add0==1){
        tr[u<<1].add0=1;
        tr[u<<1].add+=tr[u].add;
        tr[u<<1|1].add0=1;
        tr[u<<1|1].add+=tr[u].add;
        if(tr[u].add%2==1){//全是1 
            tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1;
            tr[u<<1].maxl=tr[u<<1].sum;
            tr[u<<1].maxr=tr[u<<1].sum;
            tr[u<<1].maxz=tr[u<<1].sum;
            tr[u<<1].ma=tr[u<<1].sum;
            tr[u<<1].max_l=0;
            tr[u<<1].max_r=0;
            tr[u<<1].max_z=0;
            tr[u<<1].ma_=0;

            tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1;
            tr[u<<1|1].maxl=tr[u<<1|1].sum;
            tr[u<<1|1].maxr=tr[u<<1|1].sum;
            tr[u<<1|1].maxz=tr[u<<1|1].sum;
            tr[u<<1|1].ma=tr[u<<1|1].sum;
            tr[u<<1|1].max_l=0;
            tr[u<<1|1].max_r=0;
            tr[u<<1|1].max_z=0;
            tr[u<<1|1].ma_=0;
        }else{//全是0 
            tr[u<<1].sum=0;
            tr[u<<1].maxl=0;
            tr[u<<1].maxr=0;
            tr[u<<1].maxz=0;
            tr[u<<1].ma=0;
            tr[u<<1].max_l=tr[u<<1].r-tr[u<<1].l+1;
            tr[u<<1].max_r=tr[u<<1].max_l;
            tr[u<<1].max_z=tr[u<<1].max_l;
            tr[u<<1].ma_=tr[u<<1].max_l;

            tr[u<<1|1].sum=0;
            tr[u<<1|1].maxl=0;
            tr[u<<1|1].maxr=0;
            tr[u<<1|1].maxz=0;
            tr[u<<1|1].ma=0;
            tr[u<<1|1].max_l=tr[u<<1|1].r-tr[u<<1|1].l+1;
            tr[u<<1|1].max_r=tr[u<<1|1].max_l;
            tr[u<<1|1].max_z=tr[u<<1|1].max_l;
            tr[u<<1|1].ma_=tr[u<<1|1].max_l;
        }
    }else{
        tr[u<<1].add+=tr[u].add;
        tr[u<<1|1].add+=tr[u].add;
        if(tr[u].add%2==1){//反转 
            tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
            int op1=tr[u<<1].max_l;
            int op2=tr[u<<1].max_r;
            int op3=tr[u<<1].max_z;
            int op4=tr[u<<1].ma_;
            tr[u<<1].max_l=tr[u<<1].maxl;//将1和0相关属性转换 
            tr[u<<1].max_r=tr[u<<1].maxr;
            tr[u<<1].max_z=tr[u<<1].maxz;
            tr[u<<1].ma_=tr[u<<1].ma;
            tr[u<<1].maxl=op1;
            tr[u<<1].maxr=op2;
            tr[u<<1].maxz=op3;
            tr[u<<1].ma=op4;

            tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
            op1=tr[u<<1|1].max_l;
            op2=tr[u<<1|1].max_r;
            op3=tr[u<<1|1].max_z;
            op4=tr[u<<1|1].ma_;
            tr[u<<1|1].max_l=tr[u<<1|1].maxl;
            tr[u<<1|1].max_r=tr[u<<1|1].maxr;
            tr[u<<1|1].max_z=tr[u<<1|1].maxz;
            tr[u<<1|1].ma_=tr[u<<1|1].ma;
            tr[u<<1|1].maxl=op1;
            tr[u<<1|1].maxr=op2;
            tr[u<<1|1].maxz=op3;
            tr[u<<1|1].ma=op4;
        }
    }
    tr[u].add1=0;
    tr[u].add0=0;
    tr[u].add=0;
}
void modify1(int u,int l,int r){//全改为1 
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].add1=1;
        tr[u].add0=0;
        tr[u].add=0;//清空其他懒标记 
        tr[u].sum=tr[u].r-tr[u].l+1;
        tr[u].maxl=tr[u].sum;
        tr[u].maxr=tr[u].sum;
        tr[u].maxz=tr[u].sum;
        tr[u].ma=tr[u].sum;
        tr[u].max_l=0;
        tr[u].max_r=0;
        tr[u].max_z=0;
        tr[u].ma_=0;
        return ;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
    if(mid<l) modify1(u<<1|1,l,r);
    else if(mid>=r) modify1(u<<1,l,r);
    else{
        modify1(u<<1,l,r);
        modify1(u<<1|1,l,r);
    }
    pushup(u);
}
void modify0(int u,int l,int r){//全改为0 
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].add1=0;
        tr[u].add0=1;
        tr[u].add=0;
        tr[u].sum=0;
        tr[u].maxl=0;
        tr[u].maxr=0;
        tr[u].maxz=0;
        tr[u].ma=0;
        tr[u].max_l=tr[u].r-tr[u].l+1;
        tr[u].max_r=tr[u].max_l;
        tr[u].max_z=tr[u].max_l;
        tr[u].ma_=tr[u].max_l;
        return ;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
    if(mid<l) modify0(u<<1|1,l,r);
    else if(mid>=r) modify0(u<<1,l,r);
    else{
        modify0(u<<1,l,r);
        modify0(u<<1|1,l,r);
    }
    pushup(u);
}
void modify(int u,int l,int r){//反转 
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].add++;
        tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum;
        int op1=tr[u].max_l;
        int op2=tr[u].max_r;
        int op3=tr[u].max_z;
        int op4=tr[u].ma_;
        tr[u].max_l=tr[u].maxl;
        tr[u].max_r=tr[u].maxr;
        tr[u].max_z=tr[u].maxz;
        tr[u].ma_=tr[u].ma;
        tr[u].maxl=op1;
        tr[u].maxr=op2;
        tr[u].maxz=op3;
        tr[u].ma=op4;
        return ;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
    if(mid<l) modify(u<<1|1,l,r);
    else if(mid>=r) modify(u<<1,l,r);
    else{
        modify(u<<1,l,r);
        modify(u<<1|1,l,r);
    }
    pushup(u);
}
NODE query(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r){
        return tr[u];
    }
    pushdown(u);
    NODE ans;
    int mid=(tr[u].l+tr[u].r)/2;
    if(mid<l) ans=query(u<<1|1,l,r);
    else if(mid>=r) ans=query(u<<1,l,r);
    else{
        NODE zuo=query(u<<1,l,r);
        NODE you=query(u<<1|1,l,r);
        pushup(ans,zuo,you);
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        l+=1;
        r+=1;
        if(op==0){
            modify0(1,l,r);
        }else if(op==1){
            modify1(1,l,r);
        }else if(op==2){
            modify(1,l,r);
        }else if(op==3){
            NODE ans=query(1,l,r);
            printf("%d\n",ans.sum);
        }else{
            NODE ans=query(1,l,r);
            printf("%d\n",ans.ma);
        }
    }
    return 0;
}

by Awsdkl @ 2024-11-28 10:57:21

虽然但是，好神奇的变量名...

by Awsdkl @ 2024-11-28 11:05:48

感觉push_down写复杂了

by iranai @ 2024-11-28 11:17:54

@Awsdkl我太弱了，这样写感觉思路清晰一点

by Awsdkl @ 2024-11-28 11:24:44

@iranai 其实你可以保证add,add1,add0这三个tag不同时存在的。在modify这个操作中如果add1或者add0两个tag存在那你把这两个tag swap一下就可以了，然后pushdown也差不多是这个操作。
还有你pushdown中用swap感觉会更清晰

by Awsdkl @ 2024-11-28 11:26:37

然后建议三个tag改成bool类型的，这样每次改add操作就可以直接异或1

by Awsdkl @ 2024-11-28 11:34:03

你这份代码好像三个tag就是只会存在一个tag的

by iranai @ 2024-11-28 11:46:07

@Awsdkl那请问如何修改才能A，卡好久了A不了

by Awsdkl @ 2024-11-28 17:04:18

@iranai

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100000+10];
struct NODE{
    int l,r;
    int add1;
    int add0;
    int add;
    int sum;
    int maxl;
    int maxr;
    int maxz;
    int ma;
    int max_l;
    int max_r;
    int max_z;
    int ma_;
};
NODE tr[400000+10];
void pushup(NODE &root,NODE &zuo,NODE &you){
+   root.l = zuo.l;
+   root.r = you.r;
    root.sum=zuo.sum+you.sum;
    root.maxl=(zuo.maxl==zuo.r-zuo.l+1?zuo.maxl+you.maxl:zuo.maxl);
    root.maxr=(you.maxr==you.r-you.l+1?you.maxr+zuo.maxr:you.maxr);
    root.maxz=zuo.maxr+you.maxl;
-   root.ma=max(root.maxl,max(root.maxz,root.maxr));
+   root.ma=max({root.maxl,root.maxz,root.maxr,zuo.ma,you.ma});

    root.max_l=(zuo.max_l==zuo.r-zuo.l+1?zuo.max_l+you.max_l:zuo.max_l);
    root.max_r=(you.max_r==you.r-you.l+1?you.max_r+zuo.max_r:you.max_r);
    root.max_z=zuo.max_r+you.max_l;
-   root.ma_=max(root.max_l,max(root.max_z,root.max_r));
+   root.ma_=max({root.max_l,root.max_z,root.max_r,zuo.ma_,you.ma_});
}
void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
    if(l==r){
        if(a[l]==1) tr[u]=(NODE){l,r,0,0,0,1,1,1,1,1,0,0,0,0};
        else tr[u]=(NODE){l,r,0,0,0,0,0,0,0,0,1,1,1,1};
        return ;
    }
-   tr[u]=(NODE){l,r,0,0,0};
    int mid=(l+r)/2;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void pushdown(int u){
-   if(tr[u].add1==1){
-       tr[u<<1].add1=1;
-       tr[u<<1].add+=tr[u].add;
-       tr[u<<1|1].add1=1;
-       tr[u<<1|1].add+=tr[u].add;
-       if(tr[u].add%2==0){
-           tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1;
-           tr[u<<1].maxl=tr[u<<1].sum;
-           tr[u<<1].maxr=tr[u<<1].sum;
-           tr[u<<1].maxz=tr[u<<1].sum;
-           tr[u<<1].ma=tr[u<<1].sum;
-           tr[u<<1].max_l=0;
-           tr[u<<1].max_r=0;
-           tr[u<<1].max_z=0;
-           tr[u<<1].ma_=0;
-           
-           tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1;
-           tr[u<<1|1].maxl=tr[u<<1|1].sum;
-           tr[u<<1|1].maxr=tr[u<<1|1].sum;
-           tr[u<<1|1].maxz=tr[u<<1|1].sum;
-           tr[u<<1|1].ma=tr[u<<1|1].sum;
-           tr[u<<1|1].max_l=0;
-           tr[u<<1|1].max_r=0;
-           tr[u<<1|1].max_z=0;
-           tr[u<<1|1].ma_=0;
-       }else{
-           tr[u<<1].sum=0;
-           tr[u<<1].maxl=0;
-           tr[u<<1].maxr=0;
-           tr[u<<1].maxz=0;
-           tr[u<<1].ma=0;
-           tr[u<<1].max_l=tr[u<<1].r-tr[u<<1].l+1;
-           tr[u<<1].max_r=tr[u<<1].max_l;
-           tr[u<<1].max_z=tr[u<<1].max_l;
-           tr[u<<1].ma_=tr[u<<1].max_l;
-           
-           tr[u<<1|1].sum=0;
-           tr[u<<1|1].maxl=0;
-           tr[u<<1|1].maxr=0;
-           tr[u<<1|1].maxz=0;
-           tr[u<<1|1].ma=0;
-           tr[u<<1|1].max_l=tr[u<<1|1].r-tr[u<<1|1].l+1;
-           tr[u<<1|1].max_r=tr[u<<1|1].max_l;
-           tr[u<<1|1].max_z=tr[u<<1|1].max_l;
-           tr[u<<1|1].ma_=tr[u<<1|1].max_l;
-       }
-   }else if(tr[u].add0==1){
-       tr[u<<1].add0=1;
-       tr[u<<1].add+=tr[u].add;
-       tr[u<<1|1].add0=1;
-       tr[u<<1|1].add+=tr[u].add;
-       if(tr[u].add%2==1){
-           tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1;
-           tr[u<<1].maxl=tr[u<<1].sum;
-           tr[u<<1].maxr=tr[u<<1].sum;
-           tr[u<<1].maxz=tr[u<<1].sum;
-           tr[u<<1].ma=tr[u<<1].sum;
-           tr[u<<1].max_l=0;
-           tr[u<<1].max_r=0;
-           tr[u<<1].max_z=0;
-           tr[u<<1].ma_=0;
-           
-           
-           tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1;
-           tr[u<<1|1].maxl=tr[u<<1|1].sum;
-           tr[u<<1|1].maxr=tr[u<<1|1].sum;
-           tr[u<<1|1].maxz=tr[u<<1|1].sum;
-           tr[u<<1|1].ma=tr[u<<1|1].sum;
-           tr[u<<1|1].max_l=0;
-           tr[u<<1|1].max_r=0;
-           tr[u<<1|1].max_z=0;
-           tr[u<<1|1].ma_=0;
-       }else{
-           tr[u<<1].sum=0;
-           tr[u<<1].maxl=0;
-           tr[u<<1].maxr=0;
-           tr[u<<1].maxz=0;
-           tr[u<<1].ma=0;
-           tr[u<<1].max_l=tr[u<<1].r-tr[u<<1].l+1;
-           tr[u<<1].max_r=tr[u<<1].max_l;
-           tr[u<<1].max_z=tr[u<<1].max_l;
-           tr[u<<1].ma_=tr[u<<1].max_l;
-           
-           tr[u<<1|1].sum=0;
-           tr[u<<1|1].maxl=0;
-           tr[u<<1|1].maxr=0;
-           tr[u<<1|1].maxz=0;
-           tr[u<<1|1].ma=0;
-           tr[u<<1|1].max_l=tr[u<<1|1].r-tr[u<<1|1].l+1;
-           tr[u<<1|1].max_r=tr[u<<1|1].max_l;
-           tr[u<<1|1].max_z=tr[u<<1|1].max_l;
-           tr[u<<1|1].ma_=tr[u<<1|1].max_l;
-       }
-   }else{
-       tr[u<<1].add+=tr[u].add;
-       tr[u<<1|1].add+=tr[u].add;
-       if(tr[u].add%2==1){
-           tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
-           int op1=tr[u<<1].max_l;
-           int op2=tr[u<<1].max_r;
-           int op3=tr[u<<1].max_z;
-           int op4=tr[u<<1].ma_;
-           tr[u<<1].max_l=tr[u<<1].maxl;
-           tr[u<<1].max_r=tr[u<<1].maxr;
-           tr[u<<1].max_z=tr[u<<1].maxz;
-           tr[u<<1].ma_=tr[u<<1].ma;
-           tr[u<<1].maxl=op1;
-           tr[u<<1].maxr=op2;
-           tr[u<<1].maxz=op3;
-           tr[u<<1].ma=op4;
-           
-           tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
-           op1=tr[u<<1|1].max_l;
-           op2=tr[u<<1|1].max_r;
-           op3=tr[u<<1|1].max_z;
-           op4=tr[u<<1|1].ma_;
-           tr[u<<1|1].max_l=tr[u<<1|1].maxl;
-           tr[u<<1|1].max_r=tr[u<<1|1].maxr;
-           tr[u<<1|1].max_z=tr[u<<1|1].maxz;
-           tr[u<<1|1].ma_=tr[u<<1|1].ma;
-           tr[u<<1|1].maxl=op1;
-           tr[u<<1|1].maxr=op2;
-           tr[u<<1|1].maxz=op3;
-           tr[u<<1|1].ma=op4;
-       }
-   }
-   tr[u].add1=0;
-   tr[u].add0=0;
-   tr[u].add=0;
+   if(tr[u].add1){
+       tr[u<<1].add1 = tr[u<<1|1].add1 = 1;
+       tr[u<<1].add0 = tr[u<<1].add = tr[u<<1|1].add0 = tr[u<<1|1].add = 0;
+
+       tr[u<<1].max_l = tr[u<<1].max_z = tr[u<<1].max_r = tr[u<<1].ma_ = 0;
+       tr[u<<1|1].max_l = tr[u<<1|1].max_z = tr[u<<1|1].max_r = tr[u<<1|1].ma_ = 0;
+
+       tr[u<<1].maxl = tr[u<<1].maxz = tr[u<<1].maxr = tr[u<<1].ma = tr[u<<1].r - tr[u<<1].l + 1;
+       tr[u<<1|1].maxl = tr[u<<1|1].maxz = tr[u<<1|1].maxr = tr[u<<1|1].ma = tr[u<<1|1].r - tr[u<<1|1].l + 1;
+
+       tr[u<<1].sum = tr[u<<1].r - tr[u<<1].l + 1;
+       tr[u<<1|1].sum = tr[u<<1|1].r - tr[u<<1|1].l + 1;
+
+       tr[u].add1 = 0;
+       return;
+   }
+   if(tr[u].add0){
+       tr[u<<1].add0 = tr[u<<1|1].add0 = 1;
+       tr[u<<1].add1 = tr[u<<1].add = tr[u<<1|1].add1 = tr[u<<1|1].add = 0;
+
+       tr[u<<1].max_l = tr[u<<1].max_z = tr[u<<1].max_r = tr[u<<1].ma_ = tr[u<<1].r - tr[u<<1].l + 1;
+       tr[u<<1|1].max_l = tr[u<<1|1].max_z = tr[u<<1|1].max_r = tr[u<<1|1].ma_ = tr[u<<1|1].r - tr[u<<1|1].l + 1;
+
+       tr[u<<1].maxl = tr[u<<1].maxz = tr[u<<1].maxr = tr[u<<1].ma = 0;
+       tr[u<<1|1].maxl = tr[u<<1|1].maxz = tr[u<<1|1].maxr = tr[u<<1|1].ma = 0;
+
+       tr[u<<1].sum = 0;
+       tr[u<<1|1].sum = 0;
+
+       tr[u].add0 = 0;
+       return;
+   }
+   if(tr[u].add&1)
+   {
+       if(tr[u<<1].add0 || tr[u<<1].add1) swap(tr[u<<1].add0,tr[u<<1].add1);
+       else tr[u<<1].add += 1;
+       if(tr[u<<1|1].add0 || tr[u<<1|1].add1) swap(tr[u<<1|1].add0,tr[u<<1|1].add1);
+       else tr[u<<1|1].add += 1;
+
+       swap(tr[u<<1].maxl,tr[u<<1].max_l);
+       swap(tr[u<<1].maxr,tr[u<<1].max_r);
+       swap(tr[u<<1].maxz,tr[u<<1].max_z);
+       swap(tr[u<<1].ma,tr[u<<1].ma_);
+
+       swap(tr[u<<1|1].maxl,tr[u<<1|1].max_l);
+       swap(tr[u<<1|1].maxr,tr[u<<1|1].max_r);
+       swap(tr[u<<1|1].maxz,tr[u<<1|1].max_z);
+       swap(tr[u<<1|1].ma,tr[u<<1|1].ma_);
+
+       tr[u<<1].sum = tr[u<<1].r - tr[u<<1].l + 1 - tr[u<<1].sum;
+       tr[u<<1|1].sum = tr[u<<1|1].r - tr[u<<1|1].l + 1 - tr[u<<1|1].sum;
+
+       tr[u].add = 0;
+       return;
+   }
}
void modify1(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].add1=1;
        tr[u].add0=0;
        tr[u].add=0;
        tr[u].sum=tr[u].r-tr[u].l+1;
        tr[u].maxl=tr[u].sum;
        tr[u].maxr=tr[u].sum;
        tr[u].maxz=tr[u].sum;
        tr[u].ma=tr[u].sum;
        tr[u].max_l=0;
        tr[u].max_r=0;
        tr[u].max_z=0;
        tr[u].ma_=0;
        return ;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
-   if(mid<l) modify1(u<<1|1,l,r);
-   else if(mid>=r) modify1(u<<1,l,r);
-   else{
-       modify1(u<<1,l,r);
-       modify1(u<<1|1,l,r);
-   }
+   if(l <= mid) modify1(u<<1,l,r);
+   if(r > mid) modify1(u<<1|1,l,r);
    pushup(u);
}
void modify0(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r){
        tr[u].add1=0;
        tr[u].add0=1;
        tr[u].add=0;
        tr[u].sum=0;
        tr[u].maxl=0;
        tr[u].maxr=0;
        tr[u].maxz=0;
        tr[u].ma=0;
        tr[u].max_l=tr[u].r-tr[u].l+1;
        tr[u].max_r=tr[u].max_l;
        tr[u].max_z=tr[u].max_l;
        tr[u].ma_=tr[u].max_l;
        return ;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
-   if(mid<l) modify0(u<<1|1,l,r);
-   else if(mid>=r) modify0(u<<1,l,r);
-   else{
-       modify0(u<<1,l,r);
-       modify0(u<<1|1,l,r);
-   }
+   if(l <= mid) modify0(u<<1,l,r);
+   if(r > mid) modify0(u<<1|1,l,r);
    pushup(u);
}
void modify(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r){
+       if(tr[u].add1 || tr[u].add0)
+       {
+           swap(tr[u].add1,tr[u].add0);
+       }
+       else tr[u].add ^= 1;
-       tr[u].add++;
        tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum;
        int op1=tr[u].max_l;
        int op2=tr[u].max_r;
        int op3=tr[u].max_z;
        int op4=tr[u].ma_;
        tr[u].max_l=tr[u].maxl;
        tr[u].max_r=tr[u].maxr;
        tr[u].max_z=tr[u].maxz;
        tr[u].ma_=tr[u].ma;
        tr[u].maxl=op1;
        tr[u].maxr=op2;
        tr[u].maxz=op3;
        tr[u].ma=op4;
        return ;
    }
    pushdown(u);
    int mid=(tr[u].l+tr[u].r)/2;
    if(mid<l) modify(u<<1|1,l,r);
    else if(mid>=r) modify(u<<1,l,r);
    else{
        modify(u<<1,l,r);
        modify(u<<1|1,l,r);
    }
    pushup(u);
}
NODE query(int u,int l,int r){
    if(l<=tr[u].l&&tr[u].r<=r){
        return tr[u];
    }
    pushdown(u);
    NODE ans;
    int mid=(tr[u].l+tr[u].r)/2;
-   if(mid<l) ans=query(u<<1|1,l,r);
-   else if(mid>=r) ans=query(u<<1,l,r);
-   else{
-       NODE zuo=query(u<<1,l,r);
-       NODE you=query(u<<1|1,l,r);
-       pushup(ans,zuo,you);
-   }
+   if(l <= mid)
+   {
+       ans = query(u<<1,l,r);
+       if(r > mid) 
+       {
+           NODE tmp = query(u<<1|1,l,r);
+           NODE ans1;
+           pushup(ans1,ans,tmp);
+           ans = ans1;
+       }
+   }
+   else if(r > mid) ans = query(u<<1|1,l,r);
    pushup(u);
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(m--){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        l+=1;
        r+=1;
        if(op==0){
            modify0(1,l,r);
        }else if(op==1){
            modify1(1,l,r);
        }else if(op==2){
            modify(1,l,r);
        }else if(op==3){
            NODE ans=query(1,l,r);
            printf("%d\n",ans.sum);
        }else{
            NODE ans=query(1,l,r);
            printf("%d\n",ans.ma);
        }
    }
    return 0;
}

by Awsdkl @ 2024-11-28 17:04:51

可能改多了，但先凑合着看吧

by Awsdkl @ 2024-11-28 17:07:15

AC代码