Кэш любого размера
Сколько памяти дать кэшу веб-сервера? Чтобы решить, хочется знать для каждого возможного размера, сколько запросов вчерашнего дня обошлись бы без диска. Кэш работает по правилу LRU: в нём помещается k страниц, и при нехватке места выбрасывается та, к которой дольше всех не обращались; вначале кэш пуст. Журнал запросов один, а размеров нужно проверить много.
Один из тестов — первые 100 000 успешных запросов к серверу Космического центра Кеннеди 13 июля 1995 года, страницы заменены номерами, и размеры от 1 до 3000.
Вход
В первой строке n (1 ≤ n ≤ 100 000). Во второй — n номеров страниц в порядке запросов, каждый от 1 до 10⁹. В третьей — q (1 ≤ q ≤ 100 000), в четвёртой — q размеров кэша k (1 ≤ k ≤ n).
Выход
Для каждого размера — строка с числом попаданий кэша этого размера на всём журнале.
Примеры
Пример 1
12 1 2 3 4 1 2 5 1 2 3 4 5 5 1 2 3 4 5
0 0 2 4 7
Пример 2
5 7 7 7 3 7 2 1 2
2 3
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Прогнать журнал через кэш каждого размера — O(n) на размер и O(nq) всего. Кэши разных размеров ведут себя по-разному, но не как попало: что лежит в кэше на k мест по сравнению с кэшем на k + 1 место?
2Подсказка 2
В кэше на k мест всегда лежат k страниц, к которым обращались последними (или все, если разных было меньше). Значит, обращение попадает в кэш на k мест ровно тогда, когда со времени прошлого обращения к этой странице спросили меньше k разных других страниц. Это число — стековое расстояние, и оно не зависит от k.
3Подсказка 3
Осталось быстро считать, сколько разных страниц спросили между двумя обращениями к одной. Отметьте единицей момент последнего обращения к каждой странице: разные страницы, спрошенные после момента p, — это отметки правее p.
4Идея
Один проход по журналу с деревом Фенвика по моментам времени. В дереве стоит единица в момент последнего обращения к каждой уже встреченной странице. При обращении в момент t к странице, которую в последний раз спрашивали в момент p, стековое расстояние равно числу единиц правее p: все встреченные страницы минус сумма префикса до p включительно. Записываем расстояние в гистограмму, переносим единицу из p в t. Кэш на k мест попадает на всех обращениях с расстоянием меньше k — ответ — накопленная сумма гистограммы.
5Разбор
Первое обращение к странице — промах при любом размере, в гистограмму оно не идёт, а только добавляет единицу и увеличивает счётчик встреченных страниц. Номера страниц до миллиарда сжимать не нужно: словарь «страница → момент последнего обращения» хранит только встреченные. После прохода hits[k] = hits[k − 1] + at[k − 1], и каждый вопрос — одно чтение.
Расстояние можно считать и как сумму на отрезке (p, t), то есть разность двух префиксов; вычитание из числа встреченных страниц экономит один спуск по дереву.
5+Решение
6Сложность
O(n log n + q) времени и O(n) памяти. Простой стек Маттсона — список страниц в порядке обращений — даёт те же расстояния, но поиск страницы в нём стоит столько шагов, каково расстояние: O(n·d). На журнале NASA это сто с небольшим шагов на запрос, а в четвёртом тесте, где тридцать тысяч страниц спрашивают вразнобой, — десятки тысяч.
7Типичные ошибки
- Симуляция для каждого размера. O(nq): в четвёртом тесте сто тысяч размеров.
- Стек на списке. Верно, но O(n·d) — там, где расстояния большие, это миллиарды шагов.
- Считать в расстояние все запросы, а не разные страницы. Если между двумя обращениями к странице другую страницу спросили десять раз, кэшу на два места этого хватит: расстояние — один.
- Первое обращение в гистограмме. Его расстояние бесконечно: оно не попадает ни при каком размере. В первом примере кэш на 5 мест ловит 7 обращений из 12, а не 12.
Алгоритмы задачи
O(1) на get и put
2 задачи
DS
Структура данных
Дерево Фенвика
Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера.
O(log n) на сумму префикса и на изменение
2 задачи