arrays - 如何使用笛卡尔树将数组从索引 i 多次反转到索引 j？

Question

假设我有一个给定的数组A，现在有多个形式的操作

reverse i,j // means reverse the array Ai..j inclusive

和

print i,j

打印数组 Ai..j.

例子，

A = 6 9 1 10 4 15 9
reverse 2,3
A = 6 1 9 10 4 15 9
reverse 3,6
A = 6 1 15 4 10 9 9
print 1,4

6 1 15 4

听说可以用笛卡尔树来做。所以我一直在看博客here但我仍然不明白我们如何使用笛卡尔树来做到这一点，键和值应该是什么以及我们应该如何实现？

Answer 1

在这个问题中，应该使用带有隐式键的treap(又名笛卡尔树)(根本没有键，只是按正确的顺序合并它们)。节点的值是它表示的数组元素。要实现反向操作，可以为每个节点维护反向标志(如果必须反向则为true，否则为false)并延迟推送(这里的推送意味着交换节点的左右子节点并翻转其中的标志值它的 child )。

推送伪代码:

void push(Node node)
    if node.flag
        swap(node.left, node.right)
        if node.left != null
            node.left.flag = not node.left.flag
        if node.right != null
            node.right.flag = not node.right.flag