10to100

P2572 [SCOI2010] 序列操作

steveyang137 @ 2024-07-22 10:04:49

先放一下我的程序作为参考。 注意cover和flip之间的关系:cover时清空flip标记,flip时不清空cover标记,因此如果有两个标签,cover必在flip之前发生。 而且,由于cover后可能还有flip,所以 不要清空flip tag!

总之看看我的代码和你的实现有什么出入吧

void pushdown(int p,int l,int r) {
    int mid=l+r>>1;
    if(seg[p].cover_tag!=-1) {
        seg[p<<1].tot=seg[p].cover_tag*(mid-l+1);
        seg[p<<1|1].tot=seg[p].cover_tag*(r-mid);
        seg[p<<1].cover_tag=seg[p<<1|1].cover_tag=seg[p].cover_tag;
        seg[p<<1].lmx=seg[p<<1].rmx=seg[p<<1].mx=(mid-l+1)*seg[p].cover_tag;
        seg[p<<1].lmx0=seg[p<<1].rmx0=seg[p<<1].mx0=(mid-l+1)*!seg[p].cover_tag;
        seg[p<<1|1].lmx=seg[p<<1|1].rmx=seg[p<<1|1].mx=(r-mid)*seg[p].cover_tag;
        seg[p<<1|1].lmx0=seg[p<<1|1].rmx0=seg[p<<1|1].mx0=(r-mid)*!seg[p].cover_tag;
        seg[p<<1].flip_tag=seg[p<<1|1].flip_tag=0;
        seg[p].cover_tag=-1;
        // seg[p].flip_tag=0;
    }
    if(seg[p].flip_tag) {
        seg[p<<1].tot=mid-l+1-seg[p<<1].tot;
        seg[p<<1].flip_tag^=1;
        // seg[p<<1].cover_tag^=1;
        swap(seg[p<<1].lmx,seg[p<<1].lmx0);
        swap(seg[p<<1].rmx,seg[p<<1].rmx0);
        swap(seg[p<<1].mx,seg[p<<1].mx0);

        seg[p<<1|1].tot=r-mid-seg[p<<1|1].tot;
        seg[p<<1|1].flip_tag^=1;
        // seg[p<<1|1].cover_tag^=1;
        swap(seg[p<<1|1].lmx,seg[p<<1|1].lmx0);
        swap(seg[p<<1|1].rmx,seg[p<<1|1].rmx0);
        swap(seg[p<<1|1].mx,seg[p<<1|1].mx0);
        seg[p].flip_tag=0;
    }
}

void modify(int p,int l,int r,int s,int t,int x) {
    if(s<=l&&r<=t) {
        if(x==0) seg[p]={0,0,0,0,0,0,r-l+1,r-l+1,r-l+1,seg[p].len};
        else if(x==1) seg[p]={r-l+1,1,0,r-l+1,r-l+1,r-l+1,0,0,0,seg[p].len};
        else {
            seg[p].tot=r-l+1-seg[p].tot;
            seg[p].flip_tag^=1;
            swap(seg[p].lmx,seg[p].lmx0);
            swap(seg[p].rmx,seg[p].rmx0);
            swap(seg[p].mx,seg[p].mx0);
        }
        return;
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    if(s<=mid) modify(p<<1,l,mid,s,t,x);
    if(mid<t) modify(p<<1|1,mid+1,r,s,t,x);
    seg[p]=merge(seg[p<<1],seg[p<<1|1]);
    return;
}

by yanbinmu @ 2024-10-19 12:10:51

Orz


|