Задача на структуры данных, которую можно решить каким-нибудь из деревьев или sqrt-декомпозицией. Я же хочу показать ещё один вариант sqrt-декомпозиции (как метода, а не структуры данных). Давайте читать условие:
Простое решение заключается в том, чтобы каждый раз перестраивать индекс. Такое точно не пройдёт по времени. Идея sqrt-декомпозиции заключается в том, чтобы перестраивать индекс лишь каждые N шагов. А между перестройками хранить историю изменений и получать ответ, просматривая и индекс, и накопленную историю.
N можно найти исходя из алгоритмической сложности каждой из операций (поиск ответа и перестройка индекса), но чаще всего получается квадратный корень. Отсюда и следует название метода.
Итак, нам понадобятся два массива - текущий индекс (то есть для каждого числа его позиция в таблице) и накопленная история запросов (и изменений таблицы). Всё будем нумеровать с 0, поэтому в решении будут встречаться преобразования +1 и -1:
Основные манипуляции с данными вынесем в отдельные функции, поэтому само решение будет выглядеть очень простым:
Здесь мы выводим ответы не сразу, а складываем их в список и потом выводим оптом (говорят, что так быстрее). Забегая вперёд, можно заметить, что перестроение индекса выполняется каждые 300 итераций.
Теперь напишем функцию get_index. Для заданного числа возможны два варианта:
- его уже запрашивали после последней перестройки индекса. Тогда его позиция будет равна числу различных элементов в истории запросов после него,
- иначе. Тогда его позиция будет равна его позиции в текущем индексе плюс число различных элементов в истории, чья позиция в индексе больше.
Так надо разделять элементы, которые стоят в индексе позже, заведём два множества:
Дальше пройдём по истории запросов с конца (чтобы корректно обработать первый случай, ведь запрашиваемый элемент может встречаться в истории несколько раз) и будем поддерживать множества:
Если встречаем запрашиваемый элемент, то сразу выводим ответ. Если же дошли до конца, то обрабатываем второй вариант. Время работы этой функции O(N).
Перестроение индекса выполним в два этапа. Сначала текущий индекс преобразуем в вид истории запросов. То есть выстроим элементы так, что выполнив запросы в таком порядке получим текущий индекс:
И теперь можно пройтись по совместной истории запросов с конца и построить новый индекс:
Позиция каждого элемента в индексе равна числу различных элементов, встречающихся в истории запросов после него. Для этого мы поддерживаем множество со всеми встреченными элементами.
Время работы этой функции равно O(n). И тогда общее время работы программы составит: m * O(N) + O(n) * m / N. Чтобы минимизировать эту функцию надо взять производную и найти её корни. Так и получаем корень из n. Для самого большого теста это будет 256, поэтому можно поиграть вокруг него.
Однако для Python это слишком много, поэтому по времени оно точно не пройдёт. А на PyPy это решение не заходит по памяти. Поэтому давайте накинем немного жести, чтобы затолкать это решение.
Оптимизация решения по памяти
Чтобы не утруждать сборщик мусора в PyPy, избавимся от всех динамически расширяемых структур данных и перейдём к жёстко зафиксированным массивам. Например для history точно знаем размер, а количество элементов будем поддерживать в отдельной переменной l:
Тогда основное решение изменится лишь в паре строк:
Немного сложнее обходится поддержка множеств. Можно в массиве отмечать единичками элементы, которые уже встретились, но тогда будут накладные расходы на обнуление всех значений.
Поэтому воспользуемся трюком с эпохами. В нашем случае эпоха будет равна номеру запроса. А в массиве будем ставить не единичку, а номер текущей эпохи. Тогда проверка наличия элемента в множестве будет эквивалентна проверке равенства его эпохи текущей:
Здесь в переменной cnt поддерживаем количество встреченных элементов. Работа с массивом history тоже немного изменилась. Например очистка теперь происходит занулением одной переменной.
И аналогичные действия проворачиваем в функции get_index и её двумя списками:
Теперь PyPy нет необходимости выделять и очищать память в ходе работы программы (все основные объёмы выделяются на самом старте) и решение спокойно укладывается в ограничения.
Предыдущий выпуск: Задача 631. Отгадай число
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.