Задачи
Персистентный массив
Персистентный массив
Дан массив (вернее, первая, начальная его версия). Нужно уметь отвечать на два запроса:
a_i[j] = x — создать из i-ой версии новую, в которой j-ый элемент равен x, а остальные элементы такие же, как в i-ой версии.
get a_i[j] — сказать, чему равен j-ый элемент в i-ой версии.
Входные данные
Количество чисел в массиве n (1 ≤ n ≤ 10^5) и n элементов массива. Далее количество запросов m (1 ≤ m ≤ 10^5) и m запросов. Формат описания запросов можно посмотреть в примере. Если уже существует k версий, новая версия получает номер k+1. И исходные, и новые элементы массива — целые числа от 0 до 10^9. Элементы в массиве нумеруются числами от 1 до n.
Выходные данные
На каждый запрос типа get вывести соответствующий элемент нужного массива.
Пример
Входные данные #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
Выходные данные #1
6 5 10 5 10 8 6 30