数据好像有点弱

P6136 【模板】普通平衡树(数据加强版)

aru123 @ 2023-12-14 19:10:45

在别的题里边粘了一个这个题里边写的Splay板子,Wa掉了

……找了半天是删掉节点时忘了pushUp(f(r))一下,这样在删除节点时,f(r)的sz是错的

评测记录

inline void del(int v){
    int pre = findBound(v, 0), suf = findBound(v, 1);
    if(pre) splay(pre, 0);
    if(suf) splay(suf, pre);
    if(!suf && !pre){
        cnt[root] --;
        if(!cnt[root]) root = 0;
        return ;
    }
    int x = suf? ls(suf):rs(pre);
    cnt[x] --;
    if(cnt[x]) splay(x, 0);
    else ch[f[x]][get(x)] = 0;
}

|