eolymp
Задачи

Персистентный массив

Персистентный массив

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

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

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

Количество чисел в массиве n (1 n 105) и n элементов массива. Далее количество запросов m (1 m 105) и m запросов. Формат описания запросов можно посмотреть в примере. Если уже существует k версий, новая версия получает номер k+1. И исходные, и новые элементы массива — целые числа от 0 до 109. Элементы в массиве нумеруются числами от 1 до n.

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #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