Условие
Задача взята отсюда.
Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:
- [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 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#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; } |
Решение
Для решения задачи воспользуемся так называемым Персистентным Деревом Отрезков — т.е. деревом, «помнящим» историю своих изменений. Дерево будем хранить не с помощью массива а на указателях — используя структуру типа «узел».
|
1 2 3 4 5 6 |
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); можно очень просто избавиться от рекурсии:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
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; } |
Но, судя по результатам, это в принципе не влияет на скорость работы программы.