Заметим, что если $$$min(n, x+1) < k$$$, то ответ $$$-1$$$.

Иначе существует два случая:

• Если $$$k=x$$$, то подходящий массив выглядит как $$$[0, 1, 2, \dots, k-1, \dots, k-1]$$$.

• Если $$$k \ne x$$$, то подходящий массив выглядит как $$$[0, 1, 2, \dots, k-1, x, \dots, x]$$$.

В обоих случаях мы можем построить массив и посчитать его сумму за линейное время. Итоговая асимптотика $$$O(n \cdot t)$$$.

Заметим, что после операции с $$$b_j$$$, у которого есть какой-то единичный бит, этот бит станет единичным у всех чисел из $$$a$$$ (и останется им, так как бит не может стать нулём из единицы в результате операции ИЛИ). Если $$$n$$$ чётное, то в итоговом XORе этот бит станет нулевым, так как он будет равен XORу чётного числа единиц. Если $$$n$$$ нечётное, то этот бит будет единицей в итогов XOR.

Значит, если $$$n$$$ чётное, то операцией с $$$b_j$$$ мы зануляем все единичные биты $$$b_j$$$ в XORе чисел из $$$a$$$. Если $$$n$$$ нечётное, то мы наоборот делаем эти биты единичными. Значит, если $$$n$$$ чётное, то мы при применении операции XOR не увеличивается, то есть для получения минимального возможного XOR нужно применить операцию со всеми числами из $$$b$$$, а максимальным будет исходный XOR. Для нечётного $$$n$$$ всё наоборот, минимальный — это исходный XOR, максимальный — после применения операции со всеми элементами $$$b$$$.

Для применения операции со всеми элементами из $$$b$$$ достаточно посчитать их побитовое ИЛИ, и применить операцию к массиву $$$a$$$ с ним.

Зафиксируем цвет $$$x$$$, для которого мы сейчас будем считать ответ. Если не существует ни одного $$$a_i = x$$$, то не будет и клеток цвета $$$x$$$, ответ равен $$$0$$$. Иначе есть хотя бы одна клетка цвета $$$x$$$.

Для нахождения минимального прямоугольника, содержащего все клетки данного цвета, нам надо найти самую верхнюю, нижнюю, левую и правую клетки этого цвета в массиве $$$b$$$. Найдём в $$$a$$$ префикс наибольшей длины, на котором все числа строго меньше $$$x$$$. Пусть этот префикс имеет длину $$$L$$$. Тогда в первых $$$L$$$ строках и столбцах массива $$$b$$$ не будет клеток цвета $$$x$$$, так как для всех этих клеток в формуле $$$b_{i, j} = min(a_i, a_j)$$$ будет число с префикса, а на нём все числа меньше $$$x$$$. В $$$L+1$$$-й строке и $$$L+1$$$-м столбце будут клетки цвета $$$x$$$, так как $$$a_{L+1} \geq x$$$. Таким образом, мы нашли самую верхнюю и левую клетки цвета $$$x$$$. Для нахождения нижней и правой клетки нужно найти наибольший суффикс, где все числа меньше $$$x$$$.

Осталось научиться находить префиксы и суффиксы для всех цветов быстро. Заметим, что префикс для цвета $$$x$$$ не короче префикса для цвета $$$x + 1$$$, поэтому все префиксы можно посчитать просто одним проходом по массиву, аналогично и суффиксы.

Заметим, что если для какого-то префикса есть префикс большей длины, который стоит меньше, то нам бессмысленно покупать этот префикс, все его покупки можно заменить на покупки более длинного префикса, и ответ станет только лучше. Поэтому можно заменить каждое $$$c_i$$$ на минимальное $$$c_j$$$ среди $$$i \leq j \leq n$$$ (минимальная цена префикса, длиной не меньше $$$i$$$). После этого будет выполнено $$$c_i \leq c_{i+1}$$$.

Теперь давайте решать задачу жадно. Мы хотим максимизировать первый элемент итогового массива. Он будет равен $$$k / c_1$$$, так как купить больше $$$c_1$$$ префиксов мы не можем ($$$c_1$$$ это наименьшая из всех цен). После покупки $$$k / c_1$$$ префиксов длины $$$1$$$ у нас осталось сколько-то монет. Теперь мы можем заменить некоторые покупки $$$c_1$$$ на покупку более длинных префиксов, чтобы улучшить ответ.

