E116. Декартово arbre (treap, дерамида)

Источник: e-maxx.ru/algo, страница PDF 383.

Декартово arbre - это структура данных, объединяющая в себе бинарное arbre поиска и бинарную кучу (отсюда и второе её название: treap (tree+heap) и дерамида (arbre+пирамида). Более строго, это структура данных, которая хранит пары (X,Y) в виде бинарного дерева таким образом, что она является бинарным arbreм поиска по x и бинарной пирамидой по y. Предполагая, что все X и все Y являются различными, получаем, что если некоторый element дерева содержит (X0,Y0), то у всех elementов в левом поддереве X < X0, у всех elementов в правом поддереве X > X0, а также и в левом, и в правом поддереве имеем: Y < Y0. Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.

Преимущества такой организации данных

В том применении, которое мы рассматриваем (мы будем рассматривать дерамиды, поскольку декартово arbre - это фактически более общая структура данных), X'ы являются ключами (и одновременно значениями, хранящимися в структуре данных), а Y'и - называются приоритетами. Если бы приоритетов не было, то было бы обычное бинарное arbre поиска по X, и заданному набору X'ов могло бы соответствовать много деревьев, некоторые из которых являются вырожденными (наExemple, в виде цепочки), а потому чрезвычайно медленными (основные операции выполнялись бы за O (N)). В то же время, приоритеты позволяют однозначно указать arbre, которое будет построено (разумеется, не зависящее от порядка добавления elementов) (это доказывается соответствующей теоремой). Теперь очевидно, что если выбирать приоритеты случайно, то этим мы добьёмся построения невырожденных деревьев в среднем случае, что обеспечит асимптотику O (log N) в среднем. Отсюда и понятно ещё одно название этой структуры данных - рандомизированное бинарное arbre поиска.

Операции

Итак, treap предоставляет следующие операции:

● Insert (X, Y) - за O (log N) в среднем

Выполняет добавление в arbre нового elementа. Возможен вариант, при котором значение приоритета Y не передаётся функции, а выбирается случайно (правда, нужно учесть, что оно не должно совпадать ни с каким другим Y в дереве).

● Search (X) - за O (log N) в среднем

Ищет element с указанным значением ключа X. Реализуется абсолютно так же, как и для обычного бинарного дерева поиска.

● Erase (X) - за O (log N) в среднем

Ищет element и удаляет его из дерева.

● Build (X1, ..., XN) - за O (N)

Строит arbre из списка значений. Эту операцию можно реализовать за линейное время (в предположении, что значения X1, ..., XN отсортированы), но здесь эта Implémentation рассматриваться не будет. Здесь будет использоваться только простейшая Implémentation - в виде последовательных вызовов Insert, т.е. за O (N log N).

● Union (T1, T2) - за O (M log (N/M)) в среднем

Объединяет два дерева, в предположении, что все elementы различны (впрочем, эту операцию можно реализовать с той же асимптотикой, если при объединении нужно удалять повторяющиеся elementы).

● Intersect (T1, T2) - за O (M log (N/M)) в среднем

Находит пересечение двух деревьев (т.е. их общие elementы). Здесь Implémentation этой операции не будет рассматриваться. Кроме того, за счёт того, что декартово arbre является и бинарным arbreм поиска по своим значениям, к нему применимы такие операции, как нахождение K-го по величине elementа, и, наоборот, Définition номера elementа.

Описание реализации

С точки зрения реализации, каждый element содержит в себе X, Y и указатели на левого L и правого R сына. Для реализации операций понадобится реализовать две вспомогательные операции: Split и Merge. Split (T, X) - разделяет arbre T на два дерева L и R (которые являются возвращаемым значением) таким образом, что L содержит все elementы, меньшие по ключу X, а R содержит все elementы, большие X. Эта операция выполняется за O (log N). Implémentation её довольно проста - очевидная рекурсия. Merge (T1, T2) - объединяет два поддерева T1 и T2, и returns это новое arbre. Эта операция также реализуется за O (log N). Она работает в предположении, что T1 и T2 обладают соответствующим порядком (все значения X в первом меньше значений X во втором). Таким образом, нам нужно объединить их так, чтобы не нарушить порядок по приоритетам Y. Для этого просто выбираем в качестве корня то arbre, у которого Y в корне больше, и рекурсивно вызываем себя от другого дерева и соответствующего сына выбранного дерева. Теперь очевидна Implémentation Insert (X, Y). Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по X), но останавливаемся на первом elementе, в котором значение приоритета оказалось меньше Y. Мы нашли позицию, куда будем вставлять наш element. Теперь вызываем Split (X) от найденного elementа (от elementа вместе со всем его подarbreм), и возвращаемые ею L и R записываем в качестве левого и правого сына добавляемого elementа. Также понятна и Implémentation Erase (X). Спускаемся по дереву (как в обычном бинарном дереве поиска по X), ища удаляемый element. Найдя element, мы просто вызываем Merge от его левого и правого сыновей, и возвращаемое ею значение ставим на место удаляемого elementа. Операцию Build реализуем за O (N log N) просто с помощью последовательных вызовов Insert. Наконец, операция Union (T1, T2). Теоретически её Asymptotic complexity O (M log (N/M)), однако на практике она работает очень хорошо, вероятно, с весьма малой скрытой константой. Пусть, не теряя общности, T1->Y > T2->Y, т. е. корень T1 будет корнем результата. Чтобы получить результат, нам нужно объединить деревья T1->L, T1->R и T2 в два таких дерева, чтобы их можно было сделать сыновьями T1. Для этого вызовем Split (T2, T1->X), тем самым мы разобъём T2 на две половинки L и R, которые затем рекурсивно объединим с сыновьями T1: Union (T1->L, L) и Union (T1->R, R), тем самым мы построим левое и правое поддеревья результата.

