小清新马蜂求调，样例没过/kel

mlvx @ 2024-07-06 23:17:05

#include<bits/stdc++.h>
using namespace std;
#define pl (p<<1)
#define pr (p<<1|1)
const int N=1e5+10;
struct Tree{int sum1,sum0,lx1,lx0,llx1,llx0,rlx1,rlx0;}tr[N<<2];
int n,q,op,l,r,a[N],len[N<<2],cov[N<<2],inv[N<<2];
Tree merge(Tree a,Tree b){return {a.sum1+b.sum1,a.sum0+b.sum0,max(max(a.sum1,b.sum1),a.rlx1+b.llx1),max(max(a.sum0,b.sum0),a.rlx0+b.llx0),a.sum0?a.llx1:a.sum1+b.llx1,a.sum1?a.llx0:a.sum0+b.llx0,b.sum0?b.rlx1:b.sum1+a.rlx1,b.sum1?b.rlx0:b.sum0+a.rlx0};}
void upd(int p,int op){
    if(op==0)cov[p]=0,inv[p]=0,tr[p]={0,len[p],0,len[p],0,len[p],0,len[p]};
    if(op==1)cov[p]=1,inv[p]=0,tr[p]={len[p],0,len[p],0,len[p],0,len[p],0};
    if(op==2)inv[p]^=1,swap(tr[p].sum0,tr[p].sum1),swap(tr[p].lx1,tr[p].lx0),swap(tr[p].llx1,tr[p].llx0),swap(tr[p].rlx1,tr[p].rlx0);
}void push_down(int p){
    if(~cov[p])upd(pl,cov[p]),upd(pr,cov[p]);
    if(inv[p])upd(pl,2),upd(pr,2);
    cov[p]=-1,inv[p]=0;
}void update(int l,int r,int le,int ri,int op,int p){
    if(l>=le&&r<=ri)return upd(p,op);
    int mid=l+r>>1;push_down(p);
    if(le<=mid)update(l,mid,le,ri,op,pl);
    if(ri>mid)update(mid+1,r,le,ri,op,pr);
    tr[p]=merge(tr[pl],tr[pr]);
}Tree query(int l,int r,int le,int ri,int p){
    if(l>=le&&r<=ri)return tr[p];
    int mid=l+r>>1;Tree ret={0,0,0,0,0,0,0,0};
    if(le<=mid)ret=merge(ret,query(l,mid,le,ri,pl));
    if(ri>mid)ret=merge(ret,query(mid+1,r,le,ri,pr));
    return push_down(p),ret;
}void build(int l,int r,int p){
    cov[p]=-1,len[p]=r-l+1;
    if(l==r)return a[l]?tr[p]={1,0,1,0,1,0,1,0}:tr[p]={0,1,0,1,0,1,0,1},void();
    int mid=l+r>>1;
    build(l,mid,pl),build(mid+1,r,pr),tr[p]=merge(tr[pl],tr[pr]);
}int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(build(1,n,1);q--;){
        cin>>op>>l>>r;
        if(op<=2)update(1,n,l,r,op,1);
        else cout<<(op==3?query(1,n,l,r,1).sum1:query(1,n,l,r,1).lx1)<<'\n';
    }return 0;
}

by ZettaByte @ 2024-07-06 23:39:26

@Humour_Fh 你这马蜂谁帮你调啊（）

by mlvx @ 2024-07-06 23:40:10

@ZettaByte 不就是有点压行吗/kk

by mlvx @ 2024-07-07 08:33:51

query写错了/jk，但是还是错的/ll

#include<bits/stdc++.h>
using namespace std;
#define pl (p<<1)
#define pr (p<<1|1)
const int N=1e5+10;
struct Tree{int sum1,sum0,lx1,lx0,llx1,llx0,rlx1,rlx0;}tr[N<<2];
int n,q,op,l,r,a[N],len[N<<2],cov[N<<2],inv[N<<2];
Tree merge(Tree a,Tree b){return {a.sum1+b.sum1,a.sum0+b.sum0,max(max(a.sum1,b.sum1),a.rlx1+b.llx1),max(max(a.sum0,b.sum0),a.rlx0+b.llx0),a.sum0?a.llx1:a.sum1+b.llx1,a.sum1?a.llx0:a.sum0+b.llx0,b.sum0?b.rlx1:b.sum1+a.rlx1,b.sum1?b.rlx0:b.sum0+a.rlx0};}
void upd(int p,int op){
    if(op==0)cov[p]=0,inv[p]=0,tr[p]={0,len[p],0,len[p],0,len[p],0,len[p]};
    if(op==1)cov[p]=1,inv[p]=0,tr[p]={len[p],0,len[p],0,len[p],0,len[p],0};
    if(op==2)inv[p]^=1,swap(tr[p].sum0,tr[p].sum1),swap(tr[p].lx1,tr[p].lx0),swap(tr[p].llx1,tr[p].llx0),swap(tr[p].rlx1,tr[p].rlx0);
}void push_down(int p){
    if(~cov[p])upd(pl,cov[p]),upd(pr,cov[p]);
    if(inv[p])upd(pl,2),upd(pr,2);
    cov[p]=-1,inv[p]=0;
}void update(int l,int r,int le,int ri,int op,int p){
    if(l>=le&&r<=ri)return upd(p,op);
    int mid=l+r>>1;push_down(p);
    if(le<=mid)update(l,mid,le,ri,op,pl);
    if(ri>mid)update(mid+1,r,le,ri,op,pr);
    tr[p]=merge(tr[pl],tr[pr]);
}Tree query(int l,int r,int le,int ri,int p){
    if(l>ri||r<le)return{0,0,0,0,0,0,0,0};
    if(l>=le&&r<=ri)return tr[p];
    int mid=l+r>>1;
    return push_down(p),merge(query(l,mid,le,ri,pl),query(mid+1,r,le,ri,pr));
}void build(int l,int r,int p){
    cov[p]=-1,len[p]=r-l+1;
    if(l==r)return a[l]?tr[p]={1,0,1,0,1,0,1,0}:tr[p]={0,1,0,1,0,1,0,1},void();
    int mid=l+r>>1;
    build(l,mid,pl),build(mid+1,r,pr),tr[p]=merge(tr[pl],tr[pr]);
}int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(build(1,n,1);q--;){
        cin>>op>>l>>r;
        if(op<=2)update(1,n,l,r,op,1);
        else cout<<(op==3?query(1,n,l,r,1).sum1:query(1,n,l,r,1).lx1)<<'\n';
    }return 0;
}

