Заметим, что если $$$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$$$ невключительно равный $$$j$$$ и $$$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 \geq a_r$$$ от противного:

пусть таких отрезков хотя бы 2, тогда назовем правые границы в них $$$r_1, r_2$$$ ($$$r_1 < r_2$$$), заметим что $$$MEX(l, r_1) > a_l$$$, иначе отрезок $$$l, r_1$$$ не незаменимый(можно было бы убрать $$$a_l$$$). Так как $$$a_l \geq 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$$$ в процессе алгоритма Эдмондса(с учетом изменений цен ребер при сжатии в алгоритме Эдмондса).

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

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

Попробуйте посмотреть на четность $$$n, m$$$.

Игрок, который победит не зависит от стратегии.

Единственное, от чего зависит победивший игрок это четность $$$n, m$$$.

Заметим, что игра закончится только тогда, когда фишка находится в правом верхнем углу (иначе можно сдвинуть её на $$$1$$$ клетку вправо или вверх). За все ходы фишка сдвинется на $$$n - 1$$$ вправо и на $$$m - 1$$$ вверх, значит, суммарная длина всех ходов равна $$$n + m - 2$$$ (длина хода — на сколько сдвинулась фишка за ход). Так как длина любого хода нечётна, то после любого хода Бурёнки сумма длин будет нечётна, а после любого хода Тони чётна. Значит, мы можем узнать, кто сделал последний ход в игре, посмотрев на $$$(n + m - 2) \operatorname{mod} 2 = (n + m) \operatorname{mod} 2$$$. При $$$(n + m) \operatorname{mod} 2 = 0$$$ побеждает Тоня, иначе — Бурёнка.

Сложность решения — $$$O(1)$$$.

Вместо $$$k$$$ можно рассматривать остаток от деления $$$k$$$ на 4.

Для остатка 0 ответа нет.

Для всех остальных остатков ответ есть.

Заметим, что от числа $$$k$$$ нам нужен только остаток по модулю $$$4$$$, поэтому возьмём $$$k$$$ по модулю и будем считать, что $$$0 \leq k \leq 3$$$.

Если $$$k = 0$$$, то ответа нет, так как тогда произведение чисел в каждой паре должно делиться на $$$4 = 2^2$$$, то есть произведение всех чисел от $$$1$$$ до $$$n$$$ должно делиться на $$$2^{\frac{n}{2} \cdot 2} = 2^n$$$, но степень вхождения $$$2$$$ в эту сумму равно $$$\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{4}\rfloor$$$, что меньше $$$n$$$.

Если $$$k = 1$$$ или $$$k = 3$$$, то сделаем все пары вида $$$(i, i + 1)$$$, где $$$i$$$ — нечётное. Тогда $$$a + k$$$ будет чётным в каждой паре, так как $$$a$$$ и $$$k$$$ нечётные, а так как $$$b$$$ тоже чётное, то произведение будет делится на $$$4$$$.

Если $$$k = 2$$$, то сделаем то же разбиение на пары, но во всех парах, где $$$i + 1$$$ не делится на $$$4$$$, поменяем числа местами (то есть сделаем $$$a = i + 1$$$ и $$$b = i$$$). Тогда в парах, где $$$i + 1 \operatorname{mod} 4 = 0$$$, $$$b$$$ делится на $$$4$$$ (значит, и произведение тоже), а в остальных $$$a + k$$$ делится на $$$4$$$ (так как $$$a$$$ и $$$k$$$ имеют остаток $$$2$$$ по модулю $$$4$$$).

Сложность решения — $$$O(n)$$$.

Кто бы побеждал в поединках, если бы самый сильный спортсмен был бы первым в очереди?

После какого числа раундов самый сильный спортсмен гарантированно окажется в начале очереди?

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