Сколько будет стоить замена $$$c_1$$$ на $$$c_i$$$? Она стоит $$$c_i - c_1$$$ монет. При этом заметим, что для замены $$$c_1$$$ на $$$c_i$$$ мы можем по очереди заменить $$$c_1$$$ на $$$c_2$$$, $$$c_2$$$ на $$$c_3$$$, $$$\ldots$$$, $$$c_{i-1}$$$ на $$$c_i$$$ (так как $$$c_1 \leq c_2 \leq \ldots \leq c_i$$$). Это значит, что можно делать только замены покупки $$$c_{i-1}$$$ на покупку $$$c_i$$$.

Пусть мы максимизировали первые $$$i - 1$$$ элементов ответа, у нас осталось $$$x$$$ монет. Сейчас мы хотим заменить какие-то покупки $$$c_{i-1}$$$ на $$$c_i$$$. Сколько замен мы можем сделать? Нам хватит денег не более, чем на $$$\frac{x}{c_i - c_{i-1}}$$$ замен (если $$$c_{i-1} = c_i$$$, то мы сможем заменить все $$$c_{i-1}$$$), при этом мы не можем заменить больше покупок, чем мы сделали, поэтому замен не более $$$a_{i-1}$$$ (это число покупок $$$c_{i-1}$$$). Значит, $$$a_i = min(a_{i-1}, \frac{x}{c_i - c_{i-1}})$$$, так как мы хотим максимизировать $$$a_i$$$. Осталось вычесть из числа монет стоимость замен, и перейти к $$$c_{i+1}$$$.

Давайте решать задачу динамическим программированием, давайте хранить $$$dp[i][j]$$$ такое, что $$$dp[i][j]=1$$$ если можно получить $$$XOR$$$ $$$MEX$$$ов с префикса по $$$i$$$ невключительно равный $$$x$$$ и $$$0$$$ иначе. заметим, что ответ не может быть больше $$$n$$$. поэтому размер этого двухмерного массива $$$O(n^2)$$$

Давайте научимся решать это за $$$O(n^3)$$$:

Переберем $$$l$$$ от $$$1$$$ до $$$n$$$, внутри переберем $$$r$$$ от $$$l$$$ до $$$n$$$, поддерживая значение $$$x=MEX([a_l, a_{l+1}, \dots, a_r])$$$, тогда нам нужно для всех $$$j$$$ от $$$0$$$ до $$$n$$$ пересчитывать $$$dp[r+1][j \oplus x]=1$$$ если $$$dp[l][j]=1$$$. Так мы пересчитываемся через случай, когда в итоговом наборе есть множество $$$[a_l, a_{l+1}, \dots, a_r]$$$.

Еще нужно добавить пересчет если $$$dp[l][x]=1$$$, присвоить $$$dp[l+1][x]=1$$$, он отвечает за случай, когда мы не берем $$$a_l$$$ в ответ.

Давайте определим $$$MEX(l, r) = MEX([a_l, a_{l+1}, \dots, a_r])$$$ это сделает дальнейший текст понятнее.

Посмотрим на отрезок $$$l, r$$$, заметим, что если существуют $$$l_2$$$ и $$$r_2$$$($$$l \leq l_2 \leq r_2 \leq r$$$), такие что $$$l_2 \ne l$$$ или $$$r_2 \ne r$$$ и при этом $$$MEX(l, r)=MEX(l_2, r_2)$$$, то мы можем взять отрезок $$$l_2, r_2$$$ вместо отрезка $$$l, r$$$ в набор $$$MEX$$$ов, и ответ никак не изменится. Если же для отрезка $$$l, r$$$ не существует такого отрезка $$$l_2, r_2$$$, то назовем этот отрезок $$$l, r$$$ незаменимым.

Теперь давайте докажем, что незаменимых отрезков не более $$$n \cdot 2$$$, для каждого незаменимого отрезка, посмотрим на больший элемент из пары $$$a_l, a_r$$$, пусть $$$a_l$$$ больше(другой случай зеркален), тогда давайте докажем, что существует максимум один отрезок, на котором $$$a_l$$$ является левым элементом и $$$a_l \leq a_r$$$ от противного:

пусть таких отрезков хотя бы 2, тогда назовем правые границы в них $$$r_1, r_2$$$ ($$$r_1 < r_2$$$), заметим что $$$MEX(l, r_1) > a_l$$$, иначе отрезок $$$l, r_1$$$ не незаменимый(можно было бы убрать $$$a_l$$$). Так как $$$a_l >= a_{r_2}$$$, то $$$MEX(l, r) > a_{r_2}$$$, тогда очевидно, что $$$a_{r_2}$$$ встречается среди элементов $$$[a_l, \dots, a_{r_1}]$$$ и следовательно $$$MEX(l, r_2-1) = MEX(l, r_2)$$$, а значит отрезок $$$l, r_2$$$ не незаменимый, противоречие.