by H3PO4 @ 2024-07-07 08:34:53

@Humour_Fh

lxhgww 最近收到了一个 01 序列，序列里面包含了 n 个数，下标从 0 开始。

by mlvx @ 2024-07-07 08:38:22

改了一下，只过Hack

#include<bits/stdc++.h>
using namespace std;
#define pl (p<<1)
#define pr (p<<1|1)
const int N=1e5+10;
struct Tree{int sum1,sum0,lx1,lx0,llx1,llx0,rlx1,rlx0;}tr[N<<2];
int n,q,op,l,r,a[N],len[N<<2],cov[N<<2],inv[N<<2];
Tree merge(Tree a,Tree b){return {a.sum1+b.sum1,a.sum0+b.sum0,max(max(a.sum1,b.sum1),a.rlx1+b.llx1),max(max(a.sum0,b.sum0),a.rlx0+b.llx0),a.sum0?a.llx1:a.sum1+b.llx1,a.sum1?a.llx0:a.sum0+b.llx0,b.sum0?b.rlx1:b.sum1+a.rlx1,b.sum1?b.rlx0:b.sum0+a.rlx0};}
void upd(int p,int op){
    if(op==0)cov[p]=0,inv[p]=0,tr[p]={0,len[p],0,len[p],0,len[p],0,len[p]};
    if(op==1)cov[p]=1,inv[p]=0,tr[p]={len[p],0,len[p],0,len[p],0,len[p],0};
    if(op==2)inv[p]^=1,swap(tr[p].sum0,tr[p].sum1),swap(tr[p].lx1,tr[p].lx0),swap(tr[p].llx1,tr[p].llx0),swap(tr[p].rlx1,tr[p].rlx0);
}void push_down(int p){
    if(~cov[p])upd(pl,cov[p]),upd(pr,cov[p]);
    if(inv[p])upd(pl,2),upd(pr,2);
    cov[p]=-1,inv[p]=0;
}void update(int l,int r,int le,int ri,int op,int p){
    if(l>=le&&r<=ri)return upd(p,op);
    int mid=l+r>>1;push_down(p);
    if(le<=mid)update(l,mid,le,ri,op,pl);
    if(ri>mid)update(mid+1,r,le,ri,op,pr);
    tr[p]=merge(tr[pl],tr[pr]);
}Tree query(int l,int r,int le,int ri,int p){
    if(l>ri||r<le)return{0,0,0,0,0,0,0,0};
    if(l>=le&&r<=ri)return tr[p];
    int mid=l+r>>1;
    return push_down(p),merge(query(l,mid,le,ri,pl),query(mid+1,r,le,ri,pr));
}void build(int l,int r,int p){
    cov[p]=-1,len[p]=r-l+1;
    if(l==r)return a[l]?tr[p]={1,0,1,0,1,0,1,0}:tr[p]={0,1,0,1,0,1,0,1},void();
    int mid=l+r>>1;
    build(l,mid,pl),build(mid+1,r,pr),tr[p]=merge(tr[pl],tr[pr]);
}int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(build(1,n,1);q--;){
        cin>>op>>l>>r,++l,++r;
        if(op<=2)update(1,n,l,r,op,1);
        else cout<<(op==3?query(1,n,l,r,1).sum1:query(1,n,l,r,1).lx1)<<'\n';
    }return 0;
}

by H3PO4 @ 2024-07-07 08:50:38

@Humour_Fh merge 有问题，第三、四项应该是 max(max(a.lx1,b.lx1),a.rlx1+b.llx1),max(max(a.lx0,b.lx0),a.rlx0+b.llx0)

by H3PO4 @ 2024-07-07 08:51:24

而不是 max(max(a.sum1,b.sum1),a.rlx1+b.llx1),max(max(a.sum0,b.sum0),a.rlx0+b.llx0)

by mlvx @ 2024-07-07 08:55:15

我傻了/kk