Олимпиадная задача 9 класс, структуры данных
Пожалуйста, помогите решить задачу! Цель - найти эффективное решение следующей проблемы: нужно создать структуру с парами ключ-значение (ключ не превосходит 10^9) так, чтобы
- работал метод push(key, value), отвечающий за создание пары ключ-значение, если такого ключа ещё не было, либо за увеличению ключа на значение value, если такой ключ уже был; известно, что value не превосходит 500;
- можно было в любой момент времени быстро получить 5 ключей с максимальными значениями по ним, пропуская первые K ключей с максимальными значениями (например, выдать 5 максимальных ключей, пропуская 10 первых, значение K в рамках задачи непостоянно, может меняться от запроса к запросу).
Я пытался решить задачу, но мои решения были слишком тривиальными и неэффективными по времени.
Мне кажется, здесь нужно использовать какое-то дерево, возможно, префиксное, но додуматься до красивого решения не получается. При этом важно, что решение этой задачи подразумевает отказ от использования встроенных хеш-таблиц, словарей, списков, прочих структур "сложнее массива".
Ответы (1 шт):
Строим две дерамиды (treap, декартово дерево).
Одна A размером K с инверсным приоритетом - т.е. у неё на макушке минимум.
Другая B - с оставшимися элементами с максимумом на верхушке.
Ключ позволяет искать в любой дерамиде. Если элемент при увеличении value получает значение больше, чем минимум A - передвигаем этот минимум в B, а элемент вставляем в А.
Таким образом, K наибольших ключей всё время лежат в A, а 5 следующих максимумов при необходимости снимаем с верхушки B.
(может быть, даже отдельное хранилище для этой пятёрки завести?)