Защищенная тюрьма

Автор задачи и разработчик: Даниил Орешников

Посмотрим, сколько надо заплатить, чтобы построить $$$i$$$-ю комнату внутри, а $$$j$$$-ю снаружи. Если $$$a_j \geqslant a_i$$$ и $$$b_j \geqslant a_j$$$, то платить не придется ничего. Если $$$a_j < a_i$$$ и $$$b_j < b_i$$$, то придется заплатить полную цену $$$a_i + b_i - a_j - b_j$$$. Иначе же, придется заплатить либо $$$a_i - a_j$$$, либо $$$b_i - b_j$$$ в зависимости от того, длины какой стороны не хватает.

Рассмотрим комнату $$$(a_i, b_i)$$$. Если ограничиться в выборе внешней комнаты только типами с не меньшими значениями $$$b_j$$$, ответом будет $$$\max\left(0, \min\limits_{j:\:b_j\geqslant b_i} a_i - a_j\right)$$$. Аналогичное верно при рассмотрении комнат, у которых значения $$$a_j$$$ не меньше, чем $$$a_i$$$ — ответ будет $$$\max\left(0, \min\limits_{j:\:a_j\geqslant a_i} b_i - b_j\right)$$$. Таким образом, найти минимальное количество денег, которое надо заплатить, если выбирать комнаты, в которые $$$i$$$-я уже хотя бы по одному направлению помещается, можно следующим образом. Оотсортируем все типы комнат независимо по $$$a$$$ и по $$$b$$$, на каждом из полученных отсортированных массивов насчитаем максимумы на суффиксах значений $$$b$$$ и $$$a$$$ соответственно. Запомнив для каждой комнаты ее позицию в таких сортировках, можно за $$$\mathcal{O}(1)$$$ найти ответ. Более подробное описание этих двух случаев можно найти в разборе «базовой» версии этой задачи.

Осталось рассмотреть случай, когда выгодно «расширить» комнату, изначально меньшую $$$i$$$-й по обоим направлениям. Для этого достаточно перебирать все комнаты в порядке возрастания $$$b$$$, и на всех уже рассмотренных комнатах поддерживать декартово дерево по явному ключу $$$a$$$. Для комнаты $$$(a_i, b_i)$$$ достаточно разделить это дерево по ключу $$$a_i$$$ и найти в левой части максимум величины $$$a_j + b_j$$$, которую можно специально поддерживать на поддеревьях. Время работы такого решения в сумме — $$$\mathcal{O}(n \log n)$$$ на сортировку и декартово дерево.