Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1723. Окончательная структура
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 21/04/2012 | Занятие 15 (D) |
| 05/03/2014 | Занятие 15 (E) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мирко устал от реализации всевозможных видов структур данных для разных задач.
И он решил получить
окончательную структуру, которая позволит ему управлять любимой последовательностью чисел.
Помогите ему!
Мирко даст вам последовательность чисел и последовательность запросов, которые вы должны выполнить.
Каждый запрос или запрашивает информацию, или изменяет существующую последовательность.
Возможные типы запросов перечислены ниже.
| Тип запроса | Описание | Пример |
| 1 | Заменить все элементы с номерами в диапазоне от 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
