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

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

Answer 1

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

推送的伪代码：

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