Заметим, что после того, как самый сильный спортсмен окажется в начале очереди, выигрывать будет только он. Самый сильный спортсмен окажется в начале очереди не более, чем после $$$n$$$-го раунда. Промоделируем первые $$$n$$$ раундов, если в $$$i$$$-м раунде победил $$$j$$$-й спортсмен, то запишем для него номер $$$i$$$. Теперь для ответа на запрос $$$(i, k)$$$ достаточно бинпоиском найти число побед $$$i$$$-го спортсмена в раундах с номерами $$$j \leq k$$$, а если $$$k > n$$$, и сила $$$i$$$-го спортсмена равна $$$n$$$, то к ответу нужно прибавить ещё $$$k - n$$$.

Сложность решения — $$$O(n + q log n)$$$.

Можно использовать только отрезки длины $$$2$$$ и $$$1$$$.

Существует ответ, в котором отрезки длины $$$2$$$ не пересекаются с отрезками длины $$$1$$$.

Если для $$$l, r$$$ выполнено $$$a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r} = 0$$$, то мы можем заполнить нулями этот подотрезок за $$$r-l$$$ секунд используя только отрезки длины 2.

Существует ответ, где потраченное время минимально и длины всех взятых отрезков 1 и 2. Ведь, отрезок длины $$$l, r, x$$$ можно представить как $$$\lceil \frac{r-l+1}{2} \rceil$$$ отрезков длины 2 и 1, а точнее $$$[l, l + 1, x], [l + 2, l + 3, x], \ldots, [r, r, x]$$$(или $$$[r-1, r, x]$$$ если $$$(l - r + 1)$$$ четное).

Заметим, что если для $$$l, r$$$ выполнено $$$a_l \oplus a_{l + 1} \oplus \ldots \oplus a_{r} = 0$$$, то мы можем заполнить нулями подотрезок $$$l, r$$$ за $$$r-l$$$ секунд запросами $$$[l, l+1, a_l], [l+1, l+2, a_l \oplus a_{l+1}], ... [r-1, r, a_l \oplus a_{l+1} \oplus \ldots \oplus a_r]$$$.

Заметим, что если отрезок длины 2 пересекается с отрезком длины 1, их можно менять на 2 отрезка длины 1.

Из этого всего следует, что ответ представляет из себя отрезки длины 1 и куски покрытые отрезками длины 2. Тогда легко видеть, что ответ представляет из себя $$$n - $$$ (максимальное количество непересекающихся подотрезков с ксором 0). это количество можно посчитать динамическим программированием или жадно.

Попробуйте представить $$$n$$$ как $$$F_1 + F_2 + \ldots + F_m= n$$$.

В начале проверим, что число $$$n$$$ (сумма всех $$$c_i$$$) представимо в виде суммы какого-то префикса чисел Фибоначчи, в противном случае выведем ответ NO.

Давайте попробуем набирать ответ жадно, идя от больших чисел Фибоначчи к меньшим. Для очередного числа Фибоначчи возьмём букву с наибольшим числом вхождений в строку из числа тех, которые не равны предыдущей взятой букве (для избежания появления двух соседних блоков из одной и той же буквы, чего быть не может). Если вхождений этой буквы меньше, чем это число, то ответ NO. Иначе поставим букву на это число Фибоначчи и вычтем его из числа вхождений этой буквы.Если мы смогли набрать все числа Фибоначчи, то ответ YES.

Почему же жадное решение работает? Пусть на данном шаге нужно взять $$$F_i$$$ (я буду говорить взять число из $$$c_t$$$ это будет значить взять $$$F_i$$$ букв вида $$$t$$$) , посмотрим на максимальное $$$c_x$$$ сейчас, если его нельзя представить как сумму несоседних чисел Фибоначчи до $$$F_i$$$, то ответ нет. Можно доказать, что если $$$c_x > F_{i+1}$$$, то представить $$$c_x$$$ невозможно.

Если на шаге ровно одно число больше или равно $$$F_i$$$, тогда вариант взять нужное число всего один, поэтому жадное решение работает.

Если существует два таких числа и они равны, то вариант взять нужное число ровно один с точностью до перестановки букв. Жадник опять работает.

