Пишем алгоритм за квадрат. Очевидно, если $$$i$$$ зафиксировано — мы можем набирать нашу последовательность $$$b$$$ жадно. Теперь перейдём от $$$i$$$ к $$$i+1$$$. Если $$$i$$$ было нашим $$$b_1$$$, посмотрим на ближайшее число справа равное $$$b_1$$$. Если оно дальше, чем $$$b_2$$$, посмотрим на ближайшее от этого $$$b_1$$$ справа, равное $$$b_2$$$. И так далее, если сейчас $$$b_i$$$, проверяем, что $$$b_{i+1}$$$ левее $$$b_i$$$, и если да — ищем новое $$$b_{i+1}$$$ справа.

Можно создать $$$map$$$ с позициями чисел в $$$a$$$ для каждого значения — тогда искать ближайшее справа можно за $$$\log(n)$$$ бинпоиском.

А теперь поймём, что это не квадрат, а линия. Заметим, что после каждого шага у нас двигается вправо указатель на $$$b_{i+1}$$$. А суммарный размер всех массивов с ними $$$\leqslant n$$$. Значит, работает за $$$O(n\log(n))$$$.

Делаем центроидную декомпозицию на $$$1$$$ дереве. Перебираем центроид, а внутри вершину. Теперь для этой вершины в центроидной декомпозиции $$$2$$$ дерева есть всего логарифм предков-центроидов. Переберём их — получаем (вершина; $$$2$$$ центроида, через которые идут пути). И таких пар у нас $$$n\log(n)^2$$$. И при этом мы знаем расстояние от вершины до двух этих центроидов. Тогда длина пути (который проходит через эти $$$2$$$ центроида) — просто сумма расстояний для $$$2$$$ вершин-концов этого пути.

Ну и всё, просто для каждой полученной так пары центроидов сохраняем $$$2$$$ вершины с минимальным расстоянием до них. И, взяв минимум сумм по всем, получаем ответ. Сложность $$$O(n\log(n)^2)$$$, но достаточно чистый (если аккуратно написать) — я загнал на $$$99$$$ баллов.

Сделаем центроидную декомпозицию в $$$1$$$ дереве, переберём центроид. Теперь хотим узнать минимум из всех попарных расстояний его детей. Зафигачим сжатое дерево из них во $$$2$$$ графе. У каждой вершины есть вес — её высота до центроида в $$$1$$$ дереве, у каждого ребра есть длина. Надо найти минимальную пару по (вес в вершинах+вес пути) в нашем сжатом дереве. Это делается переподвешиваниями стандартно. И было бы $$$O(n\log(n))$$$, если бы не построение сжатого дерева.

В ней у нас лишний $$$\log(n)$$$ от поисков $$$LCA$$$ — но мы зафигачим спарсы, и он уйдёт. И ещё лишний $$$\log(n)$$$ от сортировки вершин по $$$tin/tout$$$. Но если сохранять отсортированность при переходе в сыновей во время центроидной декомпозиции (тоже стандартно делается) — можно добиться желаемого $$$O(n\log(n))$$$. Но, кстати, с сортировкой за $$$O(n\log(n)^2)$$$ всё равно быстрее :)

Ну, точнее, комбинация этих подходов — $$$2$$$ массива мы пересчитываем и сохраняем отсортированными при переходе в сыновей, а $$$1$$$ массив (c $$$LCA$$$) сортируем заново. Так у меня получалось быстрее всего — и зашло, в итоге, на $$$99$$$ баллов.

Нам нужно посчитать (суммарное счастье событий, достижимых в дереве из корня, если разрешено перемещаться только по радостным событиям) по всем расстановкам значений.

То есть, сумму по всем расстановкам по всем достижимым вершинам значений в них.

То есть, сумму по всем вершинам по всем расстановкам, где они достижимы, значений в них.

Хорошо, зафиксируем вершину, узнаем сумму в ней, потом просуммируем по всем вершинам и узнаём ответ.

Заранее насчитаем значения $$$cnt$$$ — количество радостных событий, $$$sum$$$ — сумму значений по всем радостным событиям. А также расстояние (кол-во вершин на пути, включая саму эту вершину) от каждой вершины до корня — $$$h_v$$$.

