能过样例,全WA求助

P2572 [SCOI2010] 序列操作

云浅知处 @ 2020-08-18 12:00:12

对拍了八十多组数据了=_=,还是没发现错误。

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>

#define MAXN 200005
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)

using namespace std;

int a[MAXN],n,m;
struct Node{
    int sum,len;
    int l,r;
    int lz,re;
    int lmax[2],rmax[2],max[2];
};

struct SMT{

    Node d[MAXN<<2];

    inline void pushup(int o){
        d[o].sum=d[lson(o)].sum+d[rson(o)].sum;
        d[o].len=d[lson(o)].len+d[rson(o)].len;
        for(int i=0;i<=1;i++){
            d[o].lmax[i]=d[lson(o)].lmax[i];
            if(i==0&&d[lson(o)].sum==0){
                d[o].lmax[i]+=d[rson(o)].lmax[i];
            }
            else if(i==1&&d[lson(o)].sum==d[lson(o)].r-d[lson(o)].l+1){
                d[o].lmax[i]+=d[rson(o)].lmax[i];
            }
            d[o].rmax[i]=d[rson(o)].rmax[i];
            if(i==0&&d[rson(o)].sum==0){
                d[o].rmax[i]+=d[lson(o)].rmax[i];
            }
            else if(i==1&&d[rson(o)].sum==d[rson(o)].r-d[rson(o)].l+1){
                d[o].rmax[i]+=d[lson(o)].rmax[i];
            }
            d[o].max[i]=d[lson(o)].rmax[i]+d[rson(o)].lmax[i];
            d[o].max[i]=max(d[lson(o)].max[i],d[o].max[i]);
            d[o].max[i]=max(d[rson(o)].max[i],d[o].max[i]);
        }
    }

    inline void build(int l,int r,int o){
        d[o].lz=-1;
        d[o].re=0;
        d[o].l=l;
        d[o].r=r;
        d[o].len=r-l+1;
        if(l==r){
            d[o].sum=a[l];
            d[o].lmax[1]=d[o].rmax[1]=d[o].max[1]=(a[l]==1);
            d[o].lmax[0]=d[o].rmax[0]=d[o].max[0]=(a[l]==0);
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,lson(o));
        build(mid+1,r,rson(o));
        pushup(o);
    }

    inline void pushdown(int o){
        if(d[o].lz!=-1){
            d[o].re=0;
            int val=d[o].lz;

            d[lson(o)].sum=(d[lson(o)].r-d[lson(o)].l+1)*val;
            d[rson(o)].sum=(d[rson(o)].r-d[rson(o)].l+1)*val;

            d[lson(o)].lz=d[rson(o)].lz=val;
            d[lson(o)].re=d[rson(o)].re=0;

            d[lson(o)].max[val]=d[lson(o)].lmax[val]=d[lson(o)].rmax[val]=d[lson(o)].r-d[lson(o)].l+1;
            d[rson(o)].max[val]=d[rson(o)].lmax[val]=d[rson(o)].rmax[val]=d[rson(o)].r-d[rson(o)].l+1;

            d[lson(o)].max[val^1]=d[lson(o)].lmax[val^1]=d[lson(o)].rmax[val^1]=0;
            d[rson(o)].max[val^1]=d[rson(o)].lmax[val^1]=d[rson(o)].rmax[val^1]=0;

            d[o].lz=-1;
        }
        if(d[o].re){
            d[lson(o)].sum=(d[lson(o)].r-d[lson(o)].l+1)-d[lson(o)].sum;
            d[rson(o)].sum=(d[rson(o)].r-d[rson(o)].l+1)-d[rson(o)].sum;

            if(d[lson(o)].lz!=-1)d[lson(o)].lz^=1;
            else d[lson(o)].re^=1;
            if(d[rson(o)].lz!=-1)d[rson(o)].lz^=1;
            else d[rson(o)].re^=1;

            swap(d[lson(o)].max[1],d[lson(o)].max[0]);
            swap(d[rson(o)].max[1],d[rson(o)].max[0]);

            swap(d[lson(o)].lmax[1],d[lson(o)].lmax[0]);
            swap(d[rson(o)].lmax[1],d[rson(o)].lmax[0]);

            swap(d[lson(o)].rmax[1],d[lson(o)].rmax[0]);
            swap(d[rson(o)].rmax[1],d[rson(o)].rmax[0]);
        }
    }

