hick过了,其它没过,求助(悬赏关注)

P2572 [SCOI2010] 序列操作

Langke_Saonian @ 2024-07-23 12:32:34

无语了,hick过了其它没过,求助(悬赏关注)

#include<bits/stdc++.h>
using namespace std;
const int N=200020;
int n,m,a[N];
int max(int a,int b){return a>b?a:b;}
struct Tree{
    int add,rev,l,r;
    int num1,amax1,lmax1,rmax1;
    int num0,amax0,lmax0,rmax0;
}e[N<<2];
// definitions and comments
    #define lid id<<1
    #define rid id<<1|1
    #define l(u) e[u].l
    #define r(u) e[u].r
    #define rev(u) e[u].rev
    #define add(u) e[u].add
    #define num1(u) e[u].num1
    #define num0(u) e[u].num0
    #define lmax1(u) e[u].lmax1
    #define lmax0(u) e[u].lmax0
    #define rmax1(u) e[u].rmax1
    #define rmax0(u) e[u].rmax0
    #define amax1(u) e[u].amax1
    #define amax0(u) e[u].amax0
    //rev 标记是否翻转 
    //num1(the number of 1)
    //num0(the number of 0)
    //amax1(all max of 1)
    //amax0(all max of 0)
    //lmax1(left max of 1)
    //lmax0(left max of 0)
    //rmax1(right max of 1)
    //rmax0(right max of 0)
    /*
    add
    -1: do nothing
    0: all of number become 0
    1: all of number become 1
    */
