如果我的 splay 写法比较诡异,不维护父亲,怎么写 lct 啊 /kel
拒绝玩某 lct 维护 splay 的梗。
splay 写法:
void Splay_(Node *&p, int rk) {
PushDown(p);
if (rk == GetSize(p->l)) {
return;
}
if (rk < GetSize(p->l)) {
PushDown(p->l);
if (rk == GetSize(p->l->l)) {
RotateR(p);
return;
} else if (rk < GetSize(p->l->l)) {
Splay_(p->l->l, rk);
RotateR(p);
RotateR(p);
} else {
rk -= GetSize(p->l->l) + 1;
Splay_(p->l->r, rk);
RotateL(p->l);
RotateR(p);
}
} else {
PushDown(p->r);
rk -= GetSize(p->l) + 1;
if (rk == GetSize(p->r->l)) {
RotateL(p);
return;
} else if (rk < GetSize(p->r->l)) {
Splay_(p->r->l, rk);
RotateR(p->r);
RotateL(p);
} else {
rk -= GetSize(p->r->l) + 1;
Splay_(p->r->r, rk);
RotateL(p);
RotateL(p);
}
}
}