问一个问题

RT，这题还要维护虚儿子的 max 值，我之前在 rotate 中 pushup 两次，后来在 rotate 中 pushup 一次，splay 中 pushup 一次就 AC 了，请问是为什么？

AC:

CPP

inline bool nrt(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
inline void rotate(int x)
{
    int y=fa[x],z=fa[y],k=(ch[y][1]==x),u=ch[x][k^1];
    if(nrt(y)) ch[z][ch[z][1]==y]=x;
    ch[y][k]=u;ch[x][k^1]=y;
    if(u) fa[u]=y;fa[y]=x;fa[x]=z;
    pushup(y);
}
inline void splay(int x)
{
    int y,z;
    while(nrt(x))
    {
        y=fa[x],z=fa[y];
        if(nrt(y)) rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y);
        rotate(x);
    }
    pushup(x);
}

WA:

CPP

inline bool nrt(int x) {return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
inline void rotate(int x)
{
    int y=fa[x],z=fa[y],k=(ch[y][1]==x),u=ch[x][k^1];
    if(nrt(y)) ch[z][ch[z][1]==y]=x;
    ch[y][k]=u;ch[x][k^1]=y;
    if(u) fa[u]=y;fa[y]=x;fa[x]=z;
    pushup(y);pushup(x);
}
inline void splay(int x)
{
    int y,z;
    while(nrt(x))
    {
        y=fa[x],z=fa[y];
        if(nrt(y)) rotate((ch[y][1]==x)^(ch[z][1]==y)?x:y);
        rotate(x);
    }
}

讨论操作

回复

相关推荐

问一个问题