为什么这题splay的时候不pushdown也可以AC啊...

P3391 【模板】文艺平衡树

Brioche @ 2018-09-21 13:29:47

void splay(int x,int tar)
{
    while(fa[x]!=tar)
    {
        int y=fa[x],z=fa[y];
        if(z!=tar)
            rotate(((ch[y][0]==x)^(ch[z][0]==y))?x:y);
        rotate(x);
    }
    if(tar==0)root=x;
}

or

void splay(int x,int tar)
{
    int t=x,cn=0;st[++cn]=x;
    while(t!=tar)st[++cn]=(t=fa[t]);
    while(cn)pushdown(st[cn--]);
    while(fa[x]!=tar)
    {
        if(fa[fa[x]]!=tar)
            rotate(pd(x)^pd(fa[x])?x:fa[x]);
        rotate(x);
    }
    if(tar==0)root=x;
}

by Tyher @ 2018-09-25 13:39:02

@Brioche 发现大佬敲模板 Orz


by Brioche @ 2018-09-25 13:39:56

sto tyh orz


|