Hack数据过,讨论区的hack也都过了,但是还是0分,急,玄关

P2572 [SCOI2010] 序列操作

Lian_zy @ 2024-12-14 21:39:46

rt,找了好久错了,还是不知道错在哪

Subtask#1的一个点AC了

#include<bits/stdc++.h>
#define N 100005
using namespace std;

//区间变0/1 ->tag
//区间取反 ->puttag
//区间和 ->sum0/sum1
//区间最长连续1 ->ans0,ans1,rmx0,rmx1,lmx0,lmx1
struct node{
    int l,r;
    int sum0,sum1;
    int ans0,ans1,rmx0,rmx1,lmx0,lmx1;
    int tag,puttag;
}none,t[N<<2];
int n,m,x,y,z,a[N];
node push_up(node ans,node ls,node rs){
    ans.sum0=ls.sum0+rs.sum0;
    ans.sum1=ls.sum1+rs.sum1;
    //从左/右起最长的连续0/1 
    //left
    ans.lmx0=ls.lmx0+(ls.lmx0==ls.r-ls.l+1)*rs.lmx0;
    ans.lmx1=ls.lmx1+(ls.lmx1==ls.r-ls.l+1)*rs.lmx1;
    //right
    ans.rmx0=rs.rmx0+(rs.rmx0==rs.r-rs.l+1)*ls.rmx0;
    ans.rmx1=rs.rmx1+(rs.rmx1==rs.r-rs.l+1)*ls.rmx1;
    //获取ans 
    ans.ans0=max(max(ls.ans0,rs.ans0),ls.rmx0+rs.lmx0); 
    ans.ans1=max(max(ls.ans1,rs.ans1),ls.rmx1+rs.lmx1);
    return ans; 
}
void push_down(int x){
    //先赋值再取反
    if(~t[x].puttag){//处理区间赋值标记 
        if(t[x].puttag){//标记:区间赋1 
            t[x<<1].ans0=0;
            t[x<<1].lmx0=0;
            t[x<<1].rmx0=0;
            t[x<<1].sum0=0;
            t[x<<1].ans1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].lmx1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].rmx1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].sum1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1|1].ans0=0;
            t[x<<1|1].lmx0=0;
            t[x<<1|1].rmx0=0;
            t[x<<1|1].sum0=0;
            t[x<<1|1].ans1=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].lmx1=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].rmx1=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].sum1=t[x<<1|1].r-t[x<<1|1].l+1;
        }else{//区间赋0 
            t[x<<1].ans1=0;
            t[x<<1].lmx1=0;
            t[x<<1].rmx1=0;
            t[x<<1].sum1=0;
            t[x<<1].ans0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].lmx0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].rmx0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].sum0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1|1].ans1=0;
            t[x<<1|1].lmx1=0;
            t[x<<1|1].rmx1=0;
            t[x<<1|1].sum1=0;
            t[x<<1|1].ans0=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].lmx0=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].rmx0=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].sum0=t[x<<1|1].r-t[x<<1|1].l+1;
        }
        //下传
        //覆盖掉取反标记 
        t[x<<1].tag=0;
        t[x<<1|1].tag=0;
        //下传
        t[x<<1].puttag=t[x].puttag;
        t[x<<1|1].puttag=t[x].puttag;
        //标记清空
        t[x].puttag=-1; 
    }
    if(t[x].tag){//处理区间取反 
        //取反
        if(t[x].tag^t[x<<1].tag){
            swap(t[x<<1].ans0,t[x<<1].ans1);
            swap(t[x<<1].lmx0,t[x<<1].lmx1);
            swap(t[x<<1].rmx0,t[x<<1].rmx1);
            swap(t[x<<1].sum0,t[x<<1].sum1);
        }
        if(t[x].tag^t[x<<1|1].tag){
            swap(t[x<<1|1].ans0,t[x<<1|1].ans1);
            swap(t[x<<1|1].lmx0,t[x<<1|1].lmx1);
            swap(t[x<<1|1].rmx0,t[x<<1|1].rmx1);
            swap(t[x<<1|1].sum0,t[x<<1|1].sum1);
        }
        //下传
        t[x<<1].tag^=t[x].tag;
        t[x<<1|1].tag^=t[x].tag;
        //标记清空
        t[x].tag=0; 
    }
    return;
}
void build(int x,int l,int r){
    t[x].l=l;
    t[x].r=r;
    t[x].puttag=-1;
    if(l==r){
        if(a[l]){
            t[x].ans1=1;
            t[x].sum1=1;
            t[x].rmx1=1;
            t[x].lmx1=1;
        }else{
            t[x].ans0=1;
            t[x].sum0=1;
            t[x].rmx0=1;
            t[x].lmx0=1;
        }
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
    return;
}
void change(int x,int l,int r,int d){
    int L=t[x].l;
    int R=t[x].r;
    if(l<=L&&R<=r){
        t[x].puttag=d;
        t[x].tag=0;
        if(d){
            t[x].ans0=0;
            t[x].lmx0=0;
            t[x].rmx0=0;
            t[x].sum0=0;
            t[x].ans1=t[x].r-t[x].l+1;
            t[x].lmx1=t[x].r-t[x].l+1;
            t[x].rmx1=t[x].r-t[x].l+1;
            t[x].sum1=t[x].r-t[x].l+1;
        }else{
            t[x].ans1=0;
            t[x].lmx1=0;
            t[x].rmx1=0;
            t[x].sum1=0;
            t[x].ans0=t[x].r-t[x].l+1;
            t[x].lmx0=t[x].r-t[x].l+1;
            t[x].rmx0=t[x].r-t[x].l+1;
            t[x].sum0=t[x].r-t[x].l+1;
        }
        return;
    }
    push_down(x);
    int mid=L+R>>1;
    if(l<=mid)change(x<<1,l,r,d);
    if(r>mid)change(x<<1|1,l,r,d);
    t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
    return;
}
void update(int x,int l,int r){
    int L=t[x].l;
    int R=t[x].r;
    if(l<=L&&R<=r){
        t[x].tag^=1;
        swap(t[x].ans0,t[x].ans1);
        swap(t[x].lmx0,t[x].lmx1);
        swap(t[x].rmx0,t[x].rmx1);
        swap(t[x].sum0,t[x].sum1);
        return;
    }
    push_down(x);
    int mid=L+R>>1;
    if(l<=mid)update(x<<1,l,r);
    if(r>mid) update(x<<1|1,l,r);
    t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
    return;
}
node query(int x,int l,int r){
    int L=t[x].l;
    int R=t[x].r;
    if(l<=L&&R<=r)return t[x];
    push_down(x);
    node left=none;
    node right=none;
    bool lf=0,rt=0;
    int mid=L+R>>1;
    if(l<=mid)left=query(x<<1,l,r),lf=1;
    if(r>mid) right=query(x<<1|1,l,r),rt=1;
    if(lf&&rt)return push_up(none,left,right);
    if(lf)return left;
    return right;
}
void print_tree(int x){
    int L=t[x].l;
    int R=t[x].r;
    cout<<x<<' '<<L<<' '<<R<<endl;
    cout<<"ans "<<t[x].ans0<<' '<<t[x].ans1<<endl;
    cout<<"sum "<<t[x].sum0<<' '<<t[x].sum1<<endl;
    cout<<"lmx "<<t[x].lmx0<<' '<<t[x].lmx1<<endl;
    cout<<"rmx "<<t[x].rmx0<<' '<<t[x].rmx1<<endl;
    if(L==R)return;
    cout<<"ls "<<x*2<<' '<<"rs"<<x*2+1<<endl;
    print_tree(x<<1);
    print_tree(x<<1|1);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,1,n);
    //print_tree(1);
    while(m--){
        scanf("%d%d%d",&x,&y,&z);
        y++;
        z++;
        if(x==0)change(1,y,z,0);
        if(x==1)change(1,y,z,1);
        if(x==2)update(1,y,z);
        if(x==3)printf("%d\n",query(1,y,z).sum1);
        if(x==4)printf("%d\n",query(1,y,z).ans1);
        //puts("NOWTREE");
        //print_tree(1);
    }
    return 0;
} 