    inline void modify(int l,int r,int tag,int o){
        pushdown(o);
        //printf("QAQ, o=%d, l=%d, r=%d\n",o,d[o].l,d[o].r);
        if(d[o].l==l&&d[o].r==r){
            if(tag==0||tag==1){
                d[o].sum=d[o].len*tag;
                d[o].lz=tag;

                d[o].lmax[tag]=d[o].rmax[tag]=d[o].max[tag]=d[o].len;
                d[o].lmax[tag^1]=d[o].rmax[tag^1]=d[o].max[tag^1]=0;

                //puts("QAQAQ1");
            }
            else if(tag==2){
                d[o].sum=d[o].len-d[o].sum;
                d[o].re^=1;

                swap(d[o].max[1],d[o].max[0]);
                swap(d[o].lmax[1],d[o].lmax[0]);
                swap(d[o].rmax[1],d[o].rmax[0]);

                //puts("QAQAQ2");
            }
            return ;
        }
        int mid=(d[o].l+d[o].r)>>1;
        //puts("QwQwQ");
        if(l>mid)modify(l,r,tag,rson(o));
        else if(r<=mid)modify(l,r,tag,lson(o));
        else modify(l,mid,tag,lson(o)),modify(mid+1,r,tag,rson(o));
        //puts("OvOvO");
        pushup(o);
    }

    inline int query(int l,int r,int o){
        pushdown(o);
        if(d[o].l==l&&d[o].r==r){
            return d[o].sum;
        }
        int mid=(d[o].l+d[o].r)>>1;
        if(l>mid)return query(l,r,rson(o));
        else if(r<=mid)return query(l,r,lson(o));
        else return query(l,mid,lson(o))+query(mid+1,r,rson(o));
    }

    inline Node Q(int l,int r,int o){
        pushdown(o);
        if(d[o].l==l&&d[o].r==r){
            return d[o];
        }
        int mid=(d[o].l+d[o].r)>>1;
        if(l>mid)return Q(l,r,rson(o));
        else if(r<=mid)return Q(l,r,lson(o));
        else{
            Node tmp,L=Q(l,mid,lson(o)),R=Q(mid+1,r,rson(o));
            tmp.sum=L.sum+R.sum;
            for(int i=0;i<=1;i++){
                tmp.lmax[i]=L.lmax[i];
                if(i==0&&L.sum==0){
                    tmp.lmax[i]+=R.lmax[i];
                }
                else if(i==1&&L.sum==L.len){
                    tmp.lmax[i]+=R.lmax[i];
                }
                tmp.rmax[i]=R.rmax[i];
                if(i==0&&R.sum==0){
                    tmp.rmax[i]+=L.rmax[i];
                }
                else if(i==1&&R.sum==R.len){
                    tmp.rmax[i]+=L.rmax[i];
                }
                tmp.max[i]=L.rmax[i]+R.lmax[i];
                tmp.max[i]=max(tmp.max[i],L.max[i]);
                tmp.max[i]=max(tmp.max[i],R.max[i]);
            }
            return tmp;
        }
    }

    inline void print(){
        for(int i=1;i<=(n<<1);i++){
            printf("i=%d, sum=%d, len=%d, l=%d, r=%d, lz=%d, re=%d, lmax[0]=%d, lmax[1]=%d, rmax[0]=%d, rmax[1]=%d, max[0]=%d, max[1]=%d\n",i,d[i].sum,d[i].len,d[i].l,d[i].r,d[i].lz,d[i].re,d[i].lmax[0],d[i].lmax[1],d[i].rmax[0],d[i].rmax[1],d[i].max[0],d[i].max[1]);
            printf("————————————————————————————————————————————————-———————————————————————————————————————————————————————————————————\n");
        }
    }

};

SMT tree;

int main(void){

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }

    tree.build(1,n,1);
    //tree.print();

    while(m--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        opt++,l++,r++;
        //printf("%d %d %d\n",opt,l,r);
        if(opt==1){
            tree.modify(l,r,0,1);
        }
        else if(opt==2){
            tree.modify(l,r,1,1);
        }
        else if(opt==3){
            tree.modify(l,r,2,1);
        }
        else if(opt==4){
            printf("%d\n",tree.query(l,r,1));
        }
        else if(opt==5){
            printf("%d\n",tree.Q(l,r,1).max[1]);
        }
    }

    return 0;
}

by Andy_chen @ 2020-08-18 12:32:39

这个线段树太疯狂了%%%%%%%%%


by PYD1 @ 2020-08-19 12:22:00

@云浅知处

您的数据生成器是不是写挂了?或者您数据范围开太小了?我拍了一下:

Input:

10 3 1 1 1 1 0 1 0 1 0 1 2 1 7 4 7 9 3 1 5

Output:

1 1

Your Output:

1 2

同时,我把“4 7 9”这一查询操作删除后,发现您的程序的输出就对了,说明可能是4操作(或pushup/pushdown)出了一些问题。


by PYD1 @ 2020-08-19 12:22:21

好吧Markdown炸了


by 云浅知处 @ 2020-08-19 13:07:22

@PYD1 好的好的,谢谢大佬QAQ


by PYD1 @ 2020-08-19 13:18:01

@云浅知处 谔谔


|