Implémentation

Реализуем все описанные выше операции. Здесь для удобства введены другие обозначения - приоритет обозначается prior, значения - key.

struct item {

int key, prior;

item * l, * r;

item() { }

item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { } };

typedef item * pitem;

void split (pitem t, int key, pitem & l, pitem & r) {

if (!t)

l = r = NULL;

else if (key < t->key)

split (t->l, key, l, t->l), r = t;

else

split (t->r, key, t->r, r), l = t;

}

void insert (pitem & t, pitem it) {

if (!t)

t = it;

else if (it->prior > t->prior)

split (t, it->key, it->l, it->r), t = it;

else

insert (it->key < t->key ? t->l : t->r, it);

}

void merge (pitem & t, pitem l, pitem r) {

if (!l || !r)

t = l ? l : r;

else if (l->prior > r->prior)

merge (l->r, l->r, r), t = l;

else

merge (r->l, l, r->l), t = r;

}

void erase (pitem & t, int key) {

if (t->key == key)

merge (t, t->l, t->r);

else

erase (key < t->key ? t->l : t->r, key);

}

pitem unite (pitem l, pitem r) {

if (!l || !r)  return l ? l : r;

if (l->prior < r->prior)  swap (l, r);

pitem lt, rt;

split (r, l->key, lt, rt);

l->l = unite (l->l, lt);

l->r = unite (l->r, rt);

return l;

}

Поддержка размеров поддеревьев

Чтобы расширить функциональность декартового дерева, очень часто необходимо для каждой вершины хранить количество вершин в её поддереве - некое поле int cnt в структуре item. НаExemple, с его помощью легко будет find за O (log N) K-ый по величине element дерева, или, наоборот, за ту же асимптотику узнать номер elementа в отсортированном списке (Implémentation этих операций ничем не будет отличаться от их реализации для обычных бинарных деревьев поиска). При изменении дерева (добавлении или удалении elementа и т.д.) должны соответствующим образом меняться и cnt некоторых вершин. Реализуем две функции - функция cnt() будет возвращать текущее значение cnt или 0, если vertex не существует, а функция upd_cnt() будет обновлять значение cnt для указанной вершины, при условии, что для её сыновей l и r эти cnt уже корректно обновлены. Тогда, понятно, достаточно добавить вызовы функции upd_cnt () в конец каждой из функций insert, erase, split, merge, чтобы постоянно поддерживать корректные значения cnt.

int cnt (pitem t) {

return t ? t->cnt : 0;

}

void upd_cnt (pitem t) {

if (t)

t->cnt = 1 + cnt(t->l) + cnt (t->r);

}

Построение декартового дерева за O (N) в оффлайн

TODO

Неявные декартовы деревья

Неявное декартово arbre - это простая модификация обычного декартового дерева, которая, тем не менее, оказывается очень мощной структурой данных. Фактически, неявное декартово arbre можно воспринимать как tableau, над которым можно реализовать следующие операции (все за O (log N) в режиме онлайн):

