蒟蒻没想明白怎么寻找分裂结点,如何判断从这里分裂是正确的
日报上是这么说的:
为什么这样分裂是正确的?当我们对左区间树不断建立虚拟的右儿子时,而 now 的 val 都是单调不减的,所以左区间树满足二叉搜索树的性质,当我们对右区间树不断建立虚拟的左儿子时,而 now 的 val 都是单调不增的,所以右区间树满足二叉搜索树的性质。而这样建树又不会将祖先与后代的关系交换,即便祖父节点变成了父亲节点,它仍是祖先节点,所以左右区间树满足堆的性质。
出自:https://www.luogu.com.cn/blog/85514/fhq-treap-xue-xi-bi-ji
一点都看不懂,求大佬帮忙解释一下
bdfs P也不是