Если же есть $$$c_j \geq F_i, c_x \geq F_i, j \ne x$$$, то заметим, что большее из чисел $$$c_j, c_x$$$ будет больше $$$F_i$$$, если мы не возьмем его, то на следующем шаге это число будет больше $$$F_{i+1}$$$($$$i$$$ станет на 1 меньше), по доказанному выше ответа не будет, значит, брать большее из чисел всегда оптимально.

Ответ для $$$k=x$$$ и $$$k=\gcd(x, n)$$$ одинаков.

В этой задаче полезно общее утверждение: для любого массива $$$c$$$ длины $$$k$$$ верно $$$k \cdot \operatorname{max}(c_1, c_2, \ldots, c_k) \geq c_1 + c_2 + \ldots + c_n$$$.

Попробуйте применить вторую подсказку для $$$k_1=p$$$ и $$$k_2$$$ делящимся на $$$k_1$$$, где $$$k_1, k_2$$$ делители $$$n$$$/ разных $$$s$$$.

Можно рассматривать только $$$k$$$ вида $$$\frac{n}{p}$$$, где $$$p$$$ простой делитель $$$n$$$.

Давайте заметим, что ответ для $$$k=x$$$ и $$$k=\gcd(x, n)$$$ одинаков.

Действительно, для числа $$$k$$$ мы посетим числа c индексами $$$s + ik \mod n$$$ для $$$i$$$ от $$$0$$$ до $$$n-1$$$ включительно, из этого можно видеть, что индекс $$$i$$$-го числа совпадает с индексом $$$i + \frac{n}{\gcd(k, n)}$$$, причем если смотреть на два индекса, разница между которыми равна $$$l$$$ и $$$l < \frac{n}{\gcd(k, n)}$$$, то они различны, так как $$$k \cdot l \mod n \neq 0$$$, следовательно, ответ представляет из себя (сумму чисел с индексами $$$s + ik \mod n$$$ для $$$i$$$ от $$$0$$$ до $$$\frac{n}{\gcd(k, n)}-1$$$) $$$\cdot \gcd(k, n)$$$.

Теперь давайте докажем, что первые $$$\gcd(k, n)$$$ чисел одинаковы для $$$(s, x)$$$ и $$$(s, \gcd(x, n))$$$, заметим, что подходят только те индексы, которые имеют такой же остаток при делении на $$$\gcd(x, n)$$$ как и $$$s$$$, но таких индексов только $$$\frac{n}{\gcd(k, n)}$$$, а мы доказали, что у нас должно встречаться $$$\frac{n}{\gcd(k, n)}$$$ различных индексов, значит все они представлены по разу, следовательно ответ для $$$k=x$$$ и $$$k=\gcd(x, n)$$$ одинаков, ведь сумма состоит из одинаковых чисел. Ч.Т.Д.

Значит, нам нужно рассматривать только $$$k$$$ являющиеся делителями $$$n$$$, это уже заходит, если написать, например, дерево отрезков, но мы не хотим писать дерево отрезков, поэтому идем дальше, докажем, что для $$$k_1 = x$$$, ответ меньше или равен, чем для $$$k_2 = x \cdot y$$$ если $$$k_1$$$ и $$$k_2$$$ делители $$$n$$$, почему это так?

Заметим, что для числа $$$k$$$ ответ бьется на $$$\gcd(k, n)$$$ групп чисел, так что в каждой группе ровно $$$\frac{n}{\gcd(k, n)}$$$ и каждое число входит ровно в одну группу, причем для разных $$$s$$$ ответ будет выглядеть как (сумма в группе которой принадлежит $$$s$$$) $$$\cdot \gcd(k, n)$$$.

Посмотрим, на ответ для оптимального $$$s$$$ для $$$k_1$$$ назовем множество при котором он достигается $$$t$$$, заметим, что в $$$k_2$$$ для разных $$$s$$$ есть $$$m$$$ независимых множеств, которые являются подмножествами $$$t$$$. Пусть $$$m_i$$$ сумма в $$$i$$$-м множестве. Теперь заметим, что нам нужно доказать $$$max(m_1, m_2, \ldots, m_y) * y \geq m_1 + m_2 + \ldots m_y$$$ это верно для любых $$$m_i$$$, легко видеть. Ч.Т.Д.