● Вставка elementа в tableau в любую позицию

● Удаление произвольного elementа

● Сумма, минимум/максимум на произвольном отрезке, и т.д.

● Прибавление, покраска на отрезке

● Переворот (перестановка elementов в обратном порядке) на отрезке

Ключевая идея заключается в том, что в качестве ключей key следует использовать индексы elementов в tableauе. Однако явно хранить эти значения key мы не будем (иначе, наExemple, при вставке elementа пришлось бы изменять key в O (N) vertexх дерева). Заметим, что фактически в данном случае ключ для какой-то вершины - это количество вершин, меньших неё. Следует заметить, что вершины, меньшие данной, находятся не только в её левом поддереве, но и, возможно, в левых поддеревьях её предков. Более строго, неявный ключ для некоторой вершины t равен количеству вершин cnt(t->l) в левом поддереве этой вершины плюс аналогичные величины cnt(p->l)+1 для каждого предка p этой вершины, при условии, что t находится в правом поддереве для p. Ясно, как теперь быстро вычислять для текущей вершины её неявный ключ. Поскольку во всех операциях мы приходим в какую-либо вершину, спускаясь по дереву, мы можем просто накапливать эту сумму, передавая её функции. Если мы идём в левое подarbre - накапливаемая сумма не меняется, а если идём в правое - увеличивается на cnt(t->l)+1. Приведём новые реализации функций split и merge:

void merge (pitem & t, pitem l, pitem r) {

if (!l || !r)

t = l ? l : r;

else if (l->prior > r->prior)

merge (l->r, l->r, r), t = l;

else

merge (r->l, l, r->l), t = r;

upd_cnt (t);

}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {

if (!t)

return void( l = r = 0 );

int cur_key = add + cnt(t->l); // вычисляем неявный ключ

if (key <= cur_key)

split (t->l, l, t->l, key, add), r = t;

else

split (t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t;

upd_cnt (t);

} Теперь перейдём к реализации различных дополнительных операций на неявных декартовых деревьях:

● Вставка elementа.

Пусть нам надо вставить element в позицию pos. Разобьём декартово arbre на две половинки: соответствующую tableauу [0..pos-1] и tableauу [pos..sz]; для этого достаточно вызвать split (t, t1, t2, pos). После этого мы можем объединить arbre t1 с новой вершиной; для этого достаточно вызвать merge (t1, t1, new_item) (нетрудно убедиться в том, что все предусловия для merge выполнены). Наконец, объединим два дерева t1 и t2 обратно в arbre t - вызовом merge (t, t1, t2).

● Удаление elementа.

Здесь всё ещё проще: достаточно find удаляемый element, а затем выполнить merge для его сыновей l и r, и поставить результат объединения на место вершины t. Фактически, удаление из неявного декартова дерева не отличается от удаления из обычного декартова дерева.

● Сумма/минимум и т.п. на отрезке.

Во-первых, для каждой вершины создадим дополнительное поле f в структуре item, в котором будет храниться значение целевой функции для поддерева этой вершины. Такое поле легко поддерживать, для этого надо поступить аналогично поддержке размеров cnt (создать функцию, вычисляющую значение этого поля, пользуясь его значениями для сыновей, и вставить вызовы этой функции в конце всех функций, меняющих arbre). Во-вторых, нам надо научиться отвечать на запрос на произвольном отрезке [A;B]. Научимся выделять из дерева его часть, соответствующую отрезку [A;B]. Нетрудно понять, что для этого достаточно сначала вызвать split (t, t1, t2, A), а затем split (t2, t2, t3, B-A+1). В результате arbre t2 и будет состоять из всех elementов в отрезке [A;B], и только них. Следовательно, ответ на запрос будет находиться в поле f вершины t2. После ответа на запрос arbre надо восстановить вызовами merge (t, t1, t2) и merge (t, t, t3).

● Прибавление/покраска на отрезке.

Здесь мы поступаем аналогично предыдущему пункту, но вместо поля f будем хранить поле add, которое и будет содержать прибавляемую величину (или величину, в которую красят всё подarbre этой вершины). Перед выполнением любой операции эту величину add надо "протолкнуть" - т.е. соответствующим образом изменить t- l->add и t->r->add, а у себя значение add снять. Тем самым мы добьёмся того, что ни при каких изменениях дерева информация не будет потеряна.

● Переворот на отрезке.

Этот пункт почти аналогичен предыдущему - нужно ввести поле bool rev, которое ставить в true, когда it is required произвести переворот в поддереве текущей вершины. "Проталкивание" поля rev заключается в том, что мы обмениваем местами сыновья текущей вершины, и ставим этот флаг для них. Implémentation. Приведём для Exempleа полную реализацию неявного декартова дерева с переворотом на отрезке. Здесь для каждой вершины также хранится поле value - собственно значение elementа, стоящего в tableauе на текущей позиции. Приведена также Implémentation функции output(), которая выводит tableau, соответствующий текущему состоянию неявного декартова дерева.

typedef struct item * pitem;

struct item {

int prior, value, cnt;

bool rev;

pitem l, r;

};

int cnt (pitem it) {

return it ? it->cnt : 0;

}

void upd_cnt (pitem it) {

if (it)

it->cnt = cnt(it->l) + cnt(it->r) + 1;

}

void push (pitem it) {

if (it && it->rev) {

it->rev = false;

swap (it->l, it->r);

if (it->l)  it->l->rev ^= true;

if (it->r)  it->r->rev ^= true;

} }

void merge (pitem & t, pitem l, pitem r) {

push (l);

push (r);

if (!l || !r)

t = l ? l : r;

else if (l->prior > r->prior)

merge (l->r, l->r, r), t = l;

else

merge (r->l, l, r->l), t = r;

upd_cnt (t);

}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {

if (!t)

return void( l = r = 0 );

push (t);

int cur_key = add + cnt(t->l);

if (key <= cur_key)

split (t->l, l, t->l, key, add), r = t;

else

split (t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t;

upd_cnt (t);

}

void reverse (pitem t, int l, int r) {

pitem t1, t2, t3;

split (t, t1, t2, l);

split (t2, t2, t3, r-l+1);

t2->rev ^= true;

merge (t, t1, t2);

merge (t, t, t3);

}

void output (pitem t) {

if (!t)  return;

push (t);

output (t->l);

printf ("%d ", t->value);

output (t->r);

}

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct item {
            int key, prior;
            item * l, * r;
            item() { }
            item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
    };
    typedef item * pitem;
    void split (pitem t, int key, pitem & l, pitem & r) {
            if (!t)
                    l = r = NULL;
            else if (key < t->key)
                    split (t->l, key, l, t->l),  r = t;
            else
                    split (t->r, key, t->r, r),  l = t;
    }
    void insert (pitem & t, pitem it) {
            if (!t)
                    t = it;
            else if (it->prior > t->prior)
                    split (t, it->key, it->l, it->r),  t = it;
            else
                    insert (it->key < t->key ? t->l : t->r, it);
    }
    void merge (pitem & t, pitem l, pitem r) {
            if (!l || !r)
                    t = l ? l : r;
            else if (l->prior > r->prior)
                    merge (l->r, l->r, r),  t = l;
            else
                    merge (r->l, l, r->l),  t = r;
    }
    void erase (pitem & t, int key) {
            if (t->key == key)
                    merge (t, t->l, t->r);
            else
                    erase (key < t->key ? t->l : t->r, key);
    }
    pitem unite (pitem l, pitem r) {
            if (!l || !r)  return l ? l : r;
            if (l->prior < r->prior)  swap (l, r);
            pitem lt, rt;
            split (r, l->key, lt, rt);
            l->l = unite (l->l, lt);
            l->r = unite (l->r, rt);
            return l;
    }
    int cnt (pitem t) {
            return t ? t->cnt : 0;
    }
    void upd_cnt (pitem t) {
            if (t)
                    t->cnt = 1 + cnt(t->l) + cnt (t->r);
    }
    void merge (pitem & t, pitem l, pitem r) {
            if (!l || !r)
                    t = l ? l : r;
            else if (l->prior > r->prior)
                    merge (l->r, l->r, r),  t = l;
            else
                    merge (r->l, l, r->l),  t = r;
            upd_cnt (t);
    }
    void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
            if (!t)
                    return void( l = r = 0 );
            int cur_key = add + cnt(t->l); // вычисляем неявный ключ
            if (key <= cur_key)
                    split (t->l, l, t->l, key, add),  r = t;
            else
                    split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
            upd_cnt (t);
    }
    typedef struct item * pitem;
    struct item {
            int prior, value, cnt;
            bool rev;
            pitem l, r;
    };
    int cnt (pitem it) {
            return it ? it->cnt : 0;
    }
    void upd_cnt (pitem it) {
            if (it)
                    it->cnt = cnt(it->l) + cnt(it->r) + 1;
    }
    void push (pitem it) {
            if (it && it->rev) {
                    it->rev = false;
                    swap (it->l, it->r);
                    if (it->l)  it->l->rev ^= true;
                    if (it->r)  it->r->rev ^= true;
            }
    }
    void merge (pitem & t, pitem l, pitem r) {
            push (l);
            push (r);
            if (!l || !r)
                    t = l ? l : r;
            else if (l->prior > r->prior)
                    merge (l->r, l->r, r),  t = l;
            else
                    merge (r->l, l, r->l),  t = r;
            upd_cnt (t);
    }
    void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
            if (!t)
                    return void( l = r = 0 );
            push (t);
            int cur_key = add + cnt(t->l);
            if (key <= cur_key)
                    split (t->l, l, t->l, key, add),  r = t;
            else
                    split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
            upd_cnt (t);
    }
    void reverse (pitem t, int l, int r) {
            pitem t1, t2, t3;
            split (t, t1, t2, l);
            split (t2, t2, t3, r-l+1);
            t2->rev ^= true;
            merge (t, t1, t2);
            merge (t, t, t3);
    }
    void output (pitem t) {
            if (!t)  return;
            push (t);
            output (t->l);
            Console.Write ("%d ", t->value);
            output (t->r);
    }
}