Теперь, пусть мы находимся в вершине $$$v$$$. Чтобы она была достижима, нужно, чтобы все вершины на пути до корня (включая саму $$$v$$$) имели радостные события. Кол-во способов сделать это $$$cnt\cdot(cnt-1)\cdot\ldots\cdot(cnt-h_v+1)) = \frac{cnt!}{(cnt-h_v)!}$$$ (так как порядок нам важен). В частности, если $$$cnt < h_v$$$ — способов $$$0$$$ :) Все остальные значения мы можем расставлять, как хотим, поэтому всего расстановок, где эта вершина будет достижима, есть $$$\frac{cnt!}{(cnt-h_v)!}\cdot(n-h_v)!$$$

И, очевидно, у $$$a_i \geqslant 0$$$ нет никакого преимущества над $$$a_j \geqslant 0$$$, поэтому, в силу симметрии можно сказать, все радостные события будут суммарно на месте $$$v$$$ одинаковые количества раз по всем расстановкам, где она достижима. То есть, все по $$$\frac{(cnt-1)!(n-h_v)!}{(cnt-h_v)!}$$$ раз. И итоговая нужная нам сумма в вершине $$$v$$$ — это $$$\frac{(cnt-1)!(n-h_v)!}{(cnt-h_v)!}\cdot sum$$$.

Сделаем ДО c массовыми операциями. Будем хранить $$$or$$$, $$$and$$$ и $$$xor$$$ на отрезке. И, соответственно, проталкивать модификаторы $$$or=$$$, $$$and=$$$ и $$$xor=$$$.

Будем писать ДО с дополнением до степени двойки. Тогда каждый отрезок, кроме конечного, имеет чётную длину.

Нам нужно понять, как всё пересчитывать, когда мы приходим в очередную вершину. Если это лист — как-нибудь да пересчитаем :) Хорошо, значит, не лист — отвечает за отрезок с чётной длиной.

Сначала смотрим, как пересчитывать, когда нам сверху спустили модификатор $$$or=$$$ на $$$x$$$. Заметим, что $$$or$$$ и $$$and$$$ на отрезке сделают $$$or=$$$ с $$$x$$$, а вот $$$xor$$$ наоборот сделает $$$and=$$$ с (не $$$x$$$) (потому что теперь все биты чисел, где у $$$x$$$ есть единицы стали единицами, всего чисел чётно — $$$xor$$$ обратится в этих битах в $$$0$$$). Модификаторы пересчитаются так же.

Если спустили модификатор $$$and=$$$ на отрезке — в целом, аналогично $$$or=$$$.

Остался модификатор $$$xor=$$$ c $$$x$$$. Заметим, что значение $$$xor$$$ на отрезке не изменится (ведь в чётном количестве чисел каждый бит либо у всех не изменился, либо у всех инвертировался — чётность кол-ва $$$1$$$ не изменилась).

А если мы пересчитываем $$$or$$$ — для битов, которые в $$$x$$$ единицы надо понять, было ли число с $$$0$$$ в этом бите — если да, в $$$or$$$ после $$$xor=$$$ этот бит $$$1$$$, если нет — $$$0$$$). А это узнаётся просто из $$$and$$$ на отрезке (который у нас посчитан). В итоге, некоторой битовой магией получается пересчитать :) И с $$$and$$$ на отрезке при $$$xor=$$$ всё аналогично.

Формулы приводить не буду, можете сами на досуге повыводить — но общая идея ясна :)

Обозначим за $$$row_i$$$ — сумму в $$$i$$$-ом столбце, и $$$col_j$$$ — в $$$j$$$-ой строке.

Обозначим за $$$M$$$ — максимальное число элементов в ответе в одной строке/столбце (очевидно, $$$M \leqslant k$$$).

Обозначим за изолированный тот элемент ответа, у которого нет соседних с ним по строке/столбцу других элементов ответа. В частности, значение в нём будет просто $$$row_i+col_j-3a_{ij}$$$.

Сначала я опишу основные идеи, которые мы будем применять в решении, а потом предложу свой вариант их склейки в 100 баллов — тут уже всё может быть сильно вариативно :)