Значит нужно перебирать делители вида $$$\frac{n}{p}$$$ где $$$p$$$ простое, теперь это можно сдать с сетом. ура!

Для делителя $$$d$$$ предлагается хранить ответы для всех пар $$$(s, d)$$$, где $$$s \le \frac{n}{d}$$$ и максимум среди них, их можно посчитать изначально за $$$O(n log n)$$$ для одного $$$d$$$, каждый запрос это изменение одного из значений, это можно сделать за $$$O(log n)$$$.

Сложность авторского решения $$$O(6 \cdot n \operatorname{log}(n))$$$, где 6 это максимальное количество различных простых делителей числа $$$n$$$.

Попробуйте свести задачу к одному массиву и дереву.

Попробуйте свести дерево к паросочетанию.

Первая доля:для каждого $$$a_i=0$$$ отрезок подходящих значений.

Вторая доля: множество $$$S$$$ и число $$$d$$$.

Существуют $$$L$$$ и $$$R$$$ такие, что ответ на запрос <> тогда и только тогда, когда $$$L \le d \le R$$$.

Давайте построим дерево рекурсивно начав с отрезка $$$[1, n]$$$, на каждом шаге будем выбирать корнем поддерева $$$v = \operatorname{argmax}([p_l, p_{l+1} \ldots, p_r]) + l - 1$$$, затем рекурсивно построим деревья для подотрезков $$$[1, v-1], [v+1, n]$$$ если они не пустые, затем создадим ребра из корня в корни этих поддеревьев. То что мы получили называется декартовым деревом по массиву. Дальше в разборе будет упоминаться именно это дерево.

Легко видеть, что декартовы деревья по массивам совпадают тогда и только тогда, когда эти массивы похожи. Тогда необходимое и достаточное условие для того, чтобы массив $$$a$$$ был похож на $$$p$$$ это то, что для любой пары $$$u, v$$$ такой, что $$$u$$$ находится в поддереве $$$v$$$, выполнено $$$a_v > a_u$$$, другими словами $$$a_v$$$ максимум среди чисел в поддереве вершины $$$v$$$.

Назовем позицию $$$i$$$ изначально пустой, если изначально $$$a_i = 0$$$

Назовем массив $$$a$$$ почти похожим на $$$p$$$ если для любой пары $$$u, v$$$ такой, что $$$u$$$ находится в поддереве $$$v$$$, выполнено $$$a_v > a_u$$$ или обе позиции $$$u$$$, $$$v$$$ изначально пустые.

Докажем, что если существует способ заполнить пропуски в $$$a$$$, чтобы получить почти похожий на $$$p$$$ массив, то существует и способ заполнить пропуски, чтобы получить похожий.

Действительно, давайте посмотрим на почти похожий на $$$p$$$ массив $$$a$$$. пройдемся по дереву рекурсивно начиная с корня. На шаге с вершиной $$$v$$$ сначала запустимся рекурсивно от всех детей $$$v$$$, теперь для них верно, что максимумы их поддеревьев в них, посмотрим на максимального ребенка $$$v$$$, пусть это $$$u$$$, тогда если $$$a_v > a_u$$$, то всё хорошо, иначе $$$a_v < a_u$$$ заметим, что $$$v$$$ является изначально пустой позицией, ведь для всех изначально не пустых позиций верно, что они являются максимумами в своих поддеревьях (это легко видеть подставив в определение), a $$$v$$$ не является. Заметим, что $$$u$$$ является изначально пустой позицией. ведь иначе, мы ни разу не изменили $$$a_v$$$ и $$$a_u$$$, следовательно в изначальном почти похожем на $$$p$$$ массиве $$$a$$$ выполнялось $$$a_v > a_u$$$ противоречие. значит $$$v, u$$$ изначально пустые, мы можем выполнить $$$swap(a_v, a_u)$$$ и всё будет выполняться.

После выполнения этого алгоритма мы изменили только изначально пустые элементы и получили $$$a$$$ похожую на $$$p$$$. ЧТД

