Neutralized @ 2022-02-08 20:28:04
主要是
之前原版里有一个可以过的函数:
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+次
然后我气急败坏翻了很久讨论区发现这里说应该写成原来那样（第一个版本）
¿
求解答
by Neutralized @ 2022-02-08 20:28:42
换成原来的版本就A了（（（
by Gokix @ 2022-02-08 20:44:46
@Neutralized
你得看 getrank 的那个值在不在 Splay 里
by Gokix @ 2022-02-08 20:47:18
第一个方法是在不在都行
第二个方法必须保证 x 在 Splay 中
仔细看的话数据加强版并不保证 x 在 Splay 中，所以不能用第二个方法by Gokix @ 2022-02-08 20:49:39
但是一般用 Splay 的时候都保证 getrank 的数在 Splay 里by Gokix @ 2022-02-08 20:50:42
而且就算是 x 不在 Splay 中，你也可以先把它插入，查排名之后再删除
三行解决(by Neutralized @ 2022-02-08 21:01:23
@Gokix
抱歉刚刚才看到
非常感谢 刚才脑子抽一下还准备找您再问问 反应过来了（
刚才试了下，第二种雀实可以改成
inline int getrnk(int x){
insert(x);
ri ret=siz[son[root][0]];
erase(x); return ret;
}，只不过会慢一点
已关注
by Gokix @ 2022-02-08 21:07:51
@Neutralized
啊啦啊啦，你写 Splay 竟然还关注常数(((
确实会慢，毕竟要多加点删点，你可以挑一种你喜欢的写
by Neutralized @ 2022-02-08 21:32:47
@Gokix 草 kurumi经典词语
因为经常偷偷淦一些阴间算法不会正解所以卡常都卡成习惯了（