Автор: | Жюри зимних сборов 2009 | Ограничение времени: | 30 сек | |
Входной файл: | dynarray.in | Ограничение памяти: | 512 Мб | |
Выходной файл: | dynarray.out | |||
Максимальный балл: | 100 |
Требуется реализовать структуру данных, которая представляет из себя динамический массив, поддерживающий следующие операции:
Элементы массива нумеруются с единицы.
В первой строке находятся два натуральных числа n и m — начальное количество элементов в массиве и количество операций (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000). Во второй строке находится n целых чисел a1, a2, …, an — элементы исходного массива (0 ≤ ai ≤ 106). Следующие m строк содержат описания операций в формате "1 u p" (u ≥ 1, u не превосходит текущего размера массива, 0 ≤ p ≤ 106), "2 u p" (u ≥ 0, u не превосходит текущего размера массива, 0 ≤ p ≤ 106) или "3 u v p" (1 ≤ u ≤ v, v не превосходит текущего размера массива, 0 ≤ p ≤ 106).
В выходном файле должны находиться ответы на запросы — по одному в строке.
№ | Входной файл (dynarray.in ) |
Выходной файл (dynarray.out ) |
---|---|---|
1 |
|
|