1

Есть задача: необходимо перемещать некоторый отрезок массива размера N в его начало. Например, есть

Массив А - { 1, 6, 3, 4, 5, 2 }. 

Отрезок - [3; 5]. 

Результатом будет { 3, 4, 5, 1, 6, 2 }.

Т.е. элементы массива с индексами от 3 до 5 перемещаются в начало, а остальные элементы (что были до отрезка и после) приписываются дальше.

Необходимо уметь отвечать на M таких запросов. Каждый запрос происходит на массиве, полученном в предыдущем запросе.

Время ответа на запрос должно быть не хуже логарифмического от N (можно и лучше).

Пытался решать с помощью односвязного списка. Перемещение происходит за О(1), но долгий поиск границ запроса - О(N).

Возможно, есть какая-то подходящая структура данных.

3
  • "Время ответа на запрос должно быть как минимум логарифмическим от N (можно и лучше)." Как минимум, говорите? А максимум - не ограничен, то есть можно и экспоненциальное сделать? 7 янв 2018 в 23:34
  • По идее, структуры данных для операций с логарифмической стоимостью - это деревья.
    – user239133
    7 янв 2018 в 23:54
  • @AnT, согласен, очень глупо написал. Исправил
    – 9Pasha
    8 янв 2018 в 9:43

2 ответа 2

1

Структура данных, которая решает данную задачу - Декартово дерево по неявному ключу.

Оно умеет выполнять запросы на разрезание и склеивание деревьев за O(logN)

Таким образом для того, чтобы перенести какой-то отрезок в начало, понадобится сначала разрезать дерево на три куска: Левая, середина, правая.

После чего склеить в порядке: середина, левая, правая.

Таким образом на каждый запрос уйдет O(log N)

0

А давайте добавим к списку (который легко перемещается) структуру типа map в С++ (реализуемую через черно-красное дерево), в которой каждому индексу-значению сопоставлен указатель на соответствующий элемент списка. Или вообще хеш-таблицу элементов - в которой хеширование ведется по значению, а указатель - так, сопутствующая информация. Тогда поиск нужных элементов будет идти за O(lg N) или даже за O(1), ну, и перемещение за O(1).

Указатели на элементы списка при перемещении не будут становиться некорректными, так как при перемещении меняться будут только связи между элементами.

Что-то типа:

введите сюда описание изображения

Так что если элементы в список не добавляются и не удаляются - map не меняется.

4
  • Ну я тоже думал как-то map сюда приплести, но мне не совсем понятна ваша идея. То есть изначально мы заводим map с такими парами { [1, ссылка], [2, ссылка] ... [n, ссылка] }. Ну первый запрос за О(1) можно ответить, согласен. Но после запроса у некоторых элементов массива поменяются индексы, как это отобразить в map?
    – 9Pasha
    8 янв 2018 в 9:46
  • Еще раз. Указатели (итераторы) при перемещении элементов в списке остаются валидными. Поэтому map, созданный один раз, остается корректным, как бы мы ни перетасовывали узлы в списке. Понятия "индекс" ни у map, ни у list не существует. См. картинку в ответе.
    – Harry
    8 янв 2018 в 9:55
  • Ну смотрите, вы наверное меня не так поняли. Вот ваш рисунок. Да индексы остались валидными, я этого и не опровергал. Но на втором рисунке порядок в списке стал 3 4 5 1 2, соответственно у 3-ки должен быть индекс 1, у 4 - 2 и т.д. А они остались такими же, как и были. Если использовать map так, то достаточно было завести обычный массив :) Я может не очень понятно объяснил, но по крайне мере пытался акцентировать на этом. Следующий запрос должен будет произойти на полученном массиве (списке), а поскольку соответствие индексов в map не поменялось, то я буду обращаться не к тем элементам.
    – 9Pasha
    8 янв 2018 в 10:06
  • А, я считал, что вас интересуют значения 3 и 5... Потому что элементы 3 и 5 имеют индексы 2 и 4, вот меня это и сбило.Тогда, откровенно говоря, пока что не вижу вариантов.
    – Harry
    8 янв 2018 в 10:16

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.