RT,萌新刚学splay,求助为什么splay里必须写pushdown?
这是wa(样例也过不去的代码)
inline void splay(int k, int lim = 0){
for(int fa = f[k] ; (fa = f[k]) != lim ; rotate(k))
if(f[fa] != lim)
get(fa) == get(k) ? rotate(fa) : rotate(k);
if(!lim) rt = k;
}
这是AC代码
inline void splay(int k, int lim = 0){
for(int fa = f[k] ; (fa = f[k]) != lim ; rotate(k)){
pushdown(f[fa]), pushdown(fa), pushdown(k);
if(f[fa] != lim)
get(fa) == get(k) ? rotate(fa) : rotate(k);
}
if(!lim) rt = k;
}
另外,为什么在文艺平衡树里,pushdown()
和splay()
都不需要下传标记?