(Правда, из-за плохих претестов моё решение, в итоге, за-WA-шилось, так что проверить оптимальность не получится — набирает только 78 баллов :(

1. Возьмём оптимальный ответ. Посмотрим на любую строчку $$$i$$$ в нём, пусть в ней взято $$$t > 0$$$ клеток.

Заметим, что каждая взятая клетка вычитает из остальных $$$(t+2)a_{ij}$$$ и прибавляет к себе ($$$\leqslant row_i+col_j$$$). (Если мы взяли какие-то ещё числа из того же столбца — $$$col_j$$$ будет только уменьшаться).

Хорошо, $$$row_i$$$ у всех одинаковое, значит, возьмём эту строчку $$$i$$$ и заранее отсортируем все элементы в ней по $$$col_j-(t+2)a_{ij}$$$.

Пусть какой-то элемент не входит в первые $$$k$$$ из них. Тогда оставшиеся $$$k-1$$$ элемент могут занять максимум $$$k-1$$$ столбец, то есть, минимум $$$1$$$ элемент из этих первых $$$k$$$ будет одинок в своём столбце.

Заменим наш элемент (не входящий в первые $$$k$$$) на этот. Заметим, что $$$col_j-(t+2)a_{ij}$$$ стало, а было ($$$\leqslant col_x-(t+2)a_{ix}$$$), и по условию отсортированности $$$col_x-(t+2)a_{ix} \leqslant col_j-(t+2)a_{ij}$$$. Значит, сумма не уменьшилась, ведь всё остальное не изменилось (или увеличилось: если какие-то элементы ответа стояли в столбце $$$x$$$ — к ним дополнительно прибавилось $$$a_{ix}$$$).

2. Теперь будем повторять наш алгоритм (делать замену элемента в ответе), пока можем. И, в итоге, получаем, что, если в строке ровно $$$t$$$ элементов, для этих элементов у нас только $$$k$$$ вариантов. Ну, то есть, существует ответ, который состоит только из этих $$$k$$$ вариантов.

При этом $$$t$$$ у нас от $$$1$$$ до $$$M$$$. Значит, в строке могут подходить в качестве элементов ответа не больше $$$Mk$$$ вариантов (первые в порядке сортировке по $$$col_j-(t+2)a_{ij}$$$ по всем $$$1 \leqslant t \leqslant M$$$).

И абсолютно аналогично в столбце. Итого, у нас уже не $$$nm$$$ вариантов для элементов ответа, а $$$\leqslant Mk\cdot\min(n, m) \leqslant k^2\cdot\min(n, m)$$$.

Назовём эти элементы множеством кандидатов.

3. Пусть $$$C = (2Mk-1)(k-1)+1$$$. Смысл поймём чуть позже.

Посмотрим на элемент из кандидатов. У каждого такого элемента по не больше $$$Mk$$$ соседей кандидатов в строке и в столбце. Значит, если мы его возьмём, у нас обретут соседа не больше $$$2Mk-1$$$ элементов-кандидатов (включая его самого).

Теперь посмотрим на первые $$$C$$$ элементов в порядке сортировки кандидатов по $$$row_i+col_j-3a_{ij}$$$. Пусть в ответе есть элемент, не входящий в них. Тогда каждый из $$$k-1$$$ остальных элементов ответа имеет соседями по не больше $$$2Mk-1$$$ элементов. И остаётся хотя бы $$$1$$$ изолированный из этих $$$C$$$ первых.

Заменим наш (не входящий в первые $$$C$$$) элемент на этот изолированный. Заметим, что сумма не уменьшилась, так как наш элемент давал в сумму $$$\leqslant row_x+row_y-3a_{xy}$$$ (с дополнительными вычитаниями, если был с кем-то в одной строке/столбце), что из отсортированности $$$\leqslant row_i+row_j-3a_{ij}$$$ (без вычетаний по определению изолированности).

4. Отлично, будем повторять это, пока можем. В итоге, аналогично $$$2$$$ пункту, получим, что существует ответ, где все элементы его принадлежат этим $$$C$$$ первым элементам, базово просто $$$(2k^2-1)(k-1)+1$$$ элементам.

Это теперь наше новое множество кандидатов.

5. Пусть мы уже перебрали $$$t$$$ вершин, которые мы считаем, что входят в ответ. Поставим в эти клетки $$$0$$$ и будем поддерживать актуальные $$$row_i$$$ и $$$col_j$$$. Также для каждой строки/столбца будем считать кол-во уже взятых элементов в них — $$$numrow_i$$$ и $$$numcol_j$$$.

Теперь, если мы взяли в ответ ещё и элемент $$$a_{ij}$$$, мы должны дополнительно вычесть $$$(numrow_i+numcol_j)a_{ij}$$$, потому что он вычитается из значения всех уже взятых элементов, находящихся с ним в $$$1$$$ строке/столбце.

6. Учитывая всё выше сказанное, мы можем, например, перебрать какие-то $$$t$$$ элементов, какие мы уже взяли — и у нас останется взять $$$k-t$$$ элементов — пересчитаем множество кандидатов, и их станет уже $$$C = (2M(k-t)-1)(k-t-1)+1$$$. И дальше мы можем запускаться рекурсивно :)

Чтобы достаточно быстро пересчитывать кандидатов, заметим, что это, очевидно, подмножество кандидатов, которые были у нас на прошлом шаге.

7. Заметим, что, когда мы перебрали какой-то элемент, будто он входит в ответ, и перешли к следующему — можно считать, что предыдущий элемент уже не входит в ответ (иначе мы перебрали бы этот вариант раньше). Поставим соответствующую метку.

А дальше, когда мы уже насчитали следующее множество кандидатов, мы можем просто удалить из него все помеченные элементы. Это делит наше решение на $$$t!$$$, если верить, что элементы переходят в следующее множество кандидатов достаточно равномерно (где $$$t$$$ — число уже взятых элементов), так как из всех их перестановок мы учтём только $$$1$$$. В любом случае, ускоряет :)

