Задачник Базовый курс EN

Где может лежать k-й

Пирамидальную сортировку пикселей фотографии остановили сразу после первой фазы: массив из n пикселей уже стал кучей с наибольшим наверху, а извлечения ещё не начинались. Ячейки нумеруются с нуля, дети ячейки i — ячейки 2i + 1 и 2i + 2 (если они меньше n), и яркость каждого родителя больше яркости его детей. Все яркости разные.

Где в такой куче может оказаться k-й по яркости пиксель? Самый яркий — только в корне, второй по яркости — в одном из детей корня, а дальше вариантов всё больше. Для каждого запроса k посчитайте, сколько существует ячеек, для которых найдётся куча из n разных яркостей с k-м по яркости пикселем именно в этой ячейке.

Во втором примере n = 9600 — это фото из статьи, 120 × 80 пикселей. Один из закрытых тестов — 19 073, число землетрясений в каталоге USGS, а в других n доходит до 10¹⁸: перебирать ячейки по одной не выйдет.

Вход

В первой строке два числа: n (1 ≤ n ≤ 10¹⁸) и число запросов q (1 ≤ q ≤ 10⁵). Дальше q строк, в каждой одно число k (1 ≤ k ≤ n).

Выход

Для каждого запроса — в отдельной строке число ячеек, где может лежать k-й по яркости пиксель.

Примеры

Пример 1

Вход

Выход

Пример 2

Вход

Выход

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 11 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Начните с крайних случаев. Где может лежать самый яркий? Второй по яркости? А самый тёмный, k = n? Нарисуйте кучу из семи ячеек и проверьте ответ первого примера.

2Подсказка 2

Возьмите ячейку на глубине d (у корня глубина 0), в поддереве которой s ячеек, включая её саму. Сколько элементов обязательно ярче того, что в ней лежит, а сколько обязательно темнее? Получатся два условия на k. Хватит ли их, чтобы такая куча нашлась?

3Подсказка 3

В полном двоичном дереве ячейки одной глубины почти одинаковы: поддеревья слева полные, справа — на этаж ниже, и одно посередине — частичное. Значит, на каждой глубине не больше трёх разных размеров поддерева, а глубин около 60.

4Идея

Все предки ячейки ярче её — свойство кучи, применённое по цепочке. Все потомки темнее — по той же причине. Поэтому k-й по яркости может стоять в ячейке на глубине d с поддеревом из s ячеек, только если d ≤ k − 1 (предков хватает ярких) и s − 1 ≤ n − k (потомков хватает тёмных).

Этих двух условий и достаточно. Нужно выбрать k − 1 ячеек для более ярких так, чтобы вместе с каждой ячейкой в набор входил её родитель, — тогда в набор попадут все предки нашей ячейки, а её поддерево останется снаружи. Начнём с цепочки предков и будем добавлять по одной ячейке, у которой родитель уже в наборе, а сама она не из поддерева нашей ячейки и не она сама. Такие ячейки не кончатся, пока набор меньше n − s: всё, что вне поддерева, достижимо от корня в обход него. Осталось раздать самые яркие значения набору сверху вниз, k-е — нашей ячейке, остальные — оставшимся сверху вниз; свойство кучи выполнено везде.

5Разбор

Пусть H = ⌊log₂ n⌋ — глубина последнего этажа, на нём L = n − (2^H − 1) ячеек. У j-й ячейки глубины d < H под ней h = H − d этажей; полные этажи дают 2^h − 1 ячеек, а с последнего ей достаются ячейки с номерами от j·2^h до (j + 1)·2^h − 1, из которых существуют только меньшие L. Поэтому первые ⌊L/2^h⌋ ячеек глубины d имеют поддерево 2^h+1 − 1, следующая (если L не делится на 2^h) — 2^h − 1 + (L mod 2^h), остальные — 2^h − 1. На последнем этаже L листьев с поддеревом 1.

Получился список из не больше чем 3(H + 1) групп «глубина, размер, сколько ячеек». Для запроса k складываем группы с глубиной не больше k − 1 и размером не больше n − k + 1. Если k − 1 ≥ H, глубина не мешает никому, и ответ — число ячеек с поддеревом не больше n − k + 1: его даёт двоичный поиск по группам, отсортированным по размеру, и префиксные суммы. Если k ≤ H, групп не больше 3k, и их можно просто перебрать.

Во втором примере видно, как условия сменяют друг друга. Для k = 10 решает глубина: десятый по яркости может лежать только на первых десяти этажах, это 1023 ячейки, и из них не годится один корень — ответ 1022. В куче из 9600 ячеек 14 этажей, поэтому начиная с k = 14 глубина уже никому не мешает, и решают поддеревья. При k = 4800 под ячейкой может быть не больше 4800 потомков, и выпадают корень и его левый ребёнок, у которого в поддереве 5504 ячейки. При k = 9599 годятся 4800 листьев и единственная ячейка с одним ребёнком, а самый тёмный, k = 9600, — только в листе.

5+Решение

6Сложность

Подготовка — O(log² n) на одно n, запрос — O(log n): двоичный поиск или перебор не больше 3k ≤ 3 log₂ n групп. Числа до 10¹⁸ помещаются в 64-битное целое.

7Типичные ошибки

Только условие на глубину. Кажется, что k-й по яркости может лежать на любом из первых k этажей. Но под ним должны поместиться только более тёмные: самый тёмный пиксель не может лежать над кем-то. В первом примере такой ответ для k = 7 — 7 ячеек вместо 4.
Глубина с единицы. У корня нет предков, у его детей предок один: условие — d ≤ k − 1 при глубине корня 0.
Обход дерева. При n до 10¹⁸ ячейки нельзя перебрать по одной, а при q = 10⁵ нельзя и перебирать для каждого запроса все этажи вложенным циклом по ячейкам: нужны группы одинаковых поддеревьев.

Алгоритмы задачи

SRT Алгоритм Пирамидальная сортировка Куча прямо в массиве: n log n в худшем случае без лишней памяти — страховка introsort и сортировка ядра Linux. O(n log n) 2 задачи DS Структура данных Двоичная куча Минимум под рукой, добавление и извлечение за O(log n): дерево в массиве, на котором живут календари событий. O(log n) 2 задачи