求助(对代码帮助的都会关)

Binah_cyc @ 2024-02-05 10:47:28

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[100005];
struct SegmentTree
{
    int l,r;
    int change,addreverse;//reverse:1=yes,0=no
    int lmax0,rmax0,sum0,kmax0;
    int lmax1,rmax1,sum1,kmax1;
} t[100005<<2];
SegmentTree merge(SegmentTree A,SegmentTree b)
{
    SegmentTree t;
    t.l=A.l,t.r=b.r;
    t.lmax0=A.lmax0,t.lmax1=A.lmax1;
    t.rmax0=b.rmax0,t.rmax1=b.rmax1;
    t.sum0=A.sum0+b.sum0,t.sum1=A.sum1+b.sum1;
    t.kmax0=max(max(A.kmax0,b.kmax0),A.rmax0+b.lmax0);
    t.kmax1=max(max(A.kmax1,b.kmax1),A.rmax1+b.lmax1);
    if(A.lmax0==A.r-A.l+1||!A.lmax0) t.lmax0+=b.lmax0;
    if(A.lmax1==A.r-A.l+1||!A.lmax1) t.lmax1+=b.lmax1;
    if(b.rmax0==b.r-b.l+1||!b.rmax0) t.rmax0+=A.rmax0;
    if(b.rmax1==b.r-b.l+1||!b.rmax1) t.rmax1+=A.rmax1;
    return t;
}
void pushup(int p)
{
    t[p].l=t[p*2].l,t[p].r=t[p*2+1].r;
    t[p].lmax0=t[p*2].lmax0,t[p].lmax1=t[p*2].lmax1;
    t[p].rmax0=t[p*2+1].rmax0,t[p].rmax1=t[p*2+1].rmax1;
    t[p].sum0=t[p*2].sum0+t[p*2+1].sum0,t[p].sum1=t[p*2].sum1+t[p*2+1].sum1;
    t[p].kmax0=max(max(t[p*2].kmax0,t[p*2+1].kmax0),t[p*2].rmax0+t[p*2+1].lmax0);
    t[p].kmax1=max(max(t[p*2].kmax1,t[p*2+1].kmax1),t[p*2].rmax1+t[p*2+1].lmax1);
    if(t[p*2].lmax0==t[p*2].r-t[p*2].l+1) t[p].lmax0+=t[p*2+1].lmax0;
    if(t[p*2].lmax1==t[p*2].r-t[p*2].l+1) t[p].lmax1+=t[p*2+1].lmax1;
    if(t[p*2+1].rmax0==t[p*2+1].r-t[p*2+1].l+1) t[p].rmax0+=t[p*2].rmax0;
    if(t[p*2+1].rmax1==t[p*2+1].r-t[p*2+1].l+1) t[p].rmax1+=t[p*2].rmax1;
}
void spread(int p)
{
    if(t[p].change!=-1)
    {
        t[p*2].lmax1=t[p*2].rmax1=t[p*2].kmax1=t[p*2].sum1=(t[p*2].r-t[p*2].l+1)*t[p].change;
        t[p*2].lmax0=t[p*2].rmax0=t[p*2].kmax0=t[p*2].sum0=(t[p*2].r-t[p*2].l+1)*(!t[p].change);
        t[p*2+1].lmax1=t[p*2+1].rmax1=t[p*2+1].kmax1=t[p*2+1].sum1=(t[p*2+1].r-t[p*2+1].l+1)*t[p].change;
        t[p*2+1].lmax0=t[p*2+1].rmax0=t[p*2+1].kmax0=t[p*2+1].sum0=(t[p*2+1].r-t[p*2+1].l+1)*(!t[p].change);
        t[p*2].change=t[p*2+1].change=t[p].change;
        t[p*2].addreverse=t[p*2+1].addreverse=t[p].addreverse=0;
        t[p].change=-1;
    }
    else if(t[p].addreverse)
    {
        swap(t[p*2].sum0,t[p*2].sum1);
        swap(t[p*2].lmax0,t[p*2].lmax1);
        swap(t[p*2].rmax0,t[p*2].rmax1);
        swap(t[p*2].kmax0,t[p*2].kmax1);
        swap(t[p*2+1].sum0,t[p*2+1].sum1);
        swap(t[p*2+1].lmax0,t[p*2+1].lmax1);
        swap(t[p*2+1].rmax0,t[p*2+1].rmax1);
        swap(t[p*2+1].kmax0,t[p*2+1].kmax1);
        if(t[p*2].change!=-1) t[p*2].change=1-t[p*2].change;
        else t[p*2].addreverse^=1;
        if(t[p*2+1].change!=-1) t[p*2+1].change=1-t[p*2+1].change;
        else t[p*2+1].addreverse^=1;
        t[p].addreverse=0;
    }
}
void build(int l,int r,int p)
{
    t[p].l=l,t[p].r=r,t[p].change=-1,t[p].addreverse=0;
    if(l==r) return (void)(t[p].lmax0=t[p].rmax0=t[p].kmax0=t[p].sum0=(a[l]==0),t[p].lmax1=t[p].rmax1=t[p].kmax1=t[p].sum1=(a[l]==1));
    int mid=(l+r)>>1;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    pushup(p);
}
void change0(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        t[p].lmax0=t[p].rmax0=t[p].kmax0=t[p].sum0=t[p].r-t[p].l+1;
        t[p].lmax1=t[p].rmax1=t[p].kmax1=t[p].sum1=0;
        t[p].change=0,t[p].addreverse=0;
        return ;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change0(l,r,p*2);
    if(r>mid)  change0(l,r,p*2+1);
    pushup(p);
}
void change1(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        cout<<t[p].l<<' '<<t[p].r<<endl;
        t[p].lmax1=t[p].rmax1=t[p].kmax1=t[p].sum1=t[p].r-t[p].l+1;
        t[p].lmax0=t[p].rmax0=t[p].kmax0=t[p].sum0=0;
        t[p].change=1,t[p].addreverse=0;
        return ;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change1(l,r,p*2);
    if(r>mid)  change1(l,r,p*2+1);
    pushup(p);
}
void changereverse(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        swap(t[p].lmax0,t[p].lmax1),swap(t[p].rmax0,t[p].rmax1);
        swap(t[p].kmax0,t[p].kmax1),swap(t[p].sum0,t[p].sum1);
        if(t[p].change!=-1) t[p].change^=1;
        else t[p].addreverse^=1;
        return ;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) changereverse(l,r,p*2);
    if(r>mid)  changereverse(l,r,p*2+1);
    pushup(p);
}
int asksum(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p].sum1;
    spread(p);
    int mid=(t[p].l+t[p].r)>>1,cnt=0;
    if(l<=mid) cnt+=asksum(l,r,p*2);
    if(r>mid)  cnt+=asksum(l,r,p*2+1);
    return cnt;
}
SegmentTree ask(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p];
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid&&r>mid) return merge(ask(l,r,p*2),ask(l,r,p*2+1));
    else if(l<=mid) return ask(l,r,p*2);
    else return ask(l,r,p*2+1);
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    build(1,n,1);
    while(m--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        l++,r++;
        if(op==0) change0(l,r,1);
        else if(op==1) change1(l,r,1);
        else if(op==2) changereverse(l,r,1);
        else if(op==3) cout<<asksum(l,r,1)<<endl;
        else if(op==4) cout<<ask(l,r,1).kmax1<<endl;
    }
    return 0;
}