struct item {
        int key, prior;
        item * l, * r;
        item() { }
        item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item * pitem;
void split (pitem t, int key, pitem & l, pitem & r) {
        if (!t)
                l = r = NULL;
        else if (key < t->key)
                split (t->l, key, l, t->l),  r = t;
        else
                split (t->r, key, t->r, r),  l = t;
}
void insert (pitem & t, pitem it) {
        if (!t)
                t = it;
        else if (it->prior > t->prior)
                split (t, it->key, it->l, it->r),  t = it;
        else
                insert (it->key < t->key ? t->l : t->r, it);
}
void merge (pitem & t, pitem l, pitem r) {
        if (!l || !r)
                t = l ? l : r;
        else if (l->prior > r->prior)
                merge (l->r, l->r, r),  t = l;
        else
                merge (r->l, l, r->l),  t = r;
}
void erase (pitem & t, int key) {
        if (t->key == key)
                merge (t, t->l, t->r);
        else
                erase (key < t->key ? t->l : t->r, key);
}
pitem unite (pitem l, pitem r) {
        if (!l || !r)  return l ? l : r;
        if (l->prior < r->prior)  swap (l, r);
        pitem lt, rt;
        split (r, l->key, lt, rt);
        l->l = unite (l->l, lt);
        l->r = unite (l->r, rt);
        return l;
}
int cnt (pitem t) {
        return t ? t->cnt : 0;
}
void upd_cnt (pitem t) {
        if (t)
                t->cnt = 1 + cnt(t->l) + cnt (t->r);
}
void merge (pitem & t, pitem l, pitem r) {
        if (!l || !r)
                t = l ? l : r;
        else if (l->prior > r->prior)
                merge (l->r, l->r, r),  t = l;
        else
                merge (r->l, l, r->l),  t = r;
        upd_cnt (t);
}
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
        if (!t)
                return void( l = r = 0 );
        int cur_key = add + cnt(t->l); // вычисляем неявный ключ
        if (key <= cur_key)
                split (t->l, l, t->l, key, add),  r = t;
        else
                split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
        upd_cnt (t);
}
typedef struct item * pitem;
struct item {
        int prior, value, cnt;
        bool rev;
        pitem l, r;
};
int cnt (pitem it) {
        return it ? it->cnt : 0;
}
void upd_cnt (pitem it) {
        if (it)
                it->cnt = cnt(it->l) + cnt(it->r) + 1;
}
void push (pitem it) {
        if (it && it->rev) {
                it->rev = false;
                swap (it->l, it->r);
                if (it->l)  it->l->rev ^= true;
                if (it->r)  it->r->rev ^= true;
        }
}
void merge (pitem & t, pitem l, pitem r) {
        push (l);
        push (r);
        if (!l || !r)
                t = l ? l : r;
        else if (l->prior > r->prior)
                merge (l->r, l->r, r),  t = l;
        else
                merge (r->l, l, r->l),  t = r;
        upd_cnt (t);
}
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
        if (!t)
                return void( l = r = 0 );
        push (t);
        int cur_key = add + cnt(t->l);
        if (key <= cur_key)
                split (t->l, l, t->l, key, add),  r = t;
        else
                split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
        upd_cnt (t);
}
void reverse (pitem t, int l, int r) {
        pitem t1, t2, t3;
        split (t, t1, t2, l);
        split (t2, t2, t3, r-l+1);
        t2->rev ^= true;
        merge (t, t1, t2);
        merge (t, t, t3);
}
void output (pitem t) {
        if (!t)  return;
        push (t);
        output (t->l);
        printf ("%d ", t->value);
        output (t->r);
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct item {
            int key, prior;
            item * l, * r;
            item() { }
            item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
    };
    typedef item * pitem;
    void split (pitem t, int key, pitem & l, pitem & r) {
            if (!t)
                    l = r = NULL;
            else if (key < t->key)
                    split (t->l, key, l, t->l),  r = t;
            else
                    split (t->r, key, t->r, r),  l = t;
    }
    void insert (pitem & t, pitem it) {
            if (!t)
                    t = it;
            else if (it->prior > t->prior)
                    split (t, it->key, it->l, it->r),  t = it;
            else
                    insert (it->key < t->key ? t->l : t->r, it);
    }
    void merge (pitem & t, pitem l, pitem r) {
            if (!l || !r)
                    t = l ? l : r;
            else if (l->prior > r->prior)
                    merge (l->r, l->r, r),  t = l;
            else
                    merge (r->l, l, r->l),  t = r;
    }
    void erase (pitem & t, int key) {
            if (t->key == key)
                    merge (t, t->l, t->r);
            else
                    erase (key < t->key ? t->l : t->r, key);
    }
    pitem unite (pitem l, pitem r) {
            if (!l || !r)  return l ? l : r;
            if (l->prior < r->prior)  swap (l, r);
            pitem lt, rt;
            split (r, l->key, lt, rt);
            l->l = unite (l->l, lt);
            l->r = unite (l->r, rt);
            return l;
    }
    int cnt (pitem t) {
            return t ? t->cnt : 0;
    }
    void upd_cnt (pitem t) {
            if (t)
                    t->cnt = 1 + cnt(t->l) + cnt (t->r);
    }
    void merge (pitem & t, pitem l, pitem r) {
            if (!l || !r)
                    t = l ? l : r;
            else if (l->prior > r->prior)
                    merge (l->r, l->r, r),  t = l;
            else
                    merge (r->l, l, r->l),  t = r;
            upd_cnt (t);
    }
    void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
            if (!t)
                    return void( l = r = 0 );
            int cur_key = add + cnt(t->l); // вычисляем неявный ключ
            if (key <= cur_key)
                    split (t->l, l, t->l, key, add),  r = t;
            else
                    split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
            upd_cnt (t);
    }
    typedef struct item * pitem;
    struct item {
            int prior, value, cnt;
            boolean rev;
            pitem l, r;
    };
    int cnt (pitem it) {
            return it ? it->cnt : 0;
    }
    void upd_cnt (pitem it) {
            if (it)
                    it->cnt = cnt(it->l) + cnt(it->r) + 1;
    }
    void push (pitem it) {
            if (it && it->rev) {
                    it->rev = false;
                    swap (it->l, it->r);
                    if (it->l)  it->l->rev ^= true;
                    if (it->r)  it->r->rev ^= true;
            }
    }
    void merge (pitem & t, pitem l, pitem r) {
            push (l);
            push (r);
            if (!l || !r)
                    t = l ? l : r;
            else if (l->prior > r->prior)
                    merge (l->r, l->r, r),  t = l;
            else
                    merge (r->l, l, r->l),  t = r;
            upd_cnt (t);
    }
    void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
            if (!t)
                    return void( l = r = 0 );
            push (t);
            int cur_key = add + cnt(t->l);
            if (key <= cur_key)
                    split (t->l, l, t->l, key, add),  r = t;
            else
                    split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
            upd_cnt (t);
    }
    void reverse (pitem t, int l, int r) {
            pitem t1, t2, t3;
            split (t, t1, t2, l);
            split (t2, t2, t3, r-l+1);
            t2->rev ^= true;
            merge (t, t1, t2);
            merge (t, t, t3);
    }
    void output (pitem t) {
            if (!t)  return;
            push (t);
            output (t->l);
            System.out.print ("%d ", t->value);
            output (t->r);
    }
}