只有hack过了，求调

DYhzx_QWQ @ 2024-03-31 11:23:19

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,tt,rt;
struct bb {
    ll l1,l0,num,l,r,q1,q0,h1,h0,bj;//bj=1/2:赋值为0/1;bj=3:翻转
}tree[800005];
struct bl {
    ll q,h,l;
};
void pushup(ll x,ll ls,ll rs) {
    ll l=tree[x].l,r=tree[x].r,mid=(ls+rs)>>1;
    tree[x].num=tree[l].num+tree[r].num;
    tree[x].l0=max(max(tree[l].l0,tree[r].l0),tree[l].h0+tree[r].q0);
    tree[x].l1=max(max(tree[l].l1,tree[r].l1),tree[l].h1+tree[r].q1);
    tree[x].q1=(tree[l].q1+((tree[l].q1==mid-ls+1)?tree[r].q1:0)),tree[x].q0=(tree[l].q0+((tree[l].q0==mid-ls+1)?tree[r].q0:0));
    tree[x].h0=(tree[r].h0+((tree[r].h0==rs-mid)?tree[l].h0:0)),tree[x].h1=(tree[r].h1+((tree[r].h1==rs-mid)?tree[l].h1:0));
}
void pushdown(ll x,ll l,ll r) {
    ll w=tree[x].bj;
    if(!w) return ;
    if(w==1) {
        tree[x].num=0;
        tree[x].h0=tree[x].l0=tree[x].q0=r-l+1;
        tree[x].h1=tree[x].l1=tree[x].q1=0;
    }
    if(w==2) {
        tree[x].num=r-l+1;
        tree[x].h0=tree[x].l0=tree[x].q0=0;
        tree[x].h1=tree[x].l1=tree[x].q1=r-l+1;
    }
    if(w==3) {
        tree[x].num=r-l+1-tree[x].num;
        swap(tree[x].h0,tree[x].h1);
        swap(tree[x].l0,tree[x].l1);
        swap(tree[x].q0,tree[x].q1);
    }
    if(tree[x].bj==1||tree[x].bj==2) tree[tree[x].l].bj=tree[tree[x].r].bj=tree[x].bj;
    else {
        if(tree[tree[x].l].bj==1) tree[tree[x].l].bj=2;
        else if(tree[tree[x].l].bj==2) tree[tree[x].l].bj=1;
        else if(tree[tree[x].l].bj==3) tree[tree[x].l].bj=0;
        else if(tree[tree[x].l].bj==0) tree[tree[x].l].bj=3;
        if(tree[tree[x].r].bj==1) tree[tree[x].r].bj=2;
        else if(tree[tree[x].r].bj==2) tree[tree[x].r].bj=1;
        else if(tree[tree[x].r].bj==3) tree[tree[x].r].bj=0;
        else if(tree[tree[x].r].bj==0) tree[tree[x].r].bj=3;
    }
    tree[x].bj=0;
}
void add(ll &x,ll l,ll r,ll ls,ll rs,ll w) {
    if(!x) x=++tt;
    if(ls<=l&&r<=rs) {
        pushdown(x,l,r);
        tree[x].bj=w;
        pushdown(x,l,r);
        return ;
    }
    ll mid=(l+r)>>1;
    if(mid>=ls) add(tree[x].l,l,mid,ls,rs,w);
    if(mid<rs) add(tree[x].r,mid+1,r,ls,rs,w);
    if(tree[x].l) pushdown(tree[x].l,l,mid);
    if(tree[x].r) pushdown(tree[x].r,mid+1,r);
    pushup(x,l,r);
}
ll find3(ll x,ll l,ll r,ll ls,ll rs) {
    if(!x) return 0; 
    pushdown(x,l,r);
    if(ls<=l&&r<=rs) return tree[x].num;
    ll mid=(l+r)>>1,sum=0;
    if(mid>=ls) sum+=find3(tree[x].l,l,mid,ls,rs);
    if(mid<rs) sum+=find3(tree[x].r,mid+1,r,ls,rs);
    return sum;
}
bl find4(ll x,ll l,ll r,ll ls,ll rs) {
    if(!x) return (bl){0,0,0};
    pushdown(x,l,r);
    if(ls<=l&&r<=rs) return (bl){tree[x].q1,tree[x].h1,tree[x].l1};
    ll mid=(l+r)>>1;
    bl lw={0,0,0},rw={0,0,0};
    if(mid>=ls) lw=find4(tree[x].l,l,mid,ls,rs);
    if(mid<rs) rw=find4(tree[x].r,mid+1,r,ls,rs);
    return {(lw.q+((lw.q==mid-l+1)?rw.q:0)),(rw.h+(rw.h==r-mid?lw.h:0)),max(lw.l,max(rw.l,lw.h+rw.q))};
}
int main() {
    cin>>n>>m;
    for(ll i=1;i<=n;i++) {
        ll x;
        cin>>x;
        add(rt,1,n,i,i,x+1);
    }
    // cout<<find3(rt,1,n,1,n)<<endl;
    for(ll i=1;i<=m;i++) {
        ll l,r,op;
        cin>>op>>l>>r;
        l++,r++;
        if(op==0||op==1||op==2) add(rt,1,n,l,r,op+1);
        else {
            if(op==3) cout<<find3(rt,1,n,l,r)<<endl;
            if(op==4) cout<<find4(rt,1,n,l,r).l<<endl;
        }
        // for(ll i=1;i<=n;i++) cout<<find3(rt,1,n,i,i)<<' ';
        // cout<<endl;
    }
    return 0;
}
/*
0 0 0 1 1 0 1 0 1 1 

1 1 1 1 1 0 1 0 1 1 8
1 1 1 1 1 0 1 0 1 1 8
1 1 0 1 1 0 1 0 1 1 7
1 1 0 1 1 0 1 0 1 1 7
1 1 0 0 0 0 0 0 1 1 
1 1 0 1 1 1 1 1 1 1 
1 1 0 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 0 0 1 1 1  
*/