by sunkaihuan @ 2024-02-05 11:42:45

过了

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,a[100005];
struct SegmentTree
{
    int l,r;
    int change,addreverse;//reverse:1=yes,0=no
    int lmax0,rmax0,sum0,kmax0;
    int lmax1,rmax1,sum1,kmax1;
} t[100005<<2];
SegmentTree merge(SegmentTree A,SegmentTree b)
{
    SegmentTree t;
    t.l=A.l,t.r=b.r;
    t.lmax0=A.lmax0,t.lmax1=A.lmax1;
    t.rmax0=b.rmax0,t.rmax1=b.rmax1;
    t.sum0=A.sum0+b.sum0,t.sum1=A.sum1+b.sum1;
    t.kmax0=max(max(A.kmax0,b.kmax0),A.rmax0+b.lmax0);
    t.kmax1=max(max(A.kmax1,b.kmax1),A.rmax1+b.lmax1);
    if(A.lmax0==A.r-A.l+1) t.lmax0+=b.lmax0;
    if(A.lmax1==A.r-A.l+1) t.lmax1+=b.lmax1;
    if(b.rmax0==b.r-b.l+1) t.rmax0+=A.rmax0;
    if(b.rmax1==b.r-b.l+1) t.rmax1+=A.rmax1;
    return t;
}
void pushup(int p)
{
    t[p].l=t[p*2].l,t[p].r=t[p*2+1].r;
    t[p].lmax0=t[p*2].lmax0,t[p].lmax1=t[p*2].lmax1;
    t[p].rmax0=t[p*2+1].rmax0,t[p].rmax1=t[p*2+1].rmax1;
    t[p].sum0=t[p*2].sum0+t[p*2+1].sum0,t[p].sum1=t[p*2].sum1+t[p*2+1].sum1;
    t[p].kmax0=max(max(t[p*2].kmax0,t[p*2+1].kmax0),t[p*2].rmax0+t[p*2+1].lmax0);
    t[p].kmax1=max(max(t[p*2].kmax1,t[p*2+1].kmax1),t[p*2].rmax1+t[p*2+1].lmax1);
    if(t[p*2].lmax0==t[p*2].r-t[p*2].l+1) t[p].lmax0+=t[p*2+1].lmax0;
    if(t[p*2].lmax1==t[p*2].r-t[p*2].l+1) t[p].lmax1+=t[p*2+1].lmax1;
    if(t[p*2+1].rmax0==t[p*2+1].r-t[p*2+1].l+1) t[p].rmax0+=t[p*2].rmax0;
    if(t[p*2+1].rmax1==t[p*2+1].r-t[p*2+1].l+1) t[p].rmax1+=t[p*2].rmax1;
}
void spread(int p)
{
    if(t[p].change!=-1)
    {
        t[p*2].lmax1=t[p*2].rmax1=t[p*2].kmax1=t[p*2].sum1=(t[p*2].r-t[p*2].l+1)*t[p].change;
        t[p*2].lmax0=t[p*2].rmax0=t[p*2].kmax0=t[p*2].sum0=(t[p*2].r-t[p*2].l+1)*(!t[p].change);
        t[p*2+1].lmax1=t[p*2+1].rmax1=t[p*2+1].kmax1=t[p*2+1].sum1=(t[p*2+1].r-t[p*2+1].l+1)*t[p].change;
        t[p*2+1].lmax0=t[p*2+1].rmax0=t[p*2+1].kmax0=t[p*2+1].sum0=(t[p*2+1].r-t[p*2+1].l+1)*(!t[p].change);
        t[p*2].change=t[p*2+1].change=t[p].change;
        t[p*2].addreverse=t[p*2+1].addreverse=0;
        t[p].change=-1;
    }
    else if(t[p].addreverse)
    {
        swap(t[p*2].sum0,t[p*2].sum1);
        swap(t[p*2].lmax0,t[p*2].lmax1);
        swap(t[p*2].rmax0,t[p*2].rmax1);
        swap(t[p*2].kmax0,t[p*2].kmax1);
        swap(t[p*2+1].sum0,t[p*2+1].sum1);
        swap(t[p*2+1].lmax0,t[p*2+1].lmax1);
        swap(t[p*2+1].rmax0,t[p*2+1].rmax1);
        swap(t[p*2+1].kmax0,t[p*2+1].kmax1);
        if(t[p*2].change!=-1) t[p*2].change^=1;
        else t[p*2].addreverse^=1;
        if(t[p*2+1].change!=-1) t[p*2+1].change^=1;
        else t[p*2+1].addreverse^=1;
        t[p].addreverse=0;
    }
}
void build(int l,int r,int p)
{
    t[p].l=l,t[p].r=r,t[p].change=-1,t[p].addreverse=0;
    if(l==r) return (void)(t[p].lmax0=t[p].rmax0=t[p].kmax0=t[p].sum0=(a[l]==0),t[p].lmax1=t[p].rmax1=t[p].kmax1=t[p].sum1=(a[l]==1));
    int mid=(l+r)>>1;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    pushup(p);
}
void change0(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        t[p].lmax0=t[p].rmax0=t[p].kmax0=t[p].sum0=t[p].r-t[p].l+1;
        t[p].lmax1=t[p].rmax1=t[p].kmax1=t[p].sum1=0;
        t[p].change=0,t[p].addreverse=0;
        return ;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change0(l,r,p*2);
    if(r>mid)  change0(l,r,p*2+1);
    pushup(p);
}
void change1(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        //cout<<t[p].l<<' '<<t[p].r<<endl;
        t[p].lmax1=t[p].rmax1=t[p].kmax1=t[p].sum1=t[p].r-t[p].l+1;
        t[p].lmax0=t[p].rmax0=t[p].kmax0=t[p].sum0=0;
        t[p].change=1,t[p].addreverse=0;
        return ;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change1(l,r,p*2);
    if(r>mid)  change1(l,r,p*2+1);
    pushup(p);
}
void changereverse(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        swap(t[p].lmax0,t[p].lmax1),swap(t[p].rmax0,t[p].rmax1);
        swap(t[p].kmax0,t[p].kmax1),swap(t[p].sum0,t[p].sum1);
        if(t[p].change!=-1) t[p].change^=1; else t[p].addreverse^=1;
        return ;
    }
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) changereverse(l,r,p*2);
    if(r>mid)  changereverse(l,r,p*2+1);
    pushup(p);
}
int asksum(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p].sum1;
    spread(p);
    int mid=(t[p].l+t[p].r)>>1,cnt=0;
    if(l<=mid) cnt+=asksum(l,r,p*2);
    if(r>mid)  cnt+=asksum(l,r,p*2+1);
    return cnt;
}
SegmentTree ask(int l,int r,int p)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p];
    spread(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid&&r>mid) return merge(ask(l,r,p*2),ask(l,r,p*2+1));
    else if(l<=mid) return ask(l,r,p*2);
    else return ask(l,r,p*2+1);
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    build(1,n,1);
    while(m--)
    {
        int op,l,r;
        cin>>op>>l>>r;
        l++,r++;
        if(op==0) change0(l,r,1);
        else if(op==1) change1(l,r,1);
        else if(op==2) changereverse(l,r,1);
        else if(op==3) cout<<asksum(l,r,1)<<endl;
        else if(op==4) cout<<ask(l,r,1).kmax1<<endl;
    }
    return 0;
}
```cpp

by sunkaihuan @ 2024-02-05 11:45:04

merge里这一段去掉||后面的内容，否则会因为合并左/右信息时因为没有01前后缀而错误

if(A.lmax0==A.r-A.l+1||!A.lmax0) t.lmax0+=b.lmax0;
    if(A.lmax1==A.r-A.l+1||!A.lmax1) t.lmax1+=b.lmax1;
    if(b.rmax0==b.r-b.l+1||!b.rmax0) t.rmax0+=A.rmax0;
    if(b.rmax1==b.r-b.l+1||!b.rmax1) t.rmax1+=A.rmax1;

by Binah_cyc @ 2024-02-05 11:47:39

十分感谢，已关！！！ @sunkaihuan