萌新求助，样例过不去$qAq$

zhoukangyang @ 2020-04-27 21:51:43

#include<bits/stdc++.h>
using namespace std;
int n,m,s[100001],son[100001][2],siz[100001],laz[100001],key[100001],L,R,splx,sply,splz,root,tot;
int upd(int now) {
    siz[now]=siz[son[now][0]]+siz[son[now][1]]+1;
}
void pushdown(int now) {
    if(!laz[now]) return;
    swap(son[now][0],son[now][1]);
    laz[son[now][0]]^=1,laz[son[now][1]]^=1;
}
void split(int now,int k,int &x,int &y) {
    if(!now) x=y=0;
    else if(k==0) x=0,y=now;
    else {
        pushdown(now);
        if(son[now][0]>=k) y=now,split(son[now][0],k,x,son[now][0]);
        else x=now,split(son[now][1],k-son[now][0]-1,son[now][1],y);
        upd(now);
    } 
}
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(key[x]<key[y]) {
        pushdown(x),son[x][1]=merge(son[x][1],y),upd(x);
        return x;
    }
    else {
        pushdown(y),son[y][0]=merge(x,son[y][0]),upd(y);
        return y;
    }
}
void print(int now) {
    if(!now) return;
    pushdown(now);
    print(son[now][0]);
    ++tot,printf("%d ",s[now]);
    print(son[now][1]);
}  
int main() {
    srand(1919810);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) {
        s[i]=i,siz[i]=1,key[i]=rand();
        root=merge(root,i);
    }
    while(m--) {
        scanf("%d%d",&L,&R);
        split(root,R,splx,sply),split(splx,L-1,splx,splz);
        laz[splz]^=1;
        root=merge(merge(splx,splz),sply);
    }
    print(root);
    return 0;
}

by Lice @ 2020-04-27 22:01:44

@zhoukangyang 我看看

今天刚好写这个

by 热言热语 @ 2020-04-27 22:05:26

一个原则：保证打上延迟标记时当前节点的状态是更新过的

by zhoukangyang @ 2020-04-27 22:13:14

发现一个错误，更新代码

#include<bits/stdc++.h>
using namespace std;
int n,m,s[100001],son[100001][2],siz[100001],laz[100001],key[100001],L,R,splx,sply,splz,root,tot;
int upd(int now) {
    siz[now]=siz[son[now][0]]+siz[son[now][1]]+1;
}
void pushdown(int now) {
    if(!laz[now]) return;
    swap(son[now][0],son[now][1]);
    laz[son[now][0]]^=1,laz[son[now][1]]^=1;
}
void split(int now,int k,int &x,int &y) {
    if(!now) x=y=0;
    else {
        pushdown(now);
        if(siz[son[now][0]]>=k) y=now,split(son[now][0],k,x,son[now][0]);
        else x=now,split(son[now][1],k-siz[son[now][0]]-1,son[now][1],y);
        upd(now);
    } 
}
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(key[x]<key[y]) {
        pushdown(x),son[x][1]=merge(son[x][1],y),upd(x);
        return x;
    }
    else {
        pushdown(y),son[y][0]=merge(x,son[y][0]),upd(y);
        return y;
    }
}
void print(int now) {
    if(!now) return;
    pushdown(now);
    print(son[now][0]);
    ++tot,printf("%d ",s[now]);
    print(son[now][1]);
}  
int main() {
    srand(1919810);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) {
        s[i]=i,siz[i]=1,key[i]=rand();
        root=merge(root,i);
    }
    while(m--) {
        scanf("%d%d",&L,&R);
        split(root,R,splx,sply),split(splx,L-1,splx,splz);
        pushdown(splz),upd(splz),laz[splz]^=1;
        root=merge(merge(splx,splz),sply);
    }
    print(root);
    return 0;
}

by Lice @ 2020-04-27 22:15:44

@zhoukangyang 改好了，两个问题：

1. split 中应该是打错了，没有加siz.

2. pushdown 中标记下传未清空

#include<bits/stdc++.h>
using namespace std;
int n,m,s[100001],son[100001][2],siz[100001],laz[100001],key[100001],L,R,splx,sply,splz,root,tot;
void upd(int now) {
    siz[now]=siz[son[now][0]]+siz[son[now][1]]+1;
}
void pushdown(int now) {
    if(!laz[now]) return;
    swap(son[now][0],son[now][1]);
    laz[son[now][0]]^=1,laz[son[now][1]]^=1;
    laz[now] = 0;
}
void split(int now,int k,int &x,int &y) {
    if (!now) return void(x = y = 0);
    pushdown(now);/*
    if(son[now][0]>=k) y=now,split(son[now][0],k,x,son[now][0]);
    else x=now,split(son[now][1],k-son[now][0]-1,son[now][1],y);*/
    /*
    if (k >= size[lc[u]] + 1)
        l = u, split(rc[u], k - size[lc[u]] - 1, rc[u], r);
    else r = u, split(lc[u], k, l, lc[u]);
    */
    if (k >= siz[son[now][0]] + 1)
        x = now, split(son[now][1], k - siz[son[now][0]] - 1, son[now][1], y);
    else y = now, split(son[now][0], k, x, son[now][0]);
    upd(now);
}
int merge(int x,int y) {
    if(!x||!y) return x+y;
    if(key[x]<key[y]) {
        pushdown(x),son[x][1]=merge(son[x][1],y),upd(x);
        return x;
    }
    else {
        pushdown(y),son[y][0]=merge(x,son[y][0]),upd(y);
        return y;
    }
}
void print(int now) {
    if(!now) return;
    pushdown(now);
    print(son[now][0]);
    printf("%d ",s[now]);
    print(son[now][1]);
}  
int main() {
    srand(1919810);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) {
        s[i]=i,siz[i]=1,key[i]=rand();
        root=merge(root,i);
    }
    while(m--) {
        scanf("%d%d",&L,&R);
        split(root,R,splx,sply),split(splx,L-1,splx,splz);
        laz[splz]^=1, pushdown(splz);
        root=merge(merge(splx,splz),sply);
    }
    print(root);
    return 0;
}

by zhoukangyang @ 2020-04-27 22:16:19

@Wallace 谢谢大佬！

by Lice @ 2020-04-27 22:16:36

还有就是——

by zhoukangyang @ 2020-04-27 22:21:06

在您面前我就是蒟蒻/kk