e-olymp 2955. Персистентый массив

Условие

Задача взята отсюда.

Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:

[latex]a_i[j] = x[/latex] — создать из [latex]i[/latex]-ой версии новую, в которой [latex]j[/latex]-ый элемент равен [latex]x[/latex], а остальные элементы такие же, как в [latex]i[/latex]-ой версии.
[latex]get[/latex] [latex]a_i[j][/latex] — сказать, чему равен [latex]j[/latex]-ый элемент в [latex]i[/latex]-ой версии.

Входные данные

Количество чисел в массиве [latex]n[/latex] [latex](1 \leq n \leq 10^5)[/latex] и [latex]n[/latex] элементов массива. Далее количество запросов [latex]m[/latex] [latex](1 \leq m \leq 10^5)[/latex] и [latex]m[/latex] запросов. Формат описания запросов можно посмотреть в примере. Если уже существует [latex]k[/latex] версий, новая версия получает номер [latex]k + 1[/latex]. И исходные, и новые элементы массива — целые числа от [latex]0[/latex] до [latex]10^9[/latex]. Элементы в массиве нумеруются числами от [latex]1[/latex] до [latex]n[/latex].

Выходные данные

На каждый запрос типа [latex]get[/latex] вывести соответствующий элемент нужного массива.

Тесты

№	Входные данные	выходные данные
1	6 1 2 3 4 5 6 11 create 1 6 10 create 2 5 8 create 1 5 30 get 1 6 get 1 5 get 2 6 get 2 5 get 3 6 get 3 5 get 4 6 get 4 5	6 5 10 5 10 8 6 30
2	2 42 2048 17 create 1 1 1 create 2 2 1 create 3 2 5 create 3 1 4 create 5 2 6 get 1 1 get 1 2 get 2 1 get 2 2 get 3 1 get 3 2 get 4 1 get 4 2 get 5 1 get 5 2 get 6 1 get 6 2	42 2048 1 2048 1 1 1 5 4 1 4 6

Код

#include <iostream>
#include <vector>
using namespace std;

struct Node
{
    Node* lchild;
    Node* rchild;
    int val;
};

void build(Node* node, int* base, int l, int r)
{
    if (l == r)
        node->val = base[l-1]; //дерево пронумеровано с единицы
    else
    {
        int m = (l + r) / 2;
        node->lchild = new Node();
        build(node->lchild, base, l, m);
        node->rchild = new  Node();
        build(node->rchild, base, m + 1, r);
    }
}

void add(Node* to, Node* from, int l, int r, int npos, int nv)
{
    if (l == r)
        to->val = nv;
    else
    {
        int m = (l + r) / 2;
        if (npos <= m)
        {
            to->rchild = from->rchild;
            Node* left = new Node();
            add(left, from->lchild, l, m, npos, nv);
            to->lchild = left;
        }
        else
        {
            to->lchild = from->lchild;
            Node* right = new Node();
            add(right, from->rchild, m + 1, r, npos, nv);
            to->rchild = right;
        }
    }
}

int get(Node* node, int l, int r, int pos)
{
    if (l == r)
        return node->val;
    else
    {
        int m = (l + r) / 2;
        if (pos <= m)
            return get(node->lchild, l, m, pos);
        else
            return get(node->rchild, m + 1, r, pos);
    }
}

