How to reverse an array from index i to index j multiple times using cartesian tree?

Question

Suppose I have a given array A. Now there are multiple operations of the form

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

and

print i,j

Print the array Ai..j.

Example ,

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

I have heard that it can be done by cartesian trees. So I have been reading the blog here But I still can't understand how we can do this using cartesian tree, what is the key and value should be and how we should implement ?

Answer 1

In this problem, a treap(aka Cartesian tree) with implicit key should be used(there is no key at all, it is just about merging them in right order). The value of a node is an array element that it represents. To implement reverse operation, you can maintain reverse flag for each node(true if it must be reversed, false otherwise) and push it lazily(to push here means to exchange left and right children of a node and flip the value of a flag in its children).

Pseudo code for push:

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