全WA求hack

Reee1e @ 2020-10-28 13:44:01

#include<cstdio>

#include<cstring>

using namespace std;

#define re register int

#define lc (p<<1)

#define rc (p<<1|1)

const int N=1e5+10;

int a[N];

inline int read(){

    re x=0;register char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar());

    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);

    return x;

}

struct lineTree{

    int tag[N<<2],left0[N<<2],right0[N<<2],

        left1[N<<2],right1[N<<2],sum0[N<<2],sum1[N<<2],

        tot0[N<<2],tot1[N<<2];

    inline void swap(re &x,re &y){re t=x;x=y;y=t;}

    inline int min(re x,re y){return x<y?x:y;}

    inline int min(re x,re y,re z){x=min(x,y);return min(x,z);}

    inline int max(re x,re y){return x>y?x:y;}

    inline int max(re x,re y,re z){x=max(x,y);return max(x,z);}

    lineTree(){

        memset(tag,-1,sizeof(tag));

        memset(left0,0,sizeof(left0));

        memset(right0,0,sizeof(right0));

        memset(left1,0,sizeof(left1));

        memset(right1,0,sizeof(right1));

        memset(tot0,0,sizeof(tot0));

by Reee1e @ 2020-10-28 13:45:46

代码没发全，这段才是

#include<cstdio>
#include<cstring>
using namespace std;
#define re register int
#define lc (p<<1)
#define rc (p<<1|1)
const int N=1e5+10;

int a[N];

inline int read(){
    re x=0;register char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return x;
}

struct lineTree{
    int tag[N<<2],left0[N<<2],right0[N<<2],
        left1[N<<2],right1[N<<2],sum0[N<<2],sum1[N<<2],
        tot0[N<<2],tot1[N<<2];
    inline void swap(re &x,re &y){re t=x;x=y;y=t;}
    inline int min(re x,re y){return x<y?x:y;}
    inline int min(re x,re y,re z){x=min(x,y);return min(x,z);}
    inline int max(re x,re y){return x>y?x:y;}
    inline int max(re x,re y,re z){x=max(x,y);return max(x,z);}
    lineTree(){
        memset(tag,-1,sizeof(tag));
        memset(left0,0,sizeof(left0));
        memset(right0,0,sizeof(right0));
        memset(left1,0,sizeof(left1));
        memset(right1,0,sizeof(right1));
        memset(tot0,0,sizeof(tot0));
        memset(tot1,0,sizeof(tot1));
    }
    inline void pushdown(re l,re r,re p){
        //printf("pushdown(%d,%d,%d)\n",l,r,p);
        re mid=(l+r)>>1;
        if(tag[p]==0){
            tot0[lc]=sum0[lc]=left0[lc]=right0[lc]=mid-l+1;
            tot0[rc]=sum0[rc]=left0[rc]=right0[rc]=r-mid;
            tot1[lc]=sum1[lc]=left1[lc]=right1[lc]=0;
            tot1[rc]=sum1[rc]=left1[rc]=right1[rc]=0;
            tag[lc]=tag[rc]=tag[p];
            tag[p]=-1;
        }
        if(tag[p]==1){
            tot1[lc]=sum1[lc]=left1[lc]=right1[lc]=mid-l+1;
            tot1[rc]=sum1[rc]=left1[rc]=right1[rc]=r-mid;
            tot0[lc]=sum0[lc]=left0[lc]=right0[lc]=0;
            tot0[rc]=sum0[rc]=left0[rc]=right0[rc]=0;
            tag[lc]=tag[rc]=tag[p];
            tag[p]=-1;
        }
        if(tag[p]==2){
            swap(tot0[lc],tot1[lc]);
            swap(tot0[rc],tot1[rc]);
            swap(sum0[lc],sum1[lc]);
            swap(sum0[rc],sum1[rc]);
            swap(left0[lc],left1[lc]);
            swap(right0[lc],right1[lc]);
            swap(left0[rc],left1[rc]);
            swap(right0[rc],right1[rc]);
            //printf("\tlc:tot0=%d,tot1=%d\n",tot0[lc],tot1[lc]);
            //printf("\trc:tot0=%d,tot1=%d\n",tot0[rc],tot1[rc]);
            if(tag[lc]==2)tag[lc]=-1;
            else if(tag[lc]!=-1)tag[lc]^=1;
            if(tag[lc]==-1)tag[lc]=2;

            if(tag[rc]==2)tag[rc]=-1;
            else if(tag[rc]!=-1)tag[rc]^=1;
            if(tag[rc]==-1)tag[rc]=2;

            tag[p]=-1;
        }
    }
    inline void pushup(re l,re r,re p){
        re mid=(l+r)>>1;
        re tmp0=right0[lc]+left0[rc];
        re tmp1=right1[lc]+left1[rc];
        sum0[p]=max(sum0[lc],sum0[rc],tmp0);
        sum1[p]=max(sum1[lc],sum1[rc],tmp1);
        //printf("pushup(%d,%d,%d)\n",l,r,p);
        //printf("\t%d %d\n",sum0[p],sum1[p]);
        tot0[p]=tot0[lc]+tot0[rc];
        tot1[p]=tot1[lc]+tot1[rc];
        // if(left0[rc]==mid-l+1)
        //     left0[p]=left0[lc]+left0[rc];
        // if(left1[rc]==mid-l+1)
        //     left1[p]=left1[lc]+left1[rc];
        // if(right0[lc]==r-mid)
        //     right0[p]=right0[lc]+right0[rc];
        // if(right1[lc]==r-mid)
        //     right1[p]=right1[lc]+right1[rc];
        //printf("\tl0=%d r0=%d l1=%d r1=%d\n",left0[p],right0[p],left1[p],right1[p]);
        if(tot0[lc]==mid-l+1)left0[p]=tot0[lc]+left0[rc];
        else left0[p]=left0[lc];
        if(tot1[lc]==mid-l+1)left1[p]=tot1[lc]+left1[rc];
        else left1[p]=left1[lc];
        if(tot0[rc]==r-mid)right0[p]=tot0[rc]+right0[lc];
        else right0[p]=right0[rc];
        if(tot1[rc]==r-mid)right1[p]=tot1[rc]+right1[lc];
        else right1[p]=right1[rc];
        //printf("\tl0=%d r0=%d l1=%d r1=%d\n",left0[p],right0[p],left1[p],right1[p]);
        // sum0[p]=max(sum0[p],left0[p],right0[p]);
        // sum1[p]=max(sum1[p],left1[p],right1[p]);
    }
    void build(re l,re r,re p){
        if(l==r){
            if(a[l])
                tot1[p]=left1[p]=right1[p]=sum1[p]=1;
            else 
                tot0[p]=left0[p]=right0[p]=sum0[p]=1;
            return;
        }
        re mid=(l+r)>>1;
        build(l,mid,lc);
        build(mid+1,r,rc);
        pushup(l,r,p);
    }
    void set0(re x,re y,re l,re r,re p){
        if(x<=l&&y>=r){
            tot0[p]=sum0[p]=left0[p]=right0[p]=r-l+1;
            tot1[p]=sum1[p]=left1[p]=right1[p]=0;
            tag[p]=0;
            return;
        }
        pushdown(l,r,p);
        re mid=(l+r)>>1;
        if(x<=mid)set0(x,y,l,mid,lc);
        if(y>mid)set0(x,y,mid+1,r,rc);
        pushup(l,r,p);
    }
    void set1(re x,re y,re l,re r,re p){
        if(x<=l&&y>=r){
            tot1[p]=sum1[p]=left1[p]=right1[p]=r-l+1;
            tot0[p]=sum0[p]=left0[p]=right0[p]=0;
            tag[p]=1;
            return;
        }
        pushdown(l,r,p);
        re mid=(l+r)>>1;
        if(x<=mid)set1(x,y,l,mid,lc);
        if(y>mid)set1(x,y,mid+1,r,rc);
        pushup(l,r,p);
    }
    void rev(re x,re y,re l,re r,re p){
        if(x<=l&&y>=r){
            swap(left0[p],left1[p]);
            swap(right0[p],right1[p]);
            swap(sum0[p],sum1[p]);
            swap(tot0[p],tot1[p]);
            if(tag[p]==2)tag[p]=-1;
            else if(tag[p]>-1)tag[p]^=1;
            if(tag[p]==-1)tag[p]=2;
            return;
        }
        pushdown(l,r,p);
        re mid=(l+r)>>1;
        if(x<=mid)rev(x,y,l,mid,lc);
        if(y>mid)rev(x,y,mid+1,r,rc);
        pushup(l,r,p);
    }
    inline int count1(re x,re y,re l,re r,re p){
        if(x<=l&&y>=r){
            return tot1[p];
        }
        pushdown(l,r,p);
        re mid=(l+r)>>1,ans=0;
        if(x<=mid)ans+=count1(x,y,l,mid,lc);
        if(y>mid)ans+=count1(x,y,mid+1,r,rc);
        return ans;
    }
    inline int countl1(re x,re y,re l,re r,re p){
        if(x<=l&&y>=r){
            // printf("countl1(%d,%d,%d,%d,%d)\n",x,y,l,r,p);
            // printf("\tdirect reurned %d\n",sum1[p]);
            return sum1[p];
        }
        pushdown(l,r,p);
        re ans=0;
        re mid=(l+r)>>1;
        if(x<=mid)ans=max(ans,countl1(x,y,l,mid,lc));
        if(y>mid)ans=max(ans,countl1(x,y,mid+1,r,rc));
        // printf("countl1(%d,%d,%d,%d,%d)\n",x,y,l,r,p);
        if(x<=mid&&y>mid)ans=max(min(mid-x+1,right1[lc])+min(y-mid,left1[rc]),ans);
        // printf("\treturned %d\n",ans);
        return ans;
    }
}lt;

int main(){
    re n=read(),m=read();
    for(re i=1;i<=n;i++){
        a[i]=read();
    }
    lt.build(1,n,1);
    while(m--){
        fflush(stdin),fflush(stdout);
        re o=read(),l=read()+1,r=read()+1;
        //记得加一
        if(o==0)lt.set0(l,r,1,n,1);
        if(o==1)lt.set1(l,r,1,n,1);
        if(o==2)lt.rev(l,r,1,n,1);
        if(o==3)printf("%d\n",lt.count1(l,r,1,n,1));
        if(o==4)printf("%d\n",lt.countl1(l,r,1,n,1));
    }
    return 0;
}

by zimujun @ 2020-10-28 14:22:38

@Riddle233 我这边吧给你对拍的时候直接卡住了

by L_C_T @ 2020-10-28 14:29:51

为什么要hack