by HYLW @ 2024-04-06 17:42:28

俺也一样 T_T

by Contingency_Core @ 2024-06-07 16:08:10

俺也一样Q_Q

by xuchuhan @ 2024-06-25 16:56:11

同问

by HenghengMoi @ 2024-06-25 20:11:42

试试赋值和反转的懒标记分开存

by DYhzx_QWQ @ 2024-10-08 19:46:25

@HYLW @Contingency_Core @xuchuhan

之前调出来了，现在才看到，把AC代码给你们看下，有点忘了是啥问题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,tt,rt;
struct bb {
    ll l1,l0,num,l,r,q1,q0,h1,h0,bj;//bj=1/2:赋值为0/1;bj=3:翻转
}tree[800005];
struct bl {
    ll q,h,l;
};
void pushup(ll x,ll ls,ll rs) {
    ll l=tree[x].l,r=tree[x].r,mid=(ls+rs)>>1;
    tree[x].num=tree[l].num+tree[r].num;
    tree[x].l0=max(max(tree[l].l0,tree[r].l0),tree[l].h0+tree[r].q0);
    tree[x].l1=max(max(tree[l].l1,tree[r].l1),tree[l].h1+tree[r].q1);
    tree[x].q1=(tree[l].q1+((tree[l].q1==mid-ls+1)?tree[r].q1:0)),tree[x].q0=(tree[l].q0+((tree[l].q0==mid-ls+1)?tree[r].q0:0));
    tree[x].h0=(tree[r].h0+((tree[r].h0==rs-mid)?tree[l].h0:0)),tree[x].h1=(tree[r].h1+((tree[r].h1==rs-mid)?tree[l].h1:0));
}
void pushdown(ll x,ll l,ll r) {
    ll w=tree[x].bj;
    if(!w) return ;
    if(w==1) {
        tree[x].num=0;
        tree[x].h0=tree[x].l0=tree[x].q0=r-l+1;
        tree[x].h1=tree[x].l1=tree[x].q1=0;
    }
    if(w==2) {
        tree[x].num=r-l+1;
        tree[x].h0=tree[x].l0=tree[x].q0=0;
        tree[x].h1=tree[x].l1=tree[x].q1=r-l+1;
    }
    if(w==3) {
        tree[x].num=r-l+1-tree[x].num;
        swap(tree[x].h0,tree[x].h1);
        swap(tree[x].l0,tree[x].l1);
        swap(tree[x].q0,tree[x].q1);
    }
    if(tree[x].bj==1||tree[x].bj==2) tree[tree[x].l].bj=tree[tree[x].r].bj=tree[x].bj;
    else {
        if(tree[tree[x].l].bj==1) tree[tree[x].l].bj=2;
        else if(tree[tree[x].l].bj==2) tree[tree[x].l].bj=1;
        else if(tree[tree[x].l].bj==3) tree[tree[x].l].bj=0;
        else if(tree[tree[x].l].bj==0) tree[tree[x].l].bj=3;
        if(tree[tree[x].r].bj==1) tree[tree[x].r].bj=2;
        else if(tree[tree[x].r].bj==2) tree[tree[x].r].bj=1;
        else if(tree[tree[x].r].bj==3) tree[tree[x].r].bj=0;
        else if(tree[tree[x].r].bj==0) tree[tree[x].r].bj=3;
    }
    tree[x].bj=0;
}
void add(ll &x,ll l,ll r,ll ls,ll rs,ll w) {
    if(!x) x=++tt;
    pushdown(x,l,r);
    if(ls<=l&&r<=rs) {
        tree[x].bj=w;
        pushdown(x,l,r);
        return ;
    }
    ll mid=(l+r)>>1;
    if(mid>=ls) add(tree[x].l,l,mid,ls,rs,w);
    if(mid<rs) add(tree[x].r,mid+1,r,ls,rs,w);
    if(tree[x].l) pushdown(tree[x].l,l,mid);
    if(tree[x].r) pushdown(tree[x].r,mid+1,r);
    pushup(x,l,r);
}
ll find3(ll x,ll l,ll r,ll ls,ll rs) {
    if(!x) return 0; 
    pushdown(x,l,r);
    if(ls<=l&&r<=rs) return tree[x].num;
    ll mid=(l+r)>>1,sum=0;
    if(mid>=ls) sum+=find3(tree[x].l,l,mid,ls,rs);
    if(mid<rs) sum+=find3(tree[x].r,mid+1,r,ls,rs);
    return sum;
}
bl find4(ll x,ll l,ll r,ll ls,ll rs) {
    if(!x) return (bl){0,0,0};
    pushdown(x,l,r);
    if(ls<=l&&r<=rs) return (bl){tree[x].q1,tree[x].h1,tree[x].l1};
    ll mid=(l+r)>>1;
    bl lw={0,0,0},rw={0,0,0};
    if(mid>=ls) lw=find4(tree[x].l,l,mid,ls,rs);
    if(mid<rs) rw=find4(tree[x].r,mid+1,r,ls,rs);
    return {(lw.q+((lw.q==mid-max(l,ls)+1)?rw.q:0)),(rw.h+(rw.h==min(rs,r)-mid?lw.h:0)),max(lw.l,max(rw.l,lw.h+rw.q))};
}
int main() {
    cin>>n>>m;
    for(ll i=1;i<=n;i++) {
        ll x;
        cin>>x;
        add(rt,1,n,i,i,x+1);
    }
    // cout<<find3(rt,1,n,1,n)<<endl;
    for(ll i=1;i<=m;i++) {
        ll l,r,op;
        cin>>op>>l>>r;
        l++,r++;
        if(op==0||op==1||op==2) add(rt,1,n,l,r,op+1);
        else {
            if(op==3) cout<<find3(rt,1,n,l,r)<<endl;
            if(op==4) cout<<find4(rt,1,n,l,r).l<<endl;
        }
        // for(ll i=1;i<=n;i++) cout<<find3(rt,1,n,i,i)<<' ';
        // cout<<endl;
    }
    return 0;
}
/*
0 0 0 1 1 0 1 0 1 1 

1 1 1 1 1 0 1 0 1 1 8
1 1 1 1 1 0 1 0 1 1 8
1 1 0 1 1 0 1 0 1 1 7
1 1 0 1 1 0 1 0 1 1 7
1 1 0 0 0 0 0 0 1 1 
1 1 0 1 1 1 1 1 1 1 
1 1 0 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 0 1 1 1
1 1 1 1 1 0 0 1 1 1  

0 0 1 1 1 0 1 1 0 0 1 1 0 
0 1 1 1 1 0 1 1 0 0 1 1 0 
0 1 1 0 0 0 0 1 0 0 1 1 0 
0 1 1 0 0 0 0 1 0 0 1 1 0 
0 1 1 0 0 0 0 1 0 0 1 1 0 
1 1 1 1 1 1 1 1 1 1 1 1 0 
1 1 1 1 1 1 0 0 0 0 0 0 0 
1 1 1 1 0 0 0 0 0 0 0 0 0 
1 1 1 1 1 1 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 1 1 1 1 0
*/

by DYhzx_QWQ @ 2024-10-08 19:49:06

找到了，是少pushdown了

by DYhzx_QWQ @ 2024-10-08 19:49:38

那个add函数里面

by xuchuhan @ 2024-10-08 20:12:43

@DYhzx_QWQ 之前已经调成60pts了，您那个错误我没犯qwq，不过 thx.

by Contingency_Core @ 2024-10-08 20:27:12

@DYhzx_QWQ 我也调出来了，我是向上传值时忘记清空原值了qwq。。。

by HYLW @ 2024-10-09 18:15:36

@DYhzx_QWQ 之前也调出来了，是区间query出了问题，合并区间着实有点烦