Областная олимпиада по информатике 2020 год, 9-11 классы


Задача A. Кролики

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

У Айбара есть сад, который состоит из $K$ подряд идущих грядок. В саду живут $n$ кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано $q$ запросов, которые надо обработать. Они бывают следующих типов:
Формат входного файла
В первой строке входных данных даны два числа - $n$ и $K$. \\ Далее во второй строке указаны $n$ чисел - изначальное положение каждого кролика.\\ Затем в отдельной строке следует число $q$ и $q$ строк описывающих запросы. Запросы задаются в следующем формате:
Формат выходного файла
В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.
Система оценки
Подзадача 1 (20 баллов) — $1 <= n, K, q <= 1000$ Подзадача 2 (20 баллов) — $1 <= n, K, q <= 5 * 10^5$, отсутствуют запросы сдвига кролика Подзадача 3 (60 баллов) — $1 <= n, K, q <= 5 * 10^5$
Пример:
Вход
3 10
4 2 8
4
G 3 7
R 2
L 3
G 3 7
Ответ
1
3
( Sanjar Bidaibek )
посмотреть в олимпиаде

Комментарий/решение:

  0
2020-01-13 16:26:21.0 #

показать/скрыть код

  -1
2020-04-24 19:31:29.0 #

показать/скрыть код

  0
2020-07-28 13:49:48.0 #

Дерево отрезков ;)

показать/скрыть код

  0
2020-11-03 11:25:12.0 #

Кому интересно это решение через Дерево Фенвика!

показать/скрыть код