对着题解Debug了半天,更改后AC。但是没明白为什么。
```cpp
int get_next(int key, int k){
int x = 0, y = 0, ans, now;
split(root[k], key, x, y);
now = y;
while(t[now].lson) now = t[now].lson;
ans = y ? t[now].val : INF;
root[k] = merge(x, y);
return ans;
}
```
在上述代码中,分裂时如果按照 key 分裂,就能 AC, 按照 key + 1分裂会在上万行输出中 WA 一个点。请问有大佬知道为什么不能按 key + 1 分裂吗?
by 青鸟_Blue_Bird @ 2022-11-18 22:23:26
而且,如果按照 key 分裂的话,取到的值不就永远是自己了吗?
by 青鸟_Blue_Bird @ 2022-11-18 22:31:00
@[青鸟_Blue_Bird](/user/234224) 你的split是按照节点值小于等于要求值做分裂的,如果你按照x+1分裂,分裂结果是右边树大于x+1,左边小于等于x+1,而你查找的是右边树最小的值,这样如果x的后继刚好是x+1你就查不到。
by kyEEcccccc @ 2023-01-20 21:30:01