Для каждого $$$a_i$$$ существует максимум один незаменимый отрезок для которого он меньший из крайних, где он левая граница и максимум один, где он правая граница. Значит всего незаменимых отрезков не более $$$2 \cdot n$$$.

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

Давайте запишем все записи чисел в бор. Рассмотрим два обхода этого бора — в глубину (далее dfs) и в ширину (bfs). Пусть в обоих обходах мы идём в сыновей вершины в порядке возрастания числа на ребре (в боре). Пусть номер вершины, обозначающей число $$$x$$$, в обходе dfs равен $$$dfs(x)$$$, а в bfs — $$$bfs(x)$$$. Тогда заметим, что $$$x = bfs(x)$$$, так в bfs на боре мы просто будем по очереди смотреть все записи чисел с какой-то длиной (а длины будут рассматриваться по очереди). В свою очередь $$$dfs(x)$$$ — это номер записи числа $$$x$$$ в отсортированном массиве. Значит, мы хотим посчитать число x, для которых $$$dfs(x) = bfs(x)$$$.

Давайте зафиксируем слой в боре, то есть будем смотреть только на числа с какой-то фиксированной одинаковой длиной записи. Тогда посмотрим на $$$dfs(x) - bfs(x)$$$ для чисел этого слоя. Заметим, что для двух чисел $$$y$$$ и $$$y + 1$$$ этого слоя верно, что $$$bfs(y + 1) - bfs(y) = 1$$$, и $$$dfs(y + 1) - dfs(y) \geq 1$$$. Это значит, что для фиксированного слоя функция $$$dfs(x) - bfs(x)$$$ не убывает. Значит, найти $$$0$$$ этой функции можно бинпоиском на каждом из слоёв.

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

Бор имеет глубину $$$O(log(n))$$$, бинпоиск работает за столько же, значит, итоговая асипмтотика решения равна $$$O(log^3(n))$$$.

Я хочу извиниться за то, что у некоторых участников возникли проблемы с TL, если они неоптимально реализовали авторскую идею.

Давайте сначала введем более удобный способ хранения чисел — массив $$$cnt$$$, где $$$cnt[x]$$$ это количество вхождений числа $$$x$$$ в префикс для которого мы ищем ответ. Все $$$x$$$ такие, что $$$x > n$$$ будем прибавлять к $$$cnt[0]$$$ потому что применить операцию к $$${x}$$$ в таком случае оптимально.

Давайте введем несколько операций с массивом, которых нам хватит, чтобы решить задачу.

• Создать число $$$x$$$. Применить операцию к множеству чисел $$${0, 1, 2, \dots, x-1}$$$, в терминах массива $$$cnt$$$ это применить $$$\mathrel{{-}{=}} 1$$$ на отрезке от $$$0$$$ до $$$x-1$$$ и $$$cnt[x] \mathrel{{+}{=}} 1$$$.

• Превратить число $$$x$$$ в $$$0$$$. для этого нужно применить операцию к $$${x}$$$, в терминах массива $$$cnt$$$ это применить $$$cnt[x] \mathrel{{-}{=}} 1$$$ и $$$cnt[0] \mathrel{{+}{=}} 1$$$.

• Создать число $$$x$$$ и очистить мультимножество. то же, что и создать число $$$x$$$, но мы берем абсолютно все остальные числа в операцию, после этого в множестве останется единственное число $$$x$$$(ну или большее).

Можно доказать, что применяя только операции такого вида всегда можно получить оптимальный ответ.

Теперь мы можем забыть про оригинальное условие и решать задачу для массива.

Давайте научимся проверять можно ли создать число $$$k$$$ и очистить мультимножество:

Для начала попробуем создать число $$$k$$$, если это возможно, то ответ да, иначе посмотрим на самое правое из чисел, которых не хватает(или другими словами самый правый $$$0$$$), попробуем создать его и теперь нужно искать самый правый элемент $$$\leq 1$$$ слева от него, и так далее. Чтобы это реализовать нужно поддерживать число $$$p$$$ такое, что мы вычитаем из всех элементов префикса $$$p$$$(изначально $$$p=1$$$), идти по массиву справа налево и если $$$cnt[i]<p$$$ присваивать $$$p \mathrel{{+}{=}}(p-cnt[i])$$$. Когда мы дойдем до нуля $$$p$$$ может быть больше $$$cnt[0]$$$ и в таком случае нужно использовать операцию превращения любого числа в $$$0$$$. Для этого просто проверим, что количество оставшихся чисел в массиве больше или равно $$$p$$$.

