Как обратить массив из индекса i в индекс j несколько раз, используя декартово дерево?

Предположим, у меня есть заданный массив 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

Я слышал, что это можно сделать с помощью декартовых деревьев. Итак, я читал блог здесь, но я все еще не могу понять, как мы можем сделать это, используя декартово дерево, каковы должны быть ключ и ценность и как мы должны реализовать?

Источник

2 ответа

Решение

В этой задаче следует использовать трэп (иначе говоря, декартово дерево) с неявным ключом (ключа вообще нет, речь идет только о слиянии их в правильном порядке). Значение узла - это элемент массива, который он представляет. Чтобы реализовать обратную операцию, вы можете поддерживать обратный флаг для каждого узла (true, если он должен быть обращен, false в противном случае) и нажимать его лениво (нажать здесь означает обмен левыми и правыми дочерними узлами узла и переключение значения флага в его дети).

Псевдокод для 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
Источник

Ниже приведены некоторые примеры, которые вы могли бы использовать.

Источник
Другие вопросы по тегам