Изменения

Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины''' (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути от корня до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.

'''<tex>\langle</tex>Treap, Treap<tex>\rangle</tex>''' split('''Treap''' t, '''int''' k) '''if''' t == <tex> \varnothing </tex> '''return''' <tex>\langle</tex><tex> \varnothing </tex>, <tex> \varnothing </tex><tex>\rangle</tex>

'''if''' l <tex>\small{\geqslant}</tex>= k <tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.left, k)

update(vt) r = v '''return''' <tex>\langle</tex>t1, t2t<tex>\rangle</tex>

<tex>\langle</tex>t1, t2<tex>\rangle</tex> = split(t.right, k - l - 1)

update(vt) l = v '''return''' <t1tex>\langle</tex>t, t2<tex>\rangle</tex>

t.size = 1 + t.left.size + t.right.size + 1