Теперь пошла уже моя склейка этих идей, по идее, приводящая нас к успеху (если нигде не набагать :)

Будем перебирать по убыванию, начиная с $$$k$$$, максимальное кол-во элементов в $$$1$$$ строке/столбце. Обозначим его на текущем шаге за $$$M$$$ (собственно, это и есть $$$M$$$ по определению). И число кандидатов $$$C$$$ будет уменьшаться с уменьшением $$$M$$$.

Заметим, что тогда соответствующих кандидатов-строк (на линию с $$$M$$$ элементами) будет не больше, чем $$$\min(n, \frac CM)$$$ — ведь в кандидате-строке, очевидно, должно быть минимум $$$M$$$ кандидатов-элементов. И аналогично со столбцами.

Теперь переберём строку/столбец из кандидатов. По нашему предположению в ней ровно $$$M$$$ элементов взято, но тогда из $$$1$$$ пункта для них у нас есть только $$$k$$$ вариантов (а не $$$Mk$$$, как может показаться изначально). Для каждой линии-кандидата, если в ней всего $$$t \leqslant k$$$ элементов кандидатов, мы можем выбрать $$$M$$$ из них $$$C_t^M$$$ способами.

Оставшиеся $$$k-M$$$ элементов выберем в тупую рекурсивно (каждый раз пересчитываем кандидатов и выбираем элемент из них — и с помощью меток оно ещё делится на $$$(k-M)!$$$ примерно).

Если аккуратно посчитать число операций (или потестить решение) — можно понять, что для $$$M \geqslant 3$$$ мы выбираем из остальных $$$\leqslant 3$$$ элемента, и это работает достаточно быстро. Остался случай, когда $$$M \leqslant 2$$$.

Пусть мы уже взяли некоторое множество элементов в ответ. Теперь есть $$$2$$$ варианта — все оставшиеся $$$a_{ij}$$$ в ответе изолированные, или есть хотя бы $$$1$$$ пара в $$$1$$$ строке/столбце.

Если все вершины изолированные — понимаем, что $$$M = 1$$$. То есть, при текущем $$$k$$$ кандидатов $$$C = (2k-1)(k-1)+1$$$ (у нас сейчас $$$k$$$ — кол-во элементов, которые ещё нужно взять в ответ). Также используем метки времени.

Если аккуратно всё посчитать (или опять-таки потестить) — понимаем, что наше рекурсивное решение выше снова работает вполне быстро (даже если изначально все $$$a_{ij}$$$ в ответе изолированные).

Хорошо, а если у нас есть пара вершин в $$$1$$$ строке/столбце — просто запустим наше решение с перебором максимальной по кол-ву элементов в ответе строки рекурсивно :)

