不会指针Splay的蒟蒻表示无能为力
by int32 @ 2021-02-28 20:07:29
可以在$splay$之前先就把当前节点到根路径递归$push\_down$一遍 ~~我也不会指针~~
by jerry3128 @ 2021-02-28 20:09:15
@[jerry3128](/user/27338) 但是假如有x(有标记)其子节点为lc,rc
在修改lc时pushdown了x,此时rc带上了tag
那也没用啊qaq最后还是要On下放不行啊
by cmll02 @ 2021-02-28 20:11:25
555为什么写指针的那么少啊((
~~我觉得指针用起来很顺啊~~
by cmll02 @ 2021-02-28 20:11:55
@[cmll02](/user/171487) 你只下放到根路径啊,其他标记打着不管啊。是$O(dep)$的呀(
by jerry3128 @ 2021-02-28 20:13:40
@[jerry3128](/user/27338) 我rotate的时候pushdown了
by cmll02 @ 2021-02-28 20:14:46
~~我是指我这样做不会出现其他一些奇怪的错误。~~
by jerry3128 @ 2021-02-28 20:16:52
~~艹,你不说我还没认真看~~
$push\_down$是应该在$rotate$之前进行的啊。
by jerry3128 @ 2021-02-28 20:19:15
```cpp
inline void rotate(Node *x)
{
int f=d(x);
//akioi(x);puts("AKIOI");
pushdown(x);
if(f==1)rotateL(x);
else if(f==0)rotateR(x);
}
```
我好像知道问题;
by cmll02 @ 2021-02-28 20:23:25
@[jerry3128](/user/27338) 过了,谢谢!我改成这样
```cpp
inline void rotate(Node *x)
{
//akioi(x);puts("AKIOI");
if(x->fa)pushdown(x->fa);
pushdown(x);
int f=d(x);
if(f==1)rotateL(x);
else if(f==0)rotateR(x);
}
```
by cmll02 @ 2021-02-28 20:48:56