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;
}