Ряды Ошского базара


Отправить решение Решать в редакторе

Сложность: 65%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Ошский базар (Жайма-базар) — один из старейших базаров Центральной Азии: здесь торговали ещё во времена Великого шёлкового пути. Вдоль главного прохода в один ряд стоят n прилавков, пронумерованных от 1 до n. У прилавка i установлена цена a[i] сомов за килограмм товара.

Фотография
Жайма-базар в Оше. Фото: Bgag, CC0, Wikimedia Commons

Нургуль работает аналитиком в администрации базара. В течение дня к ней поступают q сообщений трёх видов:

  • 1 l r x — продавцы прилавков с l по r (включительно) одновременно меняют цены на x сомов (если x < 0, цены снижаются; цена может стать и отрицательной — это означает, что продавец доплачивает за вывоз товара);
  • 2 l r x — администрация устанавливает на прилавках с l по r единую цену x;
  • 3 l r — нужно сообщить сумму цен на прилавках с l по r и наибольшую из этих цен.

Помогите Нургуль ответить на все сообщения третьего вида.

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

В первой строке — два целых числа n и q (1 ≤ n, q ≤ 300 000).

Во второй строке — n целых чисел a[1], …, a[n] (0 ≤ a[i] ≤ 10⁹).

В каждой из следующих q строк — одно сообщение в указанном формате (1 ≤ l ≤ r ≤ n). Для сообщений первого вида |x| ≤ 10⁴, для второго вида 0 ≤ x ≤ 10⁹.

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

Для каждого сообщения третьего вида выведите в отдельной строке два числа: сумму и максимум цен на отрезке.

Пример 1

Вход:

6 6
5 3 8 1 4 2
3 2 5
1 1 3 2
3 1 6
2 3 6 7
1 4 5 -10
3 1 6

Выход:

16 8
29 10
20 7

Пояснение

После второго сообщения цены равны 7 5 10 1 4 2, после четвёртого — 7 5 7 7 7 7, после пятого — 7 5 7 −3 −3 7.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 20 n, q ≤ 3000
2 25 нет сообщений второго вида
3 55 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.

Примечание

Объём входных данных велик: используйте быстрый ввод-вывод. Сумма может не поместиться в 32-битный тип.


Комментарии

Еще нет ни одного комментария.