by AK47N @ 2024-12-14 21:54:07

@Lian_lele

#include<bits/stdc++.h>
using namespace std;
int n,q,a[100001];
struct d{
    int w,b,lw,lb,rw,rb,mw,mb;
    d(int w=0,int b=0,int lw=0,int lb=0,int rw=0,int rb=0,int mw=0,int mb=0):
    w(w),b(b),lw(lw),lb(lb),rw(rw),rb(rb),mw(mw),mb(mb){}
};
inline d hb(d i,d j){
    return d(
    i.w+j.w, i.b+j.b,
    (i.b?i.lw:i.w+j.lw), (i.w?i.lb:i.b+j.lb),
    (j.b?j.rw:j.w+i.rw), (j.w?j.rb:j.b+i.rb),
    max(max(i.mw,j.mw),i.rw+j.lw),
    max(max(i.mb,j.mb),i.rb+j.lb));
}
d dat[262144]; int len[262144],tg1[262144],tg2[262144];
inline void P(int i,int typ){
    d&t=dat[i];
    if(typ==0) tg2[i]= 0, tg1[i]=0, t=d(0,len[i],0,len[i],0,len[i],0,len[i]);
    if(typ==1) tg2[i]= 0, tg1[i]=1, t=d(len[i],0,len[i],0,len[i],0,len[i],0);
    if(typ==2) tg2[i]^=1, swap(t.w,t.b), swap(t.lw,t.lb), swap(t.rw,t.rb), swap(t.mw,t.mb);
}
inline void pd(int i){
    if(~tg1[i]) P(i<<1,tg1[i]), P(i<<1|1,tg1[i]);
    if(tg2[i]) P(i<<1,2), P(i<<1|1,2);
    tg1[i]=-1, tg2[i]=0;
}
void build(int i,int l,int r){
    len[i]=r-l+1; tg1[i]=-1;
    if(l==r) {int t=a[l]; dat[i]=d(t,t^1,t,t^1,t,t^1,t,t^1); return;}
    build(i<<1,l,l+r>>1);
    build(i<<1|1,(l+r>>1)+1,r);
    dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
void Mdf(int i,int l,int r,int a,int b,int t){
    if(b<l||r<a) return; if(a<=l&&r<=b) {P(i,t); return;}
    pd(i); Mdf(i<<1,l,l+r>>1,a,b,t), Mdf(i<<1|1,(l+r>>1)+1,r,a,b,t);
    dat[i]=hb(dat[i<<1],dat[i<<1|1]);
}
d Qur(int i,int l,int r,int a,int b){
    if(b<l||r<a) return d(); if(a<=l&&r<=b) return dat[i];
    pd(i); return hb(Qur(i<<1,l,l+r>>1,a,b),Qur(i<<1|1,(l+r>>1)+1,r,a,b));
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i) scanf("%d",a+i);
    build(1,1,n);
    for(int i=1;i<=q;++i){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r); ++l, ++r;
        if(opt<3) Mdf(1,1,n,l,r,opt);
        else {d t=Qur(1,1,n,l,r); printf("%d\n",opt==3?t.w:t.mw);}
    }
    return 0;
}

