Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача J. (20081225) Динамический массив

Автор:Жюри зимних сборов 2009   Ограничение времени:30 сек
Входной файл:dynarray.in   Ограничение памяти:512 Мб
Выходной файл:dynarray.out  
Максимальный балл:100  

Условие

Требуется реализовать структуру данных, которая представляет из себя динамический массив, поддерживающий следующие операции:

Элементы массива нумеруются с единицы.

Формат входного файла

В первой строке находятся два натуральных числа n и m — начальное количество элементов в массиве и количество операций (1n200000, 1m200000). Во второй строке находится n целых чисел a1, a2, , an  — элементы исходного массива (0ai106). Следующие m строк содержат описания операций в формате "1 u p" (u1, u не превосходит текущего размера массива, 0p106), "2 u p" (u0, u не превосходит текущего размера массива, 0p106) или "3 u v p" (1uv, v не превосходит текущего размера массива, 0p106).

Формат выходного файла

В выходном файле должны находиться ответы на запросы  — по одному в строке.

Примеры тестов

Входной файл (dynarray.in) Выходной файл (dynarray.out)
1
5 5
1 3 5 4 2
3 2 4 4
1 3 3
3 2 4 4
2 2 10
3 2 4 4
2
3
2

0.029s 0.004s 13