Как Treap помогает обновить эту упорядоченную очередь?

Question

У меня возникают проблемы с пониманием этого решения проблемы на HackerRank. Пожалуйста, смотрите код решения ниже, по-видимому, Кимиюки Онака.

Проблема: дан список уникальных номеров, и m запросы типа "move the current ith to jth elements (l,r) to the beginning", верните окончательное расположение чисел.

Онака предполагает, что структура данных Treap (поддерживающая как приоритетный, так и двоичный поиск) может помочь решить ее в O(m log n), Так как я не разбираюсь в C++, я пытался, но не смог осмыслить, как можно использовать treap. Я понимаю, что для решения проблемы вам нужно log время доступа к текущему ith to jth элементы и log время обновления текущего первого элемента / ов и общего порядка. Но я не понимаю, как это осмыслить.

В идеале я хотел бы объяснить словами, как это можно сделать. В качестве альтернативы, просто объяснение того, что делает код Onaka.

Спасибо!

#include <iostream>
#include <tuple>
#include <random>
#include <memory>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

template <typename T>
struct treap {
    typedef T value_type;
    typedef double key_type;
    value_type v;
    key_type k;
    shared_ptr<treap> l, r;
    size_t m_size;
    treap(value_type v)
            : v(v)
            , k(generate())
            , l()
            , r()
            , m_size(1) {
    }
    static shared_ptr<treap> update(shared_ptr<treap> const & t) {
        if (t) {
            t->m_size = 1 + size(t->l) + size(t->r);
        }
        return t;
    }
    static key_type generate() {
        static random_device device;
        static default_random_engine engine(device());
        static uniform_real_distribution<double> dist;
        return dist(engine);
    }
    static size_t size(shared_ptr<treap> const & t) {
        return t ? t->m_size : 0;
    }
    static shared_ptr<treap> merge(shared_ptr<treap> const & a, shared_ptr<treap> const & b) { // destructive
        if (not a) return b;
        if (not b) return a;
        if (a->k > b->k) {
            a->r = merge(a->r, b);
            return update(a);
        } else {
            b->l = merge(a, b->l);
            return update(b);
        }
    }
    static pair<shared_ptr<treap>, shared_ptr<treap> > split(shared_ptr<treap> const & t, size_t i) { // [0, i) [i, n), destructive
        if (not t) return { shared_ptr<treap>(), shared_ptr<treap>() };
        if (i <= size(t->l)) {
            shared_ptr<treap> u; tie(u, t->l) = split(t->l, i);
            return { u, update(t) };
        } else {
            shared_ptr<treap> u; tie(t->r, u) = split(t->r, i - size(t->l) - 1);
            return { update(t), u };
        }
    }
    static shared_ptr<treap> insert(shared_ptr<treap> const & t, size_t i, value_type v) { // destructive
        shared_ptr<treap> l, r; tie(l, r) = split(t, i);
        shared_ptr<treap> u = make_shared<treap>(v);
        return merge(merge(l, u), r);
    }
    static pair<shared_ptr<treap>,shared_ptr<treap> > erase(shared_ptr<treap> const & t, size_t i) { // (t \ t_i, t_t), destructive
        shared_ptr<treap> l, u, r;
        tie(l, r) = split(t, i+1);
        tie(l, u) = split(l, i);
        return { merge(l, r), u };
    }
};

typedef treap<int> T;
int main() {
    int n; cin >> n;
    shared_ptr<T> t;
    repeat (i,n) {
        int a; cin >> a;
        t = T::insert(t, i, a);
    }
    int m; cin >> m;
    while (m --) {
        int l, r; cin >> l >> r;
        -- l;
        shared_ptr<T> a, b, c;
        tie(a, c) = T::split(t, r);
        tie(a, b) = T::split(a, l);
        t = T::merge(T::merge(b, a), c);
    }
    repeat (i,n) {
        if (i) cout << ' ';
        shared_ptr<T> u;
        tie(t, u) = T::erase(t, 0);
        cout << u->v;
    }
    cout << endl;
    return 0;
}

Answer 1

Возможно, были бы полезны некоторые изображения структуры данных при обработке входных данных.

Во-первых, шесть цифр "1 2 3 4 5 6" вставляются в треп. Каждый из них связан со случайно сгенерированным двойным, который определяет, идет ли он выше или ниже других узлов. Трэп всегда упорядочен так, что все левые потомки узла идут перед ним, а все его правые потомки - после него.

Затем мы начинаем перемещать интервалы в начало. Трепа делится на три части: одна с первыми l-1 узлами, одна с узлами в интервале и последние узлы. Затем они объединяются в другом порядке.

Сначала перемещается интервал [4,5]:

Теперь порядок трэпа 4, 5, 1, 2, 3, 6. (Корень 4 стоит первым, потому что у него нет левого потомка; 3 предшествует его левый потомок 2, которому предшествует его собственный левый потомок 5; затем 5 правого потомка 1, затем 2, затем 3, затем 6.) Узлы отслеживают размер каждого поддерева (m_size).

Учитывая [3,4], мы сначала split(t,4), который должен вернуть пару: один треп с первыми 4 элементами, а другой с остальными.

Корневой узел (4) не имеет 4 вещей под своим левым поддеревом, поэтому он возвращается с split(t->r, 3), Этот узел (3) имеет 3 вещи под своим левым поддеревом, поэтому он вызывает split(t->l, 3), Теперь мы находимся в узле (2). Это вызывает split(t->r, 0), но у него нет правильного потомка, поэтому он возвращает пару нулевых указателей. Таким образом, из узла (2) мы возвращаем неизменное поддерево из (2) и nullptr. Распространяясь вверх, узел (3) устанавливает свой левый дочерний элемент на ноль и возвращает поддерево из (2), а также поддерево в (3) (которое теперь является просто двумя элементами, (3) и (6).) Наконец, в узле (4) мы устанавливаем правое подчиненное значение (2) и возвращаем дерево в (4) (которое теперь имеет четыре элемента, как требуется) и двухэлементное дерево с корнем в (3).

Далее делается звонок split(a,2), где a это первое, четырехэлементное дерево из последнего вызова.

Опять же, корень (4) не имеет левого потомка, поэтому мы рекурсивно split(t->r, 1),

Узел (2) имеет левое поддерево с размером 2, поэтому он вызывает split(t->l, 1),

Узел (5) не имеет левого потомка, поэтому он вызывает split(t->r, 0),

На листе (1) 0 <= size(t->l) пусто верно: он получает пару нулевых указателей от split(t->l, 0) и возвращает пару (ноль, (1)).

В точке (5) мы устанавливаем правому дочернему элементу значение null и возвращаем пару ((5), (1)).

В точке (2) мы устанавливаем левого потомка в (1) и возвращаем пару ((5), (2)->(1)).

Наконец, в (4) мы устанавливаем правого потомка в (5) и возвращаем пару ((4)->(5), (2)->(1)).

Наконец, интервал [2,3] (состоящий из элементов 2 и 4) перемещается:

Наконец, узлы расположены в порядке, получая 2, 4, 1, 5, 3, 6.

Возможно, вы хотели бы видеть древовидные состояния при разных входах. Я поместил копию кода treap, "инструментированного" для создания картинок, на GitHub. При запуске выдает файл trees.tex; затем работает pdflatex trees производит картинки, подобные тем, что указаны выше. (Или, если хотите, я был бы рад сделать снимки для другого ввода: это было бы проще, чем установка целого дистрибутива TeX, если у вас его нет.)