引入
题目来源：文艺平衡树 - 洛谷P3391
您需要写一种数据结构（可参考题目标题），来维护一个有序数列。
其中需要提供以下操作：翻转一个区间，例如原有序序列是 \(5\ 4\ 3\ 2\ 1\)，翻转区间是 \([2,4]\) 的话，结果是 \(5\ 2\ 3\ 4\ 1\) 。 对于 \(100\%\) 的数据，\(1 \le n\)（初始区间长度）\(m\)（翻转次数）\(\le 1\text{e}5\)。
解决方法
想用平衡树解决区间问题，那么首先考虑如何建树，要求建树建出来就是初始区间。
事实上，只需要把区间的下标插入 treap 中，然后中序遍历即可得到这个区间。
在朴素的 BST 中，按顺序插入结点建出来的是一条链，但在 treap 中，按顺序插入结点后，merge 操作会根据每个节点的 pri 调整树结构，问：如何保证中序遍历一定能正确输出？\
OI Wiki如是解释：
可以参考 笛卡尔树的单调栈建树方法 来理解这个问题。
设新插入的节点为 \(\textit{u}\)。
首先，因为是递增地插入节点，每一个新插入的节点肯定会被连接到 treap 的右链（即从根结点一直往右子树走，经过的结点形成的链）上。
从根节点开始，右链上的节点的 pri 是递增的（小根堆）。那我们可以找到右链上第一个 pri 大于 \(\textit{u}\) 的节点，我们叫这个节点 \(\textit{v}\)，并把这个节点换成 \(\textit{u}\)。
因为 \(\textit{u}\) 一定大于这个树上其他的全部节点，我们需要把 \(\textit{v}\) 以及它的子树作为 \(\textit{u}\) 的左子树。并且此时 \(\textit{u}\) 没有右子树。
可以发现，中序遍历时 \(\textit{u}\) 一定是最后一个被遍历到的（因为 \(\textit{u}\) 是右链中的最后一个，而中序遍历中，右子树是最后被遍历到的）。
博主本人的理解，对照这个图，如果你学过旋转平衡树，你会发现，他事实上可以理解为干了这么一件事：
- 把 \({5,2}\) 插入到 \({4,5}\) 的右儿子；
- 旋转上升
不过是 FHQ Treap 本身并不支持旋转操作，这里就换了一种方式，同样达到了旋转的效果。
那么接下来考虑如何实现区间翻转。
假设你想翻转 \([l,\ r]\)，你的想法就很自然的是先把这个区间给剥离出来再操作。
也就是将树分裂成 \([1, l - 1],\ [l, r],\ [r + 1, n]\) 三个区间，再对中间的 \([l, r]\) 进行翻转。
通过画图，可以发现翻转的具体操作是把区间内的子树的每一个左，右子节点交换位置。
显然的，这个操作的复杂度最坏 \(O(n)\)，不太能够满足我们的需要。我们有什么方法能避免这一点呢？
其实利用线段树的思想。不难发现，翻转再翻转等于没翻转，那么我们在交换时只需要在父节点打上标记，代表这个子树下的每个左右子节点都需要交换就行了。
标记打好了，什么时候下传标记？
回忆在线段树中，我们一般在更新和查询时下传懒标记。这是因为，在更新和查询时，我们想要更新/查询的范围不一定和懒标记代表的范围重合，所以要先下传标记，确保查到和更新后的值是正确的。
FHQ Treap 也一样。具体操作时我们会把 treap 分裂成前文讲到的三个树，然后给中间的树打上懒标记后合并这三棵树。
一句话理解：树的结构发生改变了，你就该下放标记了
为了很快的实现“翻转两次等于没有翻转”，我们想到了使用 异或 来实现。
代码如下：