原理是求排名时应特判splay的根节点权值是前驱还是后继,如实现是先插入最小、最大值后进行 `rk()` 求到其前驱后继后应判断:`sz[ch[rt][0]] + (val[rt] < x ? cnt[rt] : 0)`
给出一种被广泛采用的 rk() 实现:
```cpp
void rk(int x) { //相等节点或前驱/后继节点
int cur = rt;
if (!cur) return; //特判树为空
while (ch[cur][x > val[cur]] && x != val[cur])
cur = ch[cur][x > val[cur]];
splay(cur);
}
```
by Arson1st @ 2023-10-21 11:16:55
@[chen_zhe](/user/8457)
by Amon_Xolotl @ 2023-10-21 11:19:44
@[_RSY_](/user/46197) @[Maxmilite](/user/274993) @[feecle6418](/user/42156) @[minstdfx](/user/100250)
by Arson1st @ 2023-10-21 21:30:21
@[N_z_](/user/320087)
by Arson1st @ 2023-10-23 19:00:53
[第一篇:死循环](https://www.luogu.com.cn/blog/pks-LOVING/more-senior-data-structure-te-bie-qian-di-qian-tan-splay)
[第二篇:答案错误](https://www.luogu.com.cn/blog/teljian/solution-p3369)
[Treap:输出1 1](https://www.luogu.com.cn/blog/QVQ/solution-p3369)
[第三篇:答案错误](https://www.luogu.com.cn/blog/cjyyb/solution-p3369)
[AVL:RE?没有输出](https://www.luogu.com.cn/blog/YCE-22/solution-p3369)
[第四篇:答案错误](https://www.luogu.com.cn/blog/user22890/solution-p3369)
[第五篇:答案错误](https://www.luogu.com.cn/blog/sophon/solution-p3369)
[Treap:输出1 1](https://www.luogu.com.cn/blog/ylx/solution-p3369)
[第六篇:答案错误](https://www.luogu.com.cn/blog/161849/solution-p3369)
by Arson1st @ 2023-10-23 19:22:50
只有这几篇还是其他没测
by N_z_ @ 2023-10-23 20:00:07
@[Arson1st](/user/767765)
by N_z_ @ 2023-10-23 20:01:22
但是输出排名不应该是出现在里面的数吗
(我认为)
by Acoipp @ 2023-10-23 20:02:36
@[N_z_](/user/320087) 只测到了第五页
by Arson1st @ 2023-10-23 20:05:28
@[Acoipp](/user/674469) 比当前数小的个数 +1 确实没有这个限制吧。
by N_z_ @ 2023-10-23 20:05:33