Как мы помним, строк-кандидатов $$$\min(n, C/2)$$$ — так как $$$M = 2$$$. И аналогично $$$C = (4k-1)(k-1)+1$$$. Мы выбираем из каждой $$$C_k^2$$$ варианта максимум. Со столбцами аналогично. А затем из $$$k$$$ вычитается $$$2$$$ — глубина не больше $$$3$$$ будет. Короче, в целом, и если посчитать, и если запустить — тоже срабатывает :)

Только важно понимать, что если мы не взяли элемент в кандидаты на пару — он всё ещё может войти в изолированные вершины. Поэтому метки для них должны быть раздельные.

И да, понятное дело, что я опустил ещё некоторые оптимизации, какие-то левые идеи — думаю, из данного базиса фактов можно собрать под сотню разных работающих решений. Хотя на самой олимпиаде, как мы видим, получилось только $$$1$$$ :) Так что, дерзайте!

Попробуем найти критерий того, что наш отрезок является полезным.

Во-первых, разделим его на блоки одинаковых символов — например, $$$s = abbcbbbxx$$$ перейдёт в $$$abcbx$$$, состоящую из $$$5$$$ блоков. Дальше, если в нашем отрезке чётное число блоков — он, очевидно, является полезным (просто разделим его на пары соседних).

Хорошо, иначе (при нечётном числе блоков) докажем, что отрезок является хорошим $$$\Longleftrightarrow$$$ в нём есть либо блок на чётном месте из $$$>1$$$ символа, либо последовательная тройка блоков вида $$$aba$$$, также начинающаяся с чётного места (нумерацию будем вести с $$$1$$$). В частности, отрезки $$$abbxyz$$$ и $$$abcdcag$$$ являются полезными, а вот $$$bcaatc$$$ или $$$bbcdca$$$ — нет.

По индукции. Если весь отрезок состоит из $$$1$$$ блока — не интересно :)

Иначе заметим, что мы обязаны взять весь $$$1$$$ блок в $$$1$$$ гармоничный кусок целиком. Теперь, если длина $$$2$$$-го блока $$$>1$$$ — возьмём из него в $$$1$$$ гармоничный кусок только $$$1$$$ символ: условие на гармоничность соблюдается и кол-во блоков в оставшемся куске будет чётно — мы победили, отрезок был полезный :)

Если же длина $$$2$$$-го блока $$$1$$$ — нам также придётся взять его в $$$1$$$ гармоничный кусок целиком. Теперь, если $$$3$$$ блок совпадает с $$$1$$$ — возьмём его в этот кусок тоже. И условие на гармоничность опять-таки соблюдается, а кол-во блоков в оставшемся куске опять-таки чётно (возможно, $$$0$$$) — и мы снова победили :)

А если $$$3$$$ блок не совпадает с $$$1$$$ — взяв первые $$$2$$$ блока в $$$1$$$ гармоничный кусок мы обязаны на этом его закончить. И остался кусок ткани с кол-вом блоков на $$$2$$$ меньше — но для него уже работает предположение индукции. И $$$\Longleftrightarrow$$$ доказали (для отрезков с нечётным числом блоков :)

Ок, а поэтому давайте идти по блокам справа налево и считать кол-во полезных отрезков, начинающихся в текущем. И сделаем отдельно для отрезков, начинающихся в чётных с начала массива блоках, и для отдельно отрезков, начинающихся в нечётных.

Будем поддерживать самое левое из (стоящих на чётных местах с начала) вхождений блоков с $$$>1$$$ элементами и троек блоков вида $$$aba$$$. Тогда до этого вхождения подходят только подотрезки с чётным числом блоков, а после — вообще все (мы смотрим на местоположение конца подотрезка). Ну и будем поддерживать суммарное число элементов в подотрезках с чётным числом блоков до вхождения.

Пересчёт делается несложно — у нас добавляются $$$2$$$ блока в начало, если у $$$2$$$-го $$$>1$$$ элемента, или первые $$$3$$$ теперь имеют вид $$$aba$$$ — у нас новое самое левое вхождение. И присвоим счётчику суммарного числа элементов размер $$$2$$$-го из этих блоков (а после него будут подходить уже все).

Иначе же просто к счётчику опять-таки прибавляется размер $$$2$$$-го из этих блоков (то есть, $$$1$$$), и процесс продолжается :)

Итого — сложность решения $$$O(n)$$$, но писать не слишком приятно.

