萌新刚学Splay,求大佬讲讲这两种的区别
查看原帖
萌新刚学Splay,求大佬讲讲这两种的区别
568865
yan044楼主2022/11/9 18:24

查询rank为x的数时

il int rnk_val(int x)
        {
            int now = root;
            while (1)
            {
                if (son[now][0] && siz[son[now][0]] >= x) now = son[now][0];
                else 
                {
                    x -= (siz[son[now][0]] + cnt[now]);
                    if (x <= 0)
                    {
                        splay(now);
                        return val[now];
                    }
                    now = son[now][1];
                }
            }
        }

这是正解 但是,这样就会T

il int rnk_val(int x)
        {
            int now = root;
            while (1)
            {
                if (son[now][0] && siz[son[now][0]] >= x) now = son[now][0];
                else 
                {
                    x -= siz[son[now][0]];
                    if (x <= cnt[now])//这里不一样
                    {
                        splay(now);
                        return val[now];
                    }
                    now = son[now][1];
                }
            }
        }

有没有佬来讲一下原因(一个关注)

2022/11/9 18:24
加载中...