Есть задача: необходимо перемещать некоторый отрезок массива размера N
в его начало.
Например, есть
Массив А - { 1, 6, 3, 4, 5, 2 }.
Отрезок - [3; 5].
Результатом будет { 3, 4, 5, 1, 6, 2 }.
Т.е. элементы массива с индексами от 3 до 5 перемещаются в начало, а остальные элементы (что были до отрезка и после) приписываются дальше.
Необходимо уметь отвечать на M
таких запросов. Каждый запрос происходит на массиве, полученном в предыдущем запросе.
Время ответа на запрос должно быть не хуже логарифмического от N (можно и лучше).
Пытался решать с помощью односвязного списка. Перемещение происходит за О(1), но долгий поиск границ запроса - О(N).
Возможно, есть какая-то подходящая структура данных.