关于此题 fhq-treap 写法

P3372 【模板】线段树 1

YangRuibin @ 2024-08-28 21:47:39

按理说 fhq-treap 最多开 n 个点，但数组开 1e5 会 RE，但开到 4e5 就 AC了。求助原因。

by Iniaugoty @ 2024-08-28 21:55:39

我擦这么神奇

对着你的代码干瞪眼没瞪出来

你等我自己写一个看看

by Nityacke @ 2024-08-28 22:00:52

@YangRuibin 你这 cpypos 是啥啊

by Nityacke @ 2024-08-28 22:01:30

改成 x|y 就对了

https://www.luogu.com.cn/record/175174239

by Nityacke @ 2024-08-28 22:02:25

然后一次 merge 新建一个点，总点数就是 n+n+2*m 的

by Iniaugoty @ 2024-08-28 22:09:53

非常好，我的 FHQ 写完了，你的问题也被回答完了

by Iniaugoty @ 2024-08-28 22:10:26

可以发现只开一倍空间是可以的

by YangRuibin @ 2024-08-28 22:28:22

我知道了，原来是一个低级错误，愣是把普通平衡树写成了【伪】可持久化。

十分感谢。