赇助Splay写法
查看原帖
赇助Splay写法
538609
Neutralized楼主2022/2/8 20:28

主要是 get rank\texttt{get rank} 函数
之前原版里有一个可以过的函数:

inline int getrnk(int x){
    ri cur=root,ret=0;
    while(cur){
        if(val[cur]==x){
            ret+=siz[son[cur][0]];
            splay(cur,0); return ret;
        } if(val[cur]>x)
        cur=son[cur][0];
        else
        ret+=siz[son[cur][0]]+cnt[cur],
        cur=son[cur][1];
    } return ret;
}

然后这是过了原版的另一个函数:

inline int getrnk(int x)
{
    find(x);
    return siz[son[root][0]];
}

其中find(x)如下:

//ri : register int
inline void find(int x){
    ri cur=root;
    while(son[cur][val[cur]<x]&&val[cur]!=x)
    cur=son[cur][val[cur]<x];
    splay(cur,0);
}
//val:点值
//son:两个儿子
//splay(x,tar):把x伸展成tar的儿子

第二个是教练上课讲的版本,因为它又短又能用所以今天一直用的这个(
然后在这里疯狂WA 30pts有10+次
然后我气急败坏翻了很久讨论区发现这里说应该写成原来那样(第一个版本)
¿
求解答

2022/2/8 20:28
加载中...