Как проверить существование почти похожего на $$$p$$$ массива? Назовем числом $$$r_i$$$ минимум среди всех чисел $$$a_v$$$ таких, что $$$i$$$ находится в поддереве $$$v$$$. Назовем числом $$$l_i$$$ максимум среди всех чисел $$$a_v$$$ таких, что $$$v$$$ находится в поддереве $$$i$$$. легко видеть, что $$$a$$$ является почти похожим на $$$p$$$ если для всех $$$i$$$ выполняется, $$$l_i < a_i < r_i$$$.

Это звучит невероятно хорошо. Значит, всё что нам нужно это найти паросочетание множества $$$S_d$$$ и отрезков вида $$$[l_i, r_i]$$$ для $$$i$$$ являющихся изначально пустыми. Теперь легко доказать (пусть для $$$d_1$$$ ответ да, ответ для $$$d_2$$$ мы не знаем, попробуйте посмотреть на чередующийся путь из $$$d_1$$$ в $$$d_2$$$ в парососчетании, легко видеть, что если такой путь есть, то для $$$d_2$$$ ответ да, иначе, нет. Если посмотреть на структуру паросочетания точек с отрезками, можно увидеть, что чередующийся путь существует для непрерывного отрезка значений $$$d_2$$$), что подходящие $$$d$$$ являются непрерывным отрезком. границы можно найти бинарным поиском или два раза набирав жадно.

Асимптотика решения $$$O(n \operatorname{log} n)$$$ или $$$O(n \operatorname{log}^2 n)$$$

можно заметить, что пара действий $$$1 \, i \, j$$$, $$$2 \, k \, t$$$ и $$$2 \, k \, t$$$, $$$1 \, i \, j$$$ приводят к одинаковому результату, что это значит?

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

Попробуйте свести эту задачу к задаче о изоморфности графов.

Заведем две перестановки $$$p$$$ длины $$$n$$$ и $$$q$$$ длины $$$m$$$. Изначально обе перестановки тождественны. Для операции $$$1\, i \, j$$$, будем выполнять $$$\operatorname{swap}(p_i, p_j)$$$, для операции $$$2\, i\, j$$$ будем выполнять $$$\operatorname{swap}(q_i, q_j)$$$. Легко видеть, что после выполнения всех операций в позиции $$$i, j$$$ будет стоять $$$a_{p_i,q_j}$$$.

Теперь нужно найти подходящие перестановки $$$p, q$$$, чтобы $$$a_{p_i,q_j} = b_{i, j}$$$.

Давайте посмотрим на двудольный граф, где первая доля это строки, а вторая это столбцы. Пусть если $$$a_{i, j} \ne 0$$$, то из $$$i$$$ есть неориентированное ребро в $$$j$$$ цвета $$$a_{i, j}$$$. если построить такой же граф для $$$b$$$, то нам нужно проверить на изоморфность два двудольных графа каждое ребро которых имеет цвет, причем как мы помним по условию вершине не могут быть инцедентны 2 ребра одного цвета. Назовем их графом $$$a$$$ и графом $$$b$$$.

Эта задача во многом на реализацию, поэтому начиная с этого момента описываются действия, которые вы можете наблюдать в авторском решении 168728958.

Пусть $$$n < m$$$ иначе давайте поменяем $$$n$$$ и $$$m$$$ местами. Давайте попробуем сопоставить элементы массива $$$a$$$ элементам массива $$$b$$$. Давайте пройдемся по индексам от $$$1$$$ до $$$n$$$. Пусть сейчас мы выбираем, какую пару из $$$b$$$ выбрать для $$$i$$$-ой вершины первой доли графа $$$a$$$. Если мы уже нашли пару раньше, пропустим шаг, иначе давайте переберем подходящий вариант для пары среди всех еще не имеющих пары вершин первой компоненты $$$b$$$, таких не больше $$$n$$$, после сапостовления вершин, рёбра тоже сопоставляются однозначно(ведь не существует 2 ребер разных цветов), давайте, тогда запустим подставление рекурсивно для ребер(если мы сопоставили вершину $$$v$$$ вершине $$$u$$$ и из $$$v$$$ есть ребро цвета $$$x$$$ в $$$i$$$, а из $$$u$$$ есть ребро $$$x$$$ в $$$j$$$, то легко доказать, что в ответе $$$i$$$ будет сопоставлено с $$$j$$$), а значит мы восстановим всю компоненту. Пусть сумма числа вершин и числа ребер в компоненте это $$$k$$$, тогда мы выполним не больше, чем $$$n \cdot k$$$ действий для восстановления компоненты.