Это сейчас работает за $$$O(k)$$$, что не очень круто.

Способы оптимизации:

для начала давайте поддерживать сумму элементов $$$sm$$$ и как только она стала меньше нуля завершать работу, для этого когда вычитаем из $$$p$$$ числа $$$p-cnt[i]$$$ давайте из $$$sm$$$ вычитать $$$(p-cnt[i])\cdot(i-1)$$$. теперь давайте использовать дерево отрезков снизу на максимум, чтобы находить ближайшее слева число меньшее $$$p$$$ за $$$O(log(i))$$$.

Теперь заметим, что когда мы пересчитываемся через $$$cnt[i]$$$ то из $$$sm$$$ мы вычитаем как минимум $$$i-1$$$, а значит не может быть больше $$$O(\sqrt{n})$$$ разных значений $$$i$$$ через которые мы будем пересчитываться.

теперь мы можем отвечать для конкретного $$$k$$$ за $$$O(\sqrt{n} \cdot log(n))$$$, но в реальности асимптотика равна $$$O(\sqrt{n})$$$(из-за особенностей работы дерева отрезков снизу), Доказательство в отдельной вкладке.

Теперь как решать полную задачу:

изначально ответ равен $$$0$$$, заметим, что он не уменьшается, поэтому после каждого добавления будем проверять можно ли увеличить ответ, и увеличивать его пока возможно, ответ не может стать больше $$$n$$$, поэтому мы сделаем не более $$$2 \cdot n$$$ проверок.

Суммарно решение работает за $$$O(n \cdot \sqrt{n})$$$, вот такие пирожки.

Пусть в нашем запросе дерево отрезков снизу обработало $$$k$$$ вершин $$$[x_1, x_2 \dots, x_k]$$$.

тогда количество операций это сумма $$$dist(x_i, x_{i+1})$$$ по $$$i$$$ от 1 до $$$k-1$$$ и $$$dist(0, x_1)$$$, где $$$dist$$$ это длина пути между вершинами в дереве отрезков. Теперь заметим, для запроса $$$dist(a, b)$$$ что мы входим в вершину дерева отрезков отвечающую за блок длины $$$2^t$$$ только если $$$a$$$ и $$$b$$$ в разных блоках длины $$$2^{t-1}$$$, это логично. Теперь заметим что такое происходит не очень часто а именно числа $$$[x_1, x_2 \dots, x_k]$$$ могут входить в максимум $$$\sqrt{\frac{n}{2^t}}$$$ блоков длины $$$2^t$$$(асимптотически). а значит сумма всех запросов асимптотически равна сумме $$$\sqrt{\frac{n}{2^t}}$$$ по $$$t$$$ от 0 до 20, это геометрическая прогрессия с коэффициентом $$$\frac{1}{\sqrt{2}}$$$ так что сумма асимптотически равна $$$\sqrt{n}$$$. Доказали.

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

Для начала вам стоит познакомиться с алгоритмом нахождения ordered mst или как он еще известен, алгоритмом Эдмондса(Тут я буду ссылаться на его работу и без его знания решение понять нельзя). Дальше стоит заметить, что сжатия в процессе этого алгоритма (почти) никак не зависят от корня, и можно провести все сжатия как будто нет корня(заранее создав фиктивные ребра из $$$i$$$ в $$$i+1$$$ для $$$i$$$ от $$$1$$$ до $$$n-1$$$ и из вершины $$$n$$$ в вершину $$$1$$$ с ценой $$$n * max(a_i)+1$$$). Тогда после всех сжатий останется только одна вершина. Заметим, что разница с алгоритмом Эдмондса в том, что если на каком-то шаге алгоритма Эдмондса минимальное ребро из вершины ведет в корень, то сжатие делать не нужно.

Тогда давайте поддерживать дерево в котором каждая вершина отвечает за соответствующую ей сжатую вершину или за изначальную вершину, и детьми вершины $$$v$$$ являются все вершины, которые мы сжали, чтобы получить вершину $$$v$$$. Подразумевается, что при каждом сжатии мы создаем новую вершину.

Давайте называть ценой вершины $$$v$$$ минимальную цену ребра выходящего из вершины $$$v$$$ в процессе алгоритма Эдмондса(с учетом изменений цен ребер при сжатии в алгоритме Эдмондса).

Тогда нам нужно поддерживать сумму цен вершин дерева, в поддеревьях которых нет выделенных вершин.(Где выделенными вершинами могут быть только листья). Это не сложно делается, с помощью дерева отрезков.

Вы можете выбрать одну лучшую задачу, или не выбирать, если считаете, что такой нет.