int main() 
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int base[n];
    for (int i = 0; i < n; i++)
        cin >> base[i];
    vector<Node*> versions;
    versions.push_back(new Node());
    build(versions.at(0), base, 1, n);
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        string s;
        cin >> s;
        if (s == "create")
        {
            int rootPos, newPos, newVal;
            cin >> rootPos >> newPos >> newVal;
            versions.push_back(new Node());
            add(versions.back(), versions.at(rootPos-1), 1, n, newPos, newVal);
        }
        else
        {
            int rootPos, valPos;
            cin >> rootPos >> valPos;
            cout << get(versions.at(rootPos-1), 1, n, valPos) << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct Node

{

Node* lchild;

Node* rchild;

int val;

};

void build(Node* node, int* base, int l, int r)

{

if (l == r)

node->val = base[l-1]; //дерево пронумеровано с единицы

else

{

int m = (l + r) / 2;

node->lchild = new Node();

build(node->lchild, base, l, m);

node->rchild = new Node();

build(node->rchild, base, m + 1, r);

}

void add(Node* to, Node* from, int l, int r, int npos, int nv)

{

if (l == r)

to->val = nv;

else

{

int m = (l + r) / 2;

if (npos <= m)

{

to->rchild = from->rchild;

Node* left = new Node();

add(left, from->lchild, l, m, npos, nv);

to->lchild = left;

}

else

{

to->lchild = from->lchild;

Node* right = new Node();

add(right, from->rchild, m + 1, r, npos, nv);

to->rchild = right;

}

int get(Node* node, int l, int r, int pos)

{

if (l == r)

return node->val;

else

{

int m = (l + r) / 2;

if (pos <= m)

return get(node->lchild, l, m, pos);

else

return get(node->rchild, m + 1, r, pos);

}

int main()

{

ios::sync_with_stdio(false);

int n;

cin >> n;

int base[n];

for (int i = 0; i < n; i++)

cin >> base[i];

vector<Node*> versions;

versions.push_back(new Node());

build(versions.at(0), base, 1, n);

int k;

cin >> k;

for (int i = 0; i < k; i++)

{

string s;

cin >> s;

if (s == "create")

{

int rootPos, newPos, newVal;

cin >> rootPos >> newPos >> newVal;

versions.push_back(new Node());

add(versions.back(), versions.at(rootPos-1), 1, n, newPos, newVal);

}

else

{

int rootPos, valPos;

cin >> rootPos >> valPos;

cout << get(versions.at(rootPos-1), 1, n, valPos) << endl;

}

return 0;

}

Решение

Для решения задачи воспользуемся так называемым Персистентным Деревом Отрезков — т.е. деревом, «помнящим» историю своих изменений. Дерево будем хранить не с помощью массива а на указателях — используя структуру типа «узел».

struct Node
{
Node* lchild;
Node* rchild;
int val;
};

struct Node

{

Node* lchild;

Node* rchild;

int val;

};

(Тут [latex]lchild[/latex] и [latex]rchild[/latex] — ссылки на левый и правый поддеревья соответственно, а [latex]val[/latex] — значение, хранящееся в узле.)

Замечание: тут и далее под левым подотрезком отрезка [latex][l, l + 1, \ldots, m, m + 1, \ldots, r — 1, r][/latex], [latex]m = \lfloor\frac{l + r}{2}\rfloor[/latex] подразумевается отрезок [latex][l, \ldots, m][/latex] а под правым — [latex][m + 1, \ldots, r][/latex].

Заведем вектор-хранилище корней дерева [latex]versions[/latex] (об этом позднее). Для начала занесем туда 1 элемент — корень изначального дерева, и построим на нем дерево из элементов массива. Вопрос в том, какую информацию хранить в вершинах дерева? Оказывается, достаточно хранить в листьях элементы массива, а остальные узлы заполнять ни чем не надо — исходя из условия, запросы будут только к конкретным элементам массива. Рекурсивная процедура построения дерева стандартна, отличается только технической реализацией (вместо номеров вершин передаем ссылки на необходимые нам узлы) — рекурсивно создаем у текущего узла [latex]lchild[/latex] и [latex]rchild[/latex] и вызываем функцию построения для них, пока длина отрезка, за который они отвечают, не станет равна единице. Тогда присваиваем полю [latex]val[/latex] этого узла значение соотв. элемента массива.

Например, для массива {[latex]1, 2, 3, 4, 5, 6[/latex]} в результате построения мы получим следующую структуру (где на самом деле значения хранятся только на отрезках длины [latex]1[/latex], для остальных узлов подотрезки массива, отвечающие им, только подразумеваются).

Теперь разберемся, как эффективно создавать новые версии массива. Пусть у нас уже есть [latex]k[/latex] версий массива и мы хотим создать из [latex]i[/latex]-й [latex](k+1)[/latex]-ю. Для начала добавим в хранилище новый узел-корень, отвечающий данной версии.

Теперь рассуждаем так: допустим, элемент, который надо поменять, находиться в правом подотрезке (для левого, рассуждения будут симметричны). Левые подотрезки идентичны, тогда просто присваиваем [latex]lchild[/latex] нового узла ссылку на [latex]lchild[/latex] исходного. Правые будут отличаться. Тогда создаем у нового узла [latex]rchild[/latex], и проводим те же размышления относительного правого подотрезка, [latex]rchild[/latex]-ов исходного и нового узлов, повторяя это до тех пор, пока мы не придем в лист дерева, тогда просто присвоим этому новому узлу требуемое значение. Получаем несложный рекурсивный алгоритм функции void add(Node* to, Node* from, int l, int r, int npos, int nv);

Для наглядности, рассмотрим пример с тем же массивом. Пусть сперва нас просят выполнить create 1 6 42 — создать из первой версии новую, где шестой элемент равен [latex]42[/latex], а затем create 2 4 667 — создать новую уже из второй, где [latex]4[/latex]-й элемент равен [latex]667[/latex]. Вот, что мы получим в результате (черный цвет — первая версия, красный — вторая, синий — третья):

Рассмотрим, как получилась вторая версия. Создаем корень {[latex]1, 2, 3, 4, 5, 42[/latex]}. Необходимый нам элемент в правом подотрезке. Тогда [latex]lchild[/latex] нового корня будет ссылаться на [latex]lchild[/latex] исходного, а [latex]rchild[/latex] {[latex]4, 5, 42[/latex]}. Мы создаем. Аналогично поступаем с {[latex]4, 5, 42[/latex]} относительно {[latex]4, 5, 6[/latex]}. Левое поддерево {[latex]4, 5[/latex]} — общее, создаем правое поддерево {[latex]42[/latex]} и завершаем алгоритм. Для получения третьей версии можно провести аналогичные рассуждения, но уже беря в качестве исходного дерева вторую версию.

Так как на каждом этапе отрезок делится пополам, то очевидно, что как и в стандартной реализации ДО, асимптотика этой функции будет [latex]O(\log{n})[/latex], а при создании новой версии будет создано не более чем [latex]\lceil\log_2{n}\rceil[/latex] вершин, т.е. алгоритм является достаточно эффективным как в плане времени, так и расходуемой памяти.

Осталось реализовать функцию int get(Node* node, int l, int r, int pos); Она реализуется стандартно: спускаемся по необходимой версии дерева (из нужного узла-корня в [latex]storage[/latex]), в левое или правое поддерево, пока не дойдем до необходимой нам вершины (это будет отрезок единичной длины), далее возвращаем содержимое [latex]val[/latex] этого узла. Реализация облегчается еще и тем, что запрашивают элемент — т.е. отрезок единичной длины, и не надо рассматривать случай, когда необходимый отрезок лежит частично в левом, а частично в правом поддереве.

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

Ссылки

Засчитанное решение на e-olymp.

Рабочий код на Ideone.

Замечание

Легко заметить, что в функции int get(Node* node, int l, int r, int pos); можно очень просто избавиться от рекурсии:

int get(Node* node, int l, int r, int pos)
{
    while (l != r)
    {
        int m = (l + r) / 2;
        if (pos <= m)
        {
            r = m;
            node = node->lchild;
        }
        else
        {
            l = m + 1;
            node = node->rchild;
        }
    }
    return node->val;
}