by Lian_zy @ 2024-12-14 21:57:44

@AK47N 谢谢,但是能不能帮忙调下代码啊

这是第一篇题解吧


by Liuhy2996 @ 2024-12-14 22:51:59

@Lian_lele 把81行和87行的if去掉试试


by Liuhy2996 @ 2024-12-14 22:55:55

@Lian_lele

#include<bits/stdc++.h>
#define N 100005
using namespace std;

//区间变0/1 ->tag
//区间取反 ->puttag
//区间和 ->sum0/sum1
//区间最长连续1 ->ans0,ans1,rmx0,rmx1,lmx0,lmx1
struct node{
    int l,r;
    int sum0,sum1;
    int ans0,ans1,rmx0,rmx1,lmx0,lmx1;
    int tag,puttag;
}none,t[N<<2];
int n,m,x,y,z,a[N];
node push_up(node ans,node ls,node rs){
    ans.sum0=ls.sum0+rs.sum0;
    ans.sum1=ls.sum1+rs.sum1;
    //从左/右起最长的连续0/1 
    //left
    ans.lmx0=ls.lmx0+(ls.lmx0==ls.r-ls.l+1)*rs.lmx0;
    ans.lmx1=ls.lmx1+(ls.lmx1==ls.r-ls.l+1)*rs.lmx1;
    //right
    ans.rmx0=rs.rmx0+(rs.rmx0==rs.r-rs.l+1)*ls.rmx0;
    ans.rmx1=rs.rmx1+(rs.rmx1==rs.r-rs.l+1)*ls.rmx1;
    //获取ans 
    ans.ans0=max(max(ls.ans0,rs.ans0),ls.rmx0+rs.lmx0); 
    ans.ans1=max(max(ls.ans1,rs.ans1),ls.rmx1+rs.lmx1);
    return ans; 
}
void push_down(int x){
    //先赋值再取反
    if(~t[x].puttag){//处理区间赋值标记 
        if(t[x].puttag){//标记:区间赋1 
            t[x<<1].ans0=0;
            t[x<<1].lmx0=0;
            t[x<<1].rmx0=0;
            t[x<<1].sum0=0;
            t[x<<1].ans1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].lmx1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].rmx1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].sum1=t[x<<1].r-t[x<<1].l+1;
            t[x<<1|1].ans0=0;
            t[x<<1|1].lmx0=0;
            t[x<<1|1].rmx0=0;
            t[x<<1|1].sum0=0;
            t[x<<1|1].ans1=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].lmx1=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].rmx1=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].sum1=t[x<<1|1].r-t[x<<1|1].l+1;
        }else{//区间赋0 
            t[x<<1].ans1=0;
            t[x<<1].lmx1=0;
            t[x<<1].rmx1=0;
            t[x<<1].sum1=0;
            t[x<<1].ans0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].lmx0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].rmx0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1].sum0=t[x<<1].r-t[x<<1].l+1;
            t[x<<1|1].ans1=0;
            t[x<<1|1].lmx1=0;
            t[x<<1|1].rmx1=0;
            t[x<<1|1].sum1=0;
            t[x<<1|1].ans0=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].lmx0=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].rmx0=t[x<<1|1].r-t[x<<1|1].l+1;
            t[x<<1|1].sum0=t[x<<1|1].r-t[x<<1|1].l+1;
        }
        //下传
        //覆盖掉取反标记 
        t[x<<1].tag=0;
        t[x<<1|1].tag=0;
        //下传
        t[x<<1].puttag=t[x].puttag;
        t[x<<1|1].puttag=t[x].puttag;
        //标记清空
        t[x].puttag=-1; 
    }
    if(t[x].tag){//处理区间取反 
        //取反
        //if(t[x].tag^t[x<<1].tag){
            swap(t[x<<1].ans0,t[x<<1].ans1);
            swap(t[x<<1].lmx0,t[x<<1].lmx1);
            swap(t[x<<1].rmx0,t[x<<1].rmx1);
            swap(t[x<<1].sum0,t[x<<1].sum1);
        //}
        //if(t[x].tag^t[x<<1|1].tag){
            swap(t[x<<1|1].ans0,t[x<<1|1].ans1);
            swap(t[x<<1|1].lmx0,t[x<<1|1].lmx1);
            swap(t[x<<1|1].rmx0,t[x<<1|1].rmx1);
            swap(t[x<<1|1].sum0,t[x<<1|1].sum1);
        //}
        //下传
        t[x<<1].tag^=t[x].tag;
        t[x<<1|1].tag^=t[x].tag;
        //标记清空
        t[x].tag=0; 
    }
    return;
}
void build(int x,int l,int r){
    t[x].l=l;
    t[x].r=r;
    t[x].puttag=-1;
    if(l==r){
        if(a[l]){
            t[x].ans1=1;
            t[x].sum1=1;
            t[x].rmx1=1;
            t[x].lmx1=1;
        }else{
            t[x].ans0=1;
            t[x].sum0=1;
            t[x].rmx0=1;
            t[x].lmx0=1;
        }
        return;
    }
    int mid=l+r>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
    return;
}
void change(int x,int l,int r,int d){
    int L=t[x].l;
    int R=t[x].r;
    if(l<=L&&R<=r){
        t[x].puttag=d;
        t[x].tag=0;
        if(d){
            t[x].ans0=0;
            t[x].lmx0=0;
            t[x].rmx0=0;
            t[x].sum0=0;
            t[x].ans1=t[x].r-t[x].l+1;
            t[x].lmx1=t[x].r-t[x].l+1;
            t[x].rmx1=t[x].r-t[x].l+1;
            t[x].sum1=t[x].r-t[x].l+1;
        }else{
            t[x].ans1=0;
            t[x].lmx1=0;
            t[x].rmx1=0;
            t[x].sum1=0;
            t[x].ans0=t[x].r-t[x].l+1;
            t[x].lmx0=t[x].r-t[x].l+1;
            t[x].rmx0=t[x].r-t[x].l+1;
            t[x].sum0=t[x].r-t[x].l+1;
        }
        return;
    }
    push_down(x);
    int mid=L+R>>1;
    if(l<=mid)change(x<<1,l,r,d);
    if(r>mid)change(x<<1|1,l,r,d);
    t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
    return;
}
void update(int x,int l,int r){
    int L=t[x].l;
    int R=t[x].r;
    if(l<=L&&R<=r){
        t[x].tag^=1;
        swap(t[x].ans0,t[x].ans1);
        swap(t[x].lmx0,t[x].lmx1);
        swap(t[x].rmx0,t[x].rmx1);
        swap(t[x].sum0,t[x].sum1);
        return;
    }
    push_down(x);
    int mid=L+R>>1;
    if(l<=mid)update(x<<1,l,r);
    if(r>mid) update(x<<1|1,l,r);
    t[x]=push_up(t[x],t[x<<1],t[x<<1|1]);
    return;
}
node query(int x,int l,int r){
    int L=t[x].l;
    int R=t[x].r;
    if(l<=L&&R<=r)return t[x];
    push_down(x);
    node left=none;
    node right=none;
    bool lf=0,rt=0;
    int mid=L+R>>1;
    if(l<=mid)left=query(x<<1,l,r),lf=1;
    if(r>mid) right=query(x<<1|1,l,r),rt=1;
    if(lf&&rt)return push_up(none,left,right);
    if(lf)return left;
    return right;
}
void print_tree(int x){
    int L=t[x].l;
    int R=t[x].r;
    cout<<x<<' '<<L<<' '<<R<<endl;
    cout<<"ans "<<t[x].ans0<<' '<<t[x].ans1<<endl;
    cout<<"sum "<<t[x].sum0<<' '<<t[x].sum1<<endl;
    cout<<"lmx "<<t[x].lmx0<<' '<<t[x].lmx1<<endl;
    cout<<"rmx "<<t[x].rmx0<<' '<<t[x].rmx1<<endl;
    if(L==R)return;
    cout<<"ls "<<x*2<<' '<<"rs"<<x*2+1<<endl;
    print_tree(x<<1);
    print_tree(x<<1|1);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    build(1,1,n);
    //print_tree(1);
    while(m--){
        scanf("%d%d%d",&x,&y,&z);
        y++;
        z++;
        if(x==0)change(1,y,z,0);
        if(x==1)change(1,y,z,1);
        if(x==2)update(1,y,z);
        if(x==3)printf("%d\n",query(1,y,z).sum1);
        if(x==4)printf("%d\n",query(1,y,z).ans1);
        //puts("NOWTREE");
        //print_tree(1);
    }
    return 0;
}

by Lian_zy @ 2024-12-14 23:06:55

@Liuhy2996 A了,谢谢你,关注啦


|