printРабочее место участника

printЗадачи

1723. Окончательная структура

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Мирко устал от реализации всевозможных видов структур данных для разных задач. И он решил получить окончательную структуру, которая позволит ему управлять любимой последовательностью чисел. Помогите ему!
Мирко даст вам последовательность чисел и последовательность запросов, которые вы должны выполнить. Каждый запрос или запрашивает информацию, или изменяет существующую последовательность. Возможные типы запросов перечислены ниже.
Тип запросаОписаниеПример
`1\ A\ B\ X`Заменить все элементы с номерами в диапазоне от `A` до `B` (включительно) на `X`(9, 8, 7, 6, 5, 4, 3, 2, 1)
1 3 5 0
(9, 8, 0, 0, 0, 4, 3, 2, 1)
`2\ A\ B\ X`Добавить `X` к элементу с номером `A`, `2*X` – к `(A+1)`-му, …, `(B-A+1)*X` – к `B`-му(9, 8, 7, 6, 5, 4, 3, 2, 1)
2 3 5 2
(9, 8, 9, 10, 11, 4, 3, 2, 1)
`3\ C\ X`Вставить новый элемент со значением `X` перед элементом с номером `C`(9, 8, 7, 6, 5, 4, 3, 2, 1)
3 4 100
(9, 8, 7, 100, 6, 5, 4, 3, 2, 1)
`4\ A\ B`Найти сумму элементы с номерами в диапазоне от `A` до `B` (включительно)(2, 18, 7, 6, 1, 4, 7, 7, 2)
4 6 7
Результат: 11
Первая строка ввода содержит два целых числа – начальная длина последовательности `N` и количество запросов `Q` (`1\ ≤\ N,\ Q\ ≤\ 100\ 000`). Следующая строка содержит начальную последовательность. Последовательность состоит из неотрицательных целых чисел, не превсходящих `100\ 000`, разделенных одним пробелом. Следующие строки содержат `Q` запросов в формате, описанном выше. Во всех запросах `1\ ≤\ X\ ≤\ 100`, `1\ ≤\ A\ ≤\ B\ ≤\ "текущей"\ "длины"\ "последовательности"` и `1\ ≤\ C\ ≤\ "текущей"\ "длины"\ "последовательности"\ +1`.
Для каждого запроса типа 4 вывести одну строку, содержащую запрашиваемую сумму. Примечание: обратите внимание, что некоторые суммы не будут помещаться в 32-битный целый тип данных.

Пример ввода 1

5 5 
1 2 3 4 5 
1 5 5 0 
4 4 5 
4 5 5 
2 1 5 1 
4 1 5 

Пример вывода 1

4 
0 
25 

Пример ввода 2

1 7 
100 
3 1 17 
3 2 27 
3 4 37 
4 1 1 
4 2 2 
4 3 3 
4 4 4 

Пример вывода 2

17 
27 
100 
37 
Источник: COCI 2010/2011 Contest #7
loading