如何使用笛卡尔树多次将数组从索引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

Answer 2

下面是一些您可以使用的示例。

​

console.log(
  Array.from({length:1}).reduce((acc,item)=>acc.reverse(),[1,2,3]),
  Array.from({length:2}).reduce((acc,item)=>acc.reverse(),[1,2,3]),
  Array.from({length:3}).reduce((acc,item)=>acc.reverse(),[1,2,3])
)

console.log(  Array.from({length:1}).reduce((acc,item)=>acc.reverse(),Array(...'love')).join(''),  Array.from({length:2}).reduce((acc,item)=>acc.reverse(),Array(...'love')).join(''),  Array.from({length:3}).reduce((acc,item)=>acc.reverse(),Array(...'love')).join('')
)

const reverseXTimes = (word, xTimes)=> Array.from({length:xTimes}).reduce((acc,item)=>acc.reverse(),Array(...word)).join('')

console.log(
  reverseXTimes('passion',1),
  reverseXTimes('passion',2),
  reverseXTimes('passion',3),
)

​