Очередь за кымызом


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

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

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

У киоска с кымызом в Чолпон-Ате стоит очередь из n человек, у человека i в кошельке a[i] сомов. Кассир наблюдает за очередью и записывает события:

  • 1 l r — люди с l-го по r-й (считая от начала очереди) поссорились и встали в обратном порядке;
  • 2 p x — после p-го человека в очередь встал новый человек с x сомами (p = 0 — в самое начало);
  • 3 p — p-й человек ушёл из очереди;
  • 4 l r — запрос: сколько денег у людей с l-го по r-й вместе;
  • 5 l r — запрос: сколько денег у самого богатого из людей с l-го по r-й.

Рисунок

Гарантируется, что все номера в событиях корректны для текущей очереди и очередь никогда не становится пустой.

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

В первой строке — n и q (1 ≤ n, q ≤ 2 · 10⁵). Во второй — n чисел a[i] (0 ≤ a[i] ≤ 10⁹). В каждой из следующих q строк — событие (0 ≤ x ≤ 10⁹).

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

Для каждого запроса 4 и 5 выведите ответ в отдельной строке.

Пример 1

Вход:

5 6
3 1 4 1 5
1 1 3
2 0 9
4 1 3
3 2
1 1 5
5 1 2

Выход:

14
5

Пояснение

Очередь 3 1 4 1 5. После разворота людей 1…3 она становится 4 1 3 1 5, после 2 0 9 — 9 4 1 3 1 5, и сумма у людей 1…3 равна 14. После ухода второго (3 2) очередь 9 1 3 1 5, после разворота 1…5 — 5 1 3 1 9, и максимум у людей 1…2 равен 5.

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

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n, q ≤ 1000.

Подсказка

Декартово дерево по неявному ключу поддерживает разрезания, склейки и отложенный разворот.


Комментарии

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