不用旋转的treap？——fhq treap

前置知识：二叉排序树treap（https://www.luogu.org/blog/ztz11/pinghengshu-bst）了解什么是函数式编程（https://www.sohu.com/a/222320820_355140）本文代码均未经编译，如有错误请指出。826755370-“平衡树好烦啊，转来转去的，而且treap遇到区间序列问题就gg。

有两种类型的划分，一种是权重划分，另一种是划分。我们来谈谈权力的分裂。如图所示，当我们遍历一个节点时，如果它的权重小于k，那么它的左子树将被分割成左边的树，然后我们将迭代它的右子，如果它大于k，然后把它右边的子树分配给右边的树。如果我现在达到递归边界==0怎么办？这里有两种情况：1.root=0（即第一次分割），很明显初始化x和y，即x=y=0。

排名分割类似于权重的分割，将第一个k放在一个树中，其余放在另一个树中。码：

如图所示，我们假设第一棵树的权重小于第二棵树的权重，然后我们比较它们的随机权重。如果rnd[l]=rnd[r]，那么我们可以保留第二棵树的右子树，另一棵树作为左子树。码：

完成上述操作后，我们可以使用函数式编程的思想来完成剩余的操作。直接暴力合并，代码：

要删除权重值为v的点，首先将整个树以v作为权重分割为两个树a，b，然后根据v-1将树分成c，d。这时，v的值必须是d的根，然后我们将合并d的两个儿子（关键点：这一步是为了消除v的影响），然后重新合并它们以得到一棵新树，这个树删除了v。代码的效果：

根据a-1的权重直接分离树木，然后x树中最大的树木应小于或等于a-1，则a的等级为大小[x]+1。码：

不想说什么，直接看一下代码：让我们先看看前一个，因为它小于a，所以我们仍然按照a-1的权重划分x，现在x中的最大数字必须小于或等于a-1，所以我们直接输出x最大的数字是好的，继承不会重复。码：

查询间隔[l，r]将树分割成三棵树，检查中间树，然后将它们合并。码：

Fhqtreap可以持久化。如图所示，每次拆分和合并时，都可以创建一个新的。请注意，下游标记还必须创建一个新点。1.LuoguP3369普通迪斯科平衡树（https://www.luogu.org/problemnew/show/P3369）是为了整合上述东西。码：

持久性序列需要三个操作：1lr，将间隔从l翻转到r;2lr，询问从l到r的间隔;3p，返回p。每次修改新点以翻转标记时，代码（感谢permui的代码http://www.cnblogs.com/owenyu/）：