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

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

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

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

Зафиксируем цвет $$$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)$$$.

TBD

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

Давайте введем несколько операций с массивом, которых нам хватит, чтобы решить задачу. \begin {itemize} \item Создать число $$$x$$$. Применить операцию к множеству чисел $$${0, 1, 2, \dots, x-1}$$$, в терминах массива $$$cnt$$$ это применить $$$\mathrel{{-}{=}} 1$$$ на отрезке от $$$0$$$ до $$$x-1$$$ и $$$cnt[x] \mathrel{{+}{=}} 1$$$. \item Превратить число $$$x$$$ в $$$0$$$. для этого нужно применить операцию к $$${x}$$$, в терминах массива $$$cnt$$$ это применить $$$cnt[x] \mathrel{{-}{=}} 1$$$ и $$$cnt[0] \mathrel{{+}{=}} 1$$$. \item Создать число $$$x$$$ и очистить мультимножество. то же, что и создать число $$$x$$$, но мы берем абсолютно все остальные числа в операцию, после этого в множестве останется единственное число $$$x$$$(ну или большее). \end {itemize}

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

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

Давайте научимся проверять можно ли создать число $$$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})$$$, вот такие пирожки.

TBD

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