A. Кролики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
У Айбара есть сад, который состоит из KK подряд идущих грядок. В саду живут nn кроликов. Каждый кролик находится в одной из грядок. Иногда кролики могут переходить в соседние грядки. Также, иногда Айбару нужно узнать количество кроликов, которые находятся на каком-то отрезке, чтобы их покормить. Айбару дано qq запросов, которые надо обработать. Они бывают следующих типов:
- Кролик номер x(1≤x≤n)x(1≤x≤n) перешел на одну грядку налево или направо. При этом гарантируется, что кролик не выйдет за пределы сада
- Посчитать количество кроликов на отрезке от грядки ll до грядки rr (1≤l≤r≤K)(1≤l≤r≤K) включительно.
Входные данные
В первой строке входных данных даны два числа - nn и KK. Далее во второй строке указаны nn чисел - изначальное положение каждого кролика. Затем в отдельной строке следует число qq и qq строк описывающих запросы. Запросы задаются в следующем формате:
- L xL x - сдвинуть кролика номер xx на одну грядку налево
- R xR x - сдвинуть кролика номер xx на одну грядку направо
- G lrG lr - Посчитать и вывести количество кроликов на отрезке от грядки ll до грядки rr включительно.
Выходные данные
В выходные данные выведите по одному числу для каждого запроса третьего типа в отдельной строке.
Система оценки
Подзадача 1 (20 баллов) — 1≤n, K, q≤10001≤n, K, q≤1000
Подзадача 2 (20 баллов) — 1≤n, K, q≤5∗1051≤n, K, q≤5∗105, отсутствуют запросы сдвига кролика
Подзадача 3 (60 баллов) — 1≤n, K, q≤5∗105
как можно решить задачу? Я пробовал через дерево отрезков но зашло только на 20 баллов