Квадродерево снимка
Квадродерево сжимает картинку так: если в квадрате все пиксели почти одинаковы — самый яркий отличается от самого тёмного не больше чем на порог t, — квадрат хранится одним листом, одним цветом. Иначе он делится на четыре равных квадрата, и с каждым поступают так же. Квадрат из одного пикселя всегда лист. Так устроены многие форматы карт и снимков: на ровном небе остаются большие листья, на ветках и камнях — мелкие.
Редактор хочет выбрать порог и смотрит, сколько листьев получится при разных t. Для каждого порога из списка посчитайте число листьев квадродерева.
Тесты с третьего по шестой — четыре фотографии автора сайта в оттенках серого: «Вода и горы» 512 × 512 пикселей и ещё три по 256 × 256.
Вход
В первой строке сторона картинки s — степень двойки, 1 ≤ s ≤ 512, — и число порогов q (1 ≤ q ≤ 256). Дальше s строк по s чисел от 0 до 255 — яркости пикселей построчно. В последней строке q порогов t (0 ≤ t ≤ 255).
Выход
Для каждого порога в порядке ввода — число листьев квадродерева, в отдельной строке.
Примеры
Пример 1
4 4 10 12 200 200 11 10 200 201 90 90 30 60 90 90 40 50 0 2 30 190
13 7 4 4
Пример 2
1 2 5 0 255
1 1
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Для одного порога задача — прямой рекурсивный спуск: посчитать размах квадрата, и если он больше t, спуститься в четыре четверти. Сколько стоит такой спуск, если размах каждого квадрата считать просмотром всех его пикселей? Запишите уравнение для T(n), где n — число пикселей.
2Подсказка 2
Минимум и максимум квадрата — это минимум и максимум четырёх его четвертей. Если идти снизу вверх, склейка стоит четыре сравнения, а не просмотр всего квадрата. Как изменится уравнение?
3Подсказка 3
Порогов до 256, и строить дерево для каждого заново дорого. Размах узла не зависит от порога. При каких t узел оказывается листом?
4Идея
Строим квадродерево до единичных пикселей один раз, снизу вверх, и для каждого узла знаем размах r = max − min. Узел — лист, если его размах не больше t, а размах родителя больше t (у корня родителя нет). Значит, узел добавляет один лист ко всем порогам из полуинтервала [r(узла), r(родителя)). Таких отрезков столько, сколько узлов, и все они складываются разностным массивом по 256 возможным порогам.
5Разбор
Уровни снизу вверх. На нижнем уровне минимум и максимум квадрата 1 × 1 — сам пиксель. Квадрат стороны 2k склеивается из четырёх квадратов стороны k: его минимум — минимум четырёх минимумов, максимум — максимум четырёх максимумов. Склеивая, сразу знаем размах родителя и размахи детей.
Вклад узла. Ребёнок с размахом r внутри родителя с размахом R — лист ровно при r ≤ t < R: при меньших t его надо делить, при больших лист уже родитель или кто-то выше. Это diff[r] += 1, diff[R] -= 1. Корень — лист при всех t ≥ r(корня). Префиксные суммы diff дают ответ сразу для всех 256 порогов.
Почему это верно. Размах не растёт при переходе к части квадрата, поэтому, если узел — лист, все его предки делятся, а потомки не рассматриваются; лист — это ровно узел, у которого размах не больше t, а у родителя больше.
5+Решение
6Сложность
Узлов в квадродереве n + n/4 + n/16 + … < 4n/3, где n = s², и каждый склеивается за постоянное время: T(n) = 4T(n/4) + O(1), третий случай основной теоремы, Θ(n). Ответы — O(256 + q). Спуск сверху вниз с просмотром пикселей — это T(n) = 4T(n/4) + Θ(n), второй случай, Θ(n log n) на каждый порог, и на 262 144 пикселях шума с 43 порогами он не укладывается во время. Промежуточный вариант — построить размахи один раз, а для каждого порога спускаться по готовому дереву — стоит O(q · n) в худшем случае: на Go проходит, на Python на грани.
7Типичные ошибки
- Пересчёт размаха с нуля. Просмотр всех пикселей квадрата в каждом узле и для каждого порога — верно, но медленно (седьмой тест).
- «Лист, если листья все четыре ребёнка». Четыре ровных четверти разного цвета не дают ровного квадрата: размах надо считать по минимуму и максимуму, а не по тому, листья ли дети.
- Строгое неравенство. Лист — при размахе не больше порога; при t = 0 листом становится одноцветный квадрат.
- Забытый корень. Если вся картинка ровная (восьмой тест), ответ — один лист при любом пороге.