Делаем бинпоиск по ответу. Если мы ищем $$$2$$$ касающиеся окружности радиуса $$$r$$$ без ёлок внутри — это то же самое, что искать отрезок длины $$$2r$$$, с концами не внутри окружностей радиуса $$$r$$$, надутых из каждой ёлки (ну, и не вне прямоугольника со сторонами, урезанными на $$$r$$$).

Ниже идёт лирическое отступление, можно сказать так: Заметим, что для заданного радиуса $$$r$$$ можно проверять только отрезки вида (точка на пересечении $$$2$$$ объектов — точка на объекте (сторона/окружность)). Но тогда это будет кукарек :)

Пусть отрезок такой есть. Будем его двигать влево, пока он не коснётся вершиной окружности/стороны. Теперь начнём поднимать его вверх (двигая по этой стороне/окружности), пока можем. Если он на верхней точке — убираем с объекта, продолжая двигать влево. Иначе он либо встал $$$1$$$ вершиной на пересечении $$$2$$$ объектов, либо стал каждой вершиной на какой-то объект (возможно, совпадающие).

Если он каждой вершиной на каком-то объекте — продолжим двигать отрезок. Можно представлять, что мы двигаем окружность радиуса $$$2r$$$ по объекту. И вторая точка находится на пересечении её объекта и этой окружности. Если пересечения нет — отлично, мы "снялись" с того объекта, продолжаем алгоритм.

Хорошо, значит, когда наш мысленный алгоритм завершится, у нас будет вершина на пересечении $$$2$$$ объектов. Окей, начнём двигать $$$2$$$ вершину по окружности радиуса $$$2r$$$, с центром в нашей точке. Она остановится, когда попадёт на какой-то объект (сторону/окружность). Заметим, что диаметральная точка нашей окружности $$$1$$$ точки (или точка нашей стороны на расстоянии $$$2r$$$), в частности подходят (если не принадлежат другим объектам, на которые мы натолкнёмся раньше.

Отлично, мы доказали мысленным алгоритмом, что, если существует такой отрезок длины $$$2r$$$, то существует отрезок, у которого $$$1$$$ точка на пересечении $$$2$$$ объектов (окружностей/прямых), а вторая ещё на каком-то. Причём, если мы зафиксируем объекты, $$$1$$$ точка получается с точностью до $$$2$$$ и $$$2$$$ точка тоже — пересечение окружности радиуса $$$2r$$$ с центром в $$$1$$$ точке и того объекта.

Продолжение решения.

Теперь переберём все варианты, проверка, что отрезок подходит втупую за $$$O(n)$$$ — проверяем все окружности, что точка не лежит в них. Есть решение за $$$O(n^4\log(C))$$$ — заходит на $$$52$$$ балла.

Теперь единственный кукарек. Заметим, что точек вида (пересечение $$$2$$$ объектов), которые не лежат внутри другого объекта (а нам подходят в качестве центра НЛО только такие) порядка $$$O(n)$$$. Сразу получаем сложность $$$O(n^3\log(C))$$$, которая набирает $$$66$$$ баллов.

Теперь хотим за быстро проверять, что точка не принадлежит окружностям. Тогда получим решение за $$$O(n^2\log(C)\cdot check)$$$ — так как сначала перебираем пересечение, проверяем, что оно хорошее — и уже для $$$O(n)$$$ оставшихся вариантов перебираем объект, на котором второй центр.

Хорошо, точки для проверки лежат хотя бы на $$$1$$$ из окружностей, которые у нас есть (с центрами в ёлках радиуса $$$r$$$) или сторон прямоугольника. Надо для каждой окружности насчитать, какие точки хорошие, а какие — нет.

Просто переберём другие объекты, посчитаем пересечениями, какие отрезки плохие (лежат внутри второго объекта), теперь отсортируем, и оставим отрезки, которых тут нет. Можно сделать сканлайном легко. (Для окружностей удобно разделить всё на верхние точки и нижние, и делать всё независимо — тогда нужна только $$$x$$$-координата для проверки, что точка хорошая).

И теперь просто бинпоиском для точки проверяем, принадлежит ли она хорошему отрезку. Получаем сложность решения $$$O(n^2\log(C)\log(n))$$$, если верить в кукарек. И я смог загнать это на $$$100$$$ баллов :)