96分,WA一个点求救

P3835 【模板】可持久化平衡树

对着题解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


|