inline void push_up(int id){
//cout<<"a";
    {//the change of 1
        num1(id)=num1(lid)+num1(rid);
        lmax1(id)=lmax1(lid);
        if(num1(lid)==r(lid)-l(lid)+1) lmax1(id)+=lmax1(rid);
        rmax1(id)=rmax1(rid);
        if(num1(rid)==r(rid)-l(rid)+1) rmax1(id)+=rmax1(lid);
        amax1(id)=lmax1(rid)+rmax1(lid);
        amax1(id)=max(amax1(id),amax1(lid));
        amax1(id)=max(amax1(id),amax1(rid));
    }
    {//the change of 0
        num0(id)=num0(lid)+num0(rid);
        lmax0(id)=lmax0(lid);
        if(num0(lid)==r(lid)-l(lid)+1) lmax0(id)+=lmax0(rid);
        rmax0(id)=rmax0(rid);
        if(num0(rid)==r(rid)-l(rid)+1) rmax0(id)+=rmax0(lid);
        amax0(id)=lmax0(rid)+rmax0(lid);
        amax0(id)=max(amax0(id),amax0(lid));
        amax0(id)=max(amax0(id),amax0(rid));
    }
    return;
}
inline void build(int id,int l,int r){
    l(id)=l,r(id)=r,add(id)=-1;
    if(l==r){
        num0(id)=lmax0(id)=rmax0(id)=amax0(id)=a[l]==0;
        num1(id)=lmax1(id)=rmax1(id)=amax1(id)=a[l]==1;
        return;
    }
    int mid=l+r>>1;
    build(lid,l,mid),build(rid,mid+1,r);
    push_up(id);
}
inline void push_down(int id){
//cout<<"b";
    if(add(id)!=-1){
        rev(id)=0;
        if(add(id)==0){
            {//the change of lid
                add(lid)=0,rev(lid)=0;
                num1(lid)=amax1(lid)=lmax1(lid)=rmax1(lid)=0;
                num0(lid)=amax0(lid)=lmax0(lid)=rmax0(lid)=(r(lid)-l(lid)+1);
            }
            {//the change of rid 
                add(rid)=0,rev(rid)=0;
                num1(rid)=amax1(rid)=lmax1(rid)=rmax1(rid)=0;
                num0(rid)=amax0(rid)=lmax0(rid)=rmax0(rid)=(r(rid)-l(rid)+1);
            }
            add(id)=-1;
            return;
        }
        if(add(id)==1){
            {//the change of lid
                add(lid)=1,rev(lid)=0;
                num0(lid)=amax0(lid)=lmax0(lid)=rmax0(lid)=0;
                num1(lid)=amax1(lid)=lmax1(lid)=rmax1(lid)=(r(lid)-l(lid)+1);
            }
            {//the change of rid 
                add(rid)=1,rev(rid)=0;
                num0(rid)=amax0(rid)=lmax0(rid)=rmax0(rid)=0;
                num1(rid)=amax1(rid)=lmax1(rid)=rmax1(rid)=(r(rid)-l(rid)+1);
            }
            add(id)=-1;
            return;
        }
    }
    if(rev(id)){
        swap(num1(lid),num0(lid));
        swap(num1(rid),num0(rid));
        if(add(lid)!=-1) add(lid)^=1;
        else rev(lid)^=1;
        if(add(rid)!=-1) add(rid)^=1;
        else rev(add(rid))^=1;
        swap(amax1(lid),amax0(lid));
        swap(lmax1(lid),lmax0(lid));
        swap(rmax1(lid),rmax0(lid));
        swap(amax1(rid),amax0(rid));
        swap(lmax1(rid),lmax0(rid));
        swap(rmax1(rid),rmax0(rid));
        rev(id)=0;
        return; 
    }
    return;
}
inline void modify(int id,int x,int y,int q){
    push_down(id);
    if(x==l(id)&&r(id)==y){
        if(q==0){
            add(id)=0;
            num1(id)=amax1(id)=lmax1(id)=rmax1(id)=0;
            num0(id)=amax0(id)=lmax0(id)=rmax0(id)=(r(id)-l(id)+1);
            return;
        }
        if(q==1){
            add(id)=1;
            num0(id)=amax0(id)=lmax0(id)=rmax0(id)=0;
            num1(id)=amax1(id)=lmax1(id)=rmax1(id)=(r(id)-l(id)+1);
            return;
        }
        if(q==2){
            rev(id)^=1; 
            swap(num1(id),num0(id));
            swap(amax1(id),amax0(id));
            swap(lmax1(id),lmax0(id));
            swap(rmax1(id),rmax0(id));
            return;
        }
    }
    int mid=l(id)+r(id)>>1;
    if(mid<x) modify(rid,x,y,q);
    else if(mid>=y) modify(lid,x,y,q);
    else modify(lid,x,mid,q),modify(rid,mid+1,y,q);
    push_up(id);
    return;
}
inline int query1(int id,int x,int y){
    push_down(id);
    if(x==l(id)&&r(id)==y) return num1(id);
    int mid=l(id)+r(id)>>1;
    if(mid<x) return query1(rid,x,y);
    else if(mid>=y) return query1(lid,x,y);
    return query1(lid,x,mid)+query1(rid,mid+1,y);
}
inline Tree query2(int id,int x,int y){
    push_down(id);
    if(x==l(id)&&r(id)==y) return e[id];
    int mid=l(id)+r(id)>>1;
    if(mid<x) return query2(rid,x,y);
    else if(mid>=y) return query2(lid,x,y);
    else{
        Tree ret,L=query2(lid,x,mid),R=query2(rid,mid+1,y);
        ret.num1=L.num1+R.num1;
        ret.num0=L.num0+R.num0;
        ret.lmax1=L.lmax1;
        if(L.num1==L.r-L.l+1){
            ret.lmax1+=R.lmax1;
        }
        ret.lmax0=L.lmax0;
        if(L.num0==L.r-L.l+1){
            ret.lmax0+=R.lmax0;
        }
        ret.rmax1=R.rmax1;
        if(R.num1==R.r-R.l+1){
            ret.rmax1+=L.rmax1;
        }
        ret.rmax0=R.rmax0;
        if(R.num0==R.r-R.l+1){
            ret.rmax0+=L.rmax0;
        }
        ret.amax1=R.lmax1+L.rmax1;
        ret.amax1=max(ret.amax1,L.amax1);
        ret.amax1=max(ret.amax1,R.amax1);
        ret.amax0=R.lmax0+L.rmax0;
        ret.amax0=max(ret.amax0,L.amax0);
        ret.amax0=max(ret.amax0,R.amax0);
        return ret;
    }
} 
int main(){
    scanf("%d%d",&n,&m);
//  int dep=log2(n);
//  dep=pow(2,dep+1);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        int x,y,op;
        scanf("%d%d%d",&op,&x,&y);
        x++;y++;
        if(op==0||op==1||op==2){
            modify(1,x,y,op);
        }else if(op==3){
            printf("%d\n",query1(1,x,y));
        }else if(op==4){
            printf("%d\n",query2(1,x,y).amax1);
        }
    }
    return 0;
}

by Langke_Saonian @ 2024-07-23 15:21:46

破案了


by Langke_Saonian @ 2024-07-23 15:25:55

我在113行 push_down 时写错了

应是rev(rid)^=1;

ps:我说前几天我图灵验证怎么没过,原来我是人机

by Langke_Saonian @ 2024-07-23 15:26:27

结帖


|