| Innopolis Open 2024. Отборочный этап 1 |
|---|
| Закончено |
На территории Университета Иннополис растет множество деревьев, за которыми надо ухаживать. В частности, в Иннополисе растут взвешенные полные двоичные деревья, которые иногда надо подрезать, чтобы они не разрастались очень быстро.
Рассмотрим некоторое полное двоичное дерево с $$$n = 2^k$$$ листьями. Дадим корню номер $$$1$$$, его детям — номера $$$2$$$ и $$$3$$$ (слева направо), и так далее занумеруем каждый слой вершин последовательными целыми номерами. Листья дерева будут иметь номера от $$$n$$$ до $$$2n - 1$$$. У вершины номер $$$i$$$ вес равен $$$w_i$$$. Весом множества вершин мы будем называть сумму весов вершин этого множества.
Тогда от вас требуется определять, как эффективно подрезать деревья. Запрос на подрезку задается номерами листьев $$$l$$$ и $$$r$$$, и осуществляется следующим образом:
- Сначала выбирается множество вершин $$$V$$$ — минимальное по размеру связное множество вершин, содержащее все листья с $$$l$$$-го по $$$r$$$-й. Обозначим самую близкую к корню дерева вершину множества $$$V$$$ за $$$\mathtt{root}(V)$$$.
- Затем требуется выбрать в множестве $$$V$$$ две различные вершины $$$x$$$ и $$$y$$$ такие, что ни одна из них не является потомком другой.
- Когда вершины $$$x$$$ и $$$y$$$ выбраны, ребра, ведущие из $$$\mathtt{root}(V)$$$, $$$x$$$ и $$$y$$$ «наверх» (в сторону корня), обрезаются. Тем самым $$$V$$$ отделяется от всего дерева, и распадается на три подмножества, обозначим их как $$$V_\mathtt{root}$$$, $$$V_x$$$ и $$$V_y$$$, соответственно.
- После чего все три этих подмножества высаживаются в качестве отдельных поддеревьев, чтобы повысить благоустройство территории.
У руководства есть несколько вариантов, как подрезать данное вам дерево. Ваша цель — определить для каждого из их запросов $$$(l, r)$$$, какие вершины $$$x$$$ и $$$y$$$ следует выбрать, чтобы минимизировать максимальный из весов $$$V_\mathtt{root}$$$, $$$V_x$$$ и $$$V_y$$$.
В первой строке через пробел даны два целых числа $$$n$$$ и $$$m$$$ — количество листьев в дереве и количество запросов у руководства ($$$2 \le n \le 2^{16}$$$; $$$1 \le m \le 10^5$$$; $$$n = 2^k$$$ для некоторого целого $$$k$$$).
В следующей строке через пробел перечислены $$$2n - 1$$$ целых чисел $$$w_i$$$ — веса вершин дерева ($$$1 \le w_i \le 10^9$$$).
В $$$i$$$-й из следующих $$$m$$$ строк дан $$$i$$$-й запрос руководства, два целых числа $$$l_i$$$ и $$$r_i$$$ — номер первого и последнего листьев, участвующих в подрезке дерева ($$$n \le l_i, r_i \le 2n - 1$$$; $$$r_i \ge l_i + 1$$$).
Для каждого запроса руководства выведите в отдельной строке через пробел два целых числа $$$x$$$ и $$$y$$$ — номера дополнительных вершин, по которым стоит обрезать дерево, чтобы минимизировать максимальный из весов трех отрезанных частей.
Если есть несколько вариантов ответов, минимизирующих максимальный вес отрезанной части, выведите любой из них.
По умолчанию баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу с потестовой оценкой начисляются за каждый пройденный тест независимо (по $$$2$$$ балла за каждый из шестнадцати тестов).
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Оценка |
| 0 | – | примеры из условия | – | |
| 1 | 6 | $$$n \le 32$$$, $$$m \le 20$$$ | 0 | полная группа |
| 2 | 10 | $$$n \le 512$$$, $$$m \le 400$$$ | 0, 1 | полная группа |
| 3 | 13 | $$$r_i = l_i + 1$$$ для всех $$$i$$$ | полная группа | |
| 4 | 23 | $$$w_i = 1$$$ для всех $$$i$$$ | полная группа | |
| 5 | 16 | $$$n \le 1024$$$, $$$m \le 2000$$$ | 0 – 2 | полная группа |
| 6 | 16 $$$\times$$$ 2 | нет | 0 – 5 | потестовая |
4 41 1 1 1 1 1 14 55 66 74 7
4 5 5 3 6 7 5 3
8 75 3 1 4 2 1 5 1 2 2 5 1 2 1 48 158 1110 138 1211 129 1413 15
5 3 4 11 5 3 4 5 5 3 5 3 6 15
Ниже дана иллюстрация для первых четырех запросов во втором примере из условия задачи.
У каждой вершины отмечен ее вес. Серыми выделены вершины, которые не вошли во множество $$$V$$$. Выбранные листья $$$l$$$ и $$$r$$$ обведены зеленым. Вершина $$$\mathtt{root}(V)$$$ обведена красным цветом, а вершины $$$x$$$ и $$$y$$$, которые нужно выбрать в качестве ответа — синим. Пунктиром выделены те ребра, которые обрезаются при выполнении соответствующей подрезки.
