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