两个问题：
一是 `delete` 函数有点问题，我改了一下：
```c++
inline void delect(int val){
int p = rt;
while(1){
if(val == value[p]) break;
if(val < value[p]) p = sons[p][0];
else p = sons[p][1];
}
if(cnt[p] > 1){
cnt[p]--;
sz[p]--;
splay(p);
return;
}
while(1){
if(!sons[p][0] && !sons[p][1]){
sons[fa[p]][get_pos(p)] = 0;
update(fa[p]);
if(fa[p]) splay(fa[p]);
else rt=0;
fa[p] = 0;
return ;
}
if(tem = sons[p][0]){
rorate(sons[p][0]);
p = sons[tem][1];
}
else{
rorate(tem = sons[p][1]);
p = sons[tem][0];
}
}
}
```
二是 `get_rk` 所访问到的点要 splay 上去，否则复杂度会退化。
当然可能还有点问题，毕竟我到现在都不能保证我的 splay 板子复杂度是对的...
@[huangrenheluogu](/user/461359)
by xzf888 @ 2023-12-12 15:48:58
@[xzf888](/user/1217150) 谢谢，但是问个问题，我感觉 `get_rk` 的函数就是一个访问的过程，不需要 Splay 吧。
by huangrenheluogu @ 2023-12-12 16:35:10
`delect` 函数已更改，下面重发一遍代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, sons[N][2], cnt[N], idx, rt, fa[N], sz[N], value[N], tem, o, val;
inline bool get_pos(int x){
return x == sons[fa[x]][1];
}
inline void update(int x){
sz[x] = sz[sons[x][0]] + sz[sons[x][1]] + cnt[x];
}
inline void rorate(int x){
int f = fa[x], gf = fa[fa[x]];
if(f == 0) return ;
bool pos = get_pos(x), pos1 = get_pos(f);
sons[f][pos] = sons[x][pos ^ 1];
sons[x][pos ^ 1] = f;
fa[f] = x, fa[sons[f][pos]] = f;
fa[x] = gf;
if(gf){
sons[gf][pos1] = x;
}
update(f);
update(x);
}
inline void splay(int x){
for(int i = fa[x]; i ; rorate(x), i = fa[x]){
if(fa[i]) rorate(get_pos(i) == get_pos(x) ? i : x);
}
rt = x;
}
inline void insert(int val){
int p = rt, f = 0;
while(1){
if(val == value[p] && p){
cnt[p]++;
sz[p]++;
splay(p);
return ;
}
f = p;
p = sons[p][val < value[p] ? 0 : 1];
if(!p){
p = ++idx;
cnt[p] = 1;
sz[p] = 1;
value[p] = val;
if(f){
fa[p] = f;
sons[f][value[f] > val ? 0 : 1] = p;
update(f);
}
splay(p);
return ;
}
}
}
inline void delect(int val){
int p = rt;
while(1){
if(val == value[p]) break;
if(val < value[p]) p = sons[p][0];
else p = sons[p][1];
}
if(cnt[p] > 1){
cnt[p]--;
sz[p]--;
splay(p);
}
while(1){
if(!sons[p][0] && !sons[p][1]){
sons[fa[p]][get_pos(p)] = 0;
update(fa[p]);
if(fa[p]) splay(fa[p]);
else rt = 0;
fa[p] = 0;
return ;
}
if(tem = sons[p][0]){
rorate(sons[p][0]);
p = sons[tem][1];
}
else{
rorate(tem = sons[p][1]);
p = sons[tem][0];
}
}
}
inline int get_rk(int val){
int p = rt, res = 0;
while(1){
if(!p){
return res + 1;
}
if(val == value[p]){
return res + sz[sons[p][0]] + 1;
}
if(val < value[p]){
p = sons[p][0];
}
else{
res += sz[sons[p][0]] + cnt[p];
p = sons[p][1];
}
}
}
inline int get_num(int rk){
int p = rt;
while(1){
if(rk <= sz[sons[p][0]]){
p = sons[p][0];
continue ;
}
if(rk > sz[sons[p][0]] + cnt[p]){
rk -= sz[sons[p][0]] + cnt[p];
p = sons[p][1];
continue ;
}
return value[p];
}
}
inline int get_pre(){
int p = sons[rt][0];
while(sons[p][1]) p = sons[p][1];
return value[p];
}
inline int get_nxt(){
int p = sons[rt][1];
while(sons[p][0]) p = sons[p][0];
return value[p];
}
int main(){
// freopen("data.in", "r", stdin);
// freopen("code.out", "w", stdout);
scanf("%d", &n);
while(n--){
scanf("%d%d", &o, &val);
// printf("opt is %d %d : \n", o, val);
switch(o){
case 1:
insert(val);
break;
case 2:
delect(val);
break;
case 3:
printf("%d\n", get_rk(val));
break;
case 4:
printf("%d\n", get_num(val));
break;
case 5:
insert(val);
printf("%d\n", get_pre());
delect(val);
break;
case 6:
insert(val);
printf("%d\n", get_nxt());
delect(val);
break;
default:
assert(0);
}
}
return 0;
}
```
by huangrenheluogu @ 2023-12-12 16:38:00
@[huangrenheluogu](/user/461359) 你的delete真改完了吗？好像在67行后面还少了 `return` 吧
另外最后一个点好像是从小到大插入权值的，这时候 splay 会退化为接近一条链，此时在多次查询最深的一号点的排名会炸。
毕竟 splay 嘛... 我用了半年的板子最后发现写了个假的双旋...
by xzf888 @ 2023-12-12 21:43:00
@[xzf888](/user/1217150) 谢谢。
by huangrenheluogu @ 2023-12-12 21:45:12
已 A，结此贴。
by huangrenheluogu @ 2023-12-13 07:51:24