В этой задаче вам надо реализовать структуру данных исторический массив. Исторический массив изначально имеет размер n и заполнен нулями. Он поддерживает следующие операции:
- set(index, value) - присвоить элементу на позиции i значение value;
- begin_new_era(era_id) - эта операция начинает новую эру с номером era_id. В каждый момент времени активна единственная эра. Изначальная эра имеет индекс era_id = 0. Когда начинается новая эра, предыдущая заканчивается.
- get(index, era_id) - получить значение элемента на позиции index на момент окончания эры era_id.
В первой строке дан размер исторического массива n (1 ≤ n ≤ 100000).
Во второй строке дано число операций, производимых с массивом, — q (1 ≤ q ≤ 100000)
В следующих q строках даны операции по одной в строке. Есть три вида операций:
- set index value (0 ≤ index ≤ n−1,0 ≤ value ≤ 109)
- begin_new_era era_id (1 ≤ era_id ≤ 109)
- get index era_id (0 ≤ index ≤ n−1,0 ≤ era_id ≤ 109)
Гарантируется, что при запросе значения из конкретной эры эта эра уже успела закончиться.
Гарантируется, что при создании эры с идентификатором era_id этот индентификатор еще не был использован.
На каждую операцию третьего типа необходимо вывести на отдельной строке значение, которое содержал элемент массива с номером index на момент окончания эры era_id.
|
6 9 set 0 3 set 1 8 begin_new_era 6000 get 0 0 get 1 0 set 0 9 begin_new_era 1000000 get 0 6000 get 0 0 |
3 8 9 3 |
|
1 12 set 0 1 set 0 2 begin_new_era 1000 set 0 4 set 0 100 begin_new_era 666 set 0 7 set 0 42 begin_new_era 424242 get 0 0 get 0 666 get 0 1000 |
2 42 100 |