по перестановкам получить последовательность обменов это дело техники, его я объяснять не буду, но это отдельная функция в авторском решении вы разберетесь.

суммарно наше решение работает за $$$O(n(n \cdot m + n + m))$$$ изи за $$$O(min(n, m)(n \cdot m + n + m))$$$, где $$$n \cdot m + n + m$$$ суммарное число вершин и ребер во всех компонентах.

если вы чего-то не поняли, задавайте вопросы!

Единственная подсказка по этой задаче — вам не надо пытаться ее решить, оно того не стоит.

Для того, чтобы найти количество чисел от $$$1$$$ до $$$C$$$, взаимнопростых с $$$x$$$ выпишем его простые делители (различные). Пусть это простые числа $$$a_{1}, a_{2}, \ldots, a_{k}$$$. Тогда можно найти ответ за $$$2^{k}$$$ при помощи формулы включений-исключений.

Так как, $$$\left\lfloor\frac{a}{b\cdot c}\right\rfloor = \left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$$$, аналогичное утверждение выполнено и для $$$k$$$ чисел (можно делить нацело в любом порядке).

Разобьем простые числа до $$$2\times 10^4$$$ на 2 класса — мальнькие ($$$\leq 42$$$) и большие (остальные). Маленьких чисел 13, а больших 2249. Отдельно запишем пары больших чисел, которые в произведении дают число не превосходящее $$$10^5$$$. Таких пар будет 4904.

Сопоставим каждому набору маленьких простых чисел какую-то маску. Напишем $$$dp[mask]$$$ — знакопеременная сумма по подмаскам $$$mask$$$ чисел $$$\left\lfloor\frac{C}{a_{1} \cdot a_{2} \cdot \ldots \cdot a_{k}} \right\rfloor$$$, где $$$a_{1}, \ldots, a_{k}$$$ — простые из подмаски. Аналогично определим $$$dp[mask][big]$$$ (кроме маски есть большое простое $$$big$$$) и $$$dp[mask][case]$$$ (кроме маски есть пара простых из пары больших простых $$$case$$$). Каждое $$$dp$$$ можно насчитать за $$$states \times bits$$$, где $$$states$$$ — количество состояний в $$$dp$$$, а $$$bits$$$ — размер маски (количество битов).

Если выписать все большие простые на отрезке, для которого $$$mask$$$ — маска маленьких простых, ответом для этого отрезка будет сумма $$$dp[mask] + \sum dp[mask][big_{i}] + \sum dp[mask][case_{i}]$$$ (для $$$big$$$ и $$$case$$$, лежащих на отрезке). Таким образом, на запрос можно ответить за 7000 обращений к $$$dp$$$.

Для того, чтобы найти множетсво простых на отрезке, можно воспользоваться алгоритмом МО.

Итоговая асимптотика $$$O(n\sqrt{n} + q\times(\pi(m)+casesCount(C)))$$$

Стоит отметить, что (при очень сильном желании) можно дополнительно оптимизировать решение с помощью avx-инструций, а именно в 16 раз ускорить подсчет суммы по подмаскам в динамике, в 8 раз ускорить подсчет суммы $$$dp[mask][big]$$$, что позволит ответить на запрос за ~5000 (вместо 7000) обращений к $$$dp$$$, а предподсчет за $$$4\cdot 10^7$$$ вместо $$$7\cdot 10^8$$$ (на самом деле предподсчет работает намного быстрее за счет оптимизаций компилятора).

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