Что написано в условии? Сказано, что мы можем взять левую башню и обрезать правую башню высотой первой, приечм мы можем это делать только с самой ближайшей справа башней, которая больше левой. А можно ли любую башню справа обрезать, а не только самую ближайшую.

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

В башне $$$i$$$ мы можем получить высоту $$$\min(a_1,a_2,\ldots,a_i)$$$, но никак не меньше. Тогда чему равен ответ?

Пусть $$$A_i$$$ — префиксный минимум, тогда ответ $$$\sum_i A_i$$$

Что происходит в задаче? Мы сначала перемешиваем массив $$$b$$$, а потом пытаемся превратить его в $$$a$$$ с помощью добавления неотрицательных чисел. Тогда какой критерий можно сформулировать для массива $$$b$$$ после перемешивание, что его можно превратить в $$$a$$$?

Массив $$$b$$$ можно превратить в $$$a$$$ тогда и только тогда, когда $$$b_i \le a_i$$$ для всех $$$i$$$. Тогда посмотрим на исходный массив $$$b$$$, посмотрим на какой-то элемент $$$b_i$$$, на каких позициях он может стоят в финальном ответе?

Найдем для него минимальный $$$j$$$, что $$$b_i \le a_j$$$, тогда мы можем положить $$$b_i$$$ в любую позицию, начиная с $$$j$$$, то есть $$$(j,j+1,\ldots)$$$. Тогда какую простую стратегию можем придумать?

Можем идти слева направо и если встретили $$$b_i \gt a_i$$$, тогда для него можем найти миниальную позицию $$$j$$$, что $$$b_i \le a_j$$$ и подвинуть этот элемент туда. Ограничения позволяют решить задачу за $$$O(n^2)$$$. Почему это работает?

Во-первых, мы обязаны подвинуть элемент $$$b_i$$$ хотя бы в $$$j$$$, но с другой стороны не имеет смысл сейчас его двигать дальше, потому что мы сможем это сделать на следующих шагах, если потребуется.

В большинстве задач, можно попробовать решать их, идя слева направо, то есть попытаться решить задачу для префикса $$$a_1,a_2,\ldots,a_i$$$. В этой задаче стоит сделать именно так, потому что в итоге мы хотим получить отсортированный массив, значит максимум будут всегда справа. Как это сделать?

Пускай мы решили задачу для префикса $$$a_1,\ldots,a_{i-1}$$$. Мы хотим добавить $$$a_i$$$. Какие бывают случаи?

Если $$$a_{i-1} \le a_i$$$, то префикс уже отсортирован, а если $$$a_i \lt a_{i-1}$$$?

Тогда мы обязаны свапать $$$a_i$$$ с предыдущим элементом пока префикс не отсортирован. Что тогда будет происходить?

Тогда сам элемент $$$a_i$$$ не поменяется, но подвинется куда-то влево, а те элементы, с которыми мы поменяемся местами увеличиться на $$$a_i$$$. Отлично, научились решать задачу за $$$O(n^2)$$$, но можно ли быстрее? Нужно ли нам знать весь префикс?

Так как в итоге нам нужно узнать только последний элемент, то можем помнить только его, тогда если $$$a_{i-1} \le a_i$$$, то новый макс. элемент равен $$$a_i$$$, а иначе $$$a_{i-1}+a_i \ge a_{i-1}$$$.

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

Строка точно не является красивой, если она содержит хотя бы два элемента, причем все элементы чередуются (например $$$01010101$$$), то есть нет одинаковых соседей.

Задача похожа на часто-встречающуюся задачу, когда два соседних элемента заменяют на их сумму. В такой задаче сумма массива никогда не меняется. Можно ли сделать в этой задаче что-то похожее?

Пусть $$$a$$$ — это число, на которое мы заменим нули, а $$$b$$$ — число, на которое мы заменим единицы. Тогда мы хотим, чтобы $$$a + a = b, b + b = a$$$, то есть $$$2a=b,2b=a$$$. Что тогда?

Тогда $$$a = 2\cdot b = 2\cdot (2\cdot a) = 4a$$$, то есть $$$3a = 0$$$. На что похоже?

Это похоже на арифметику по модулю $$$3$$$. Возьмем $$$a \equiv +1\pmod{3}, b \equiv -1 \pmod{3}$$$

Тогда какой второй критерий мы хотим?

Так как теперь при выполнении операции сумма элементов по модулю 3 не меняется, то в итоге мы хоим получить либо $$$a$$$, либо $$$b$$$, то есть хотим, чтобы сумма элементов не была равна нулю по модулю 3. Попробуем проверить, достаточно ли этих двух критериев.

Пусть у нас есть строка $$$s_1s_2\ldots s_n, n \ge 2$$$, приечм $$$\sum s_i \not\equiv 0\pmod{3}$$$. И еще есть два равных соседа $$$s_i = s_{i+1}$$$, тогда если мы применим к ним операцию, то сумма опять не будет равна нулю, осталось проверить, что в случае $$$n \ge 3$$$ у нас опять будут одинаковые соседи. Рассмотрим самую левую пару одинаковых элементов. Если $$$i \gt 1$$$, то у нас слева стоит $$$-s_{i-1}$$$, а два элемента $$$s_i,s_{i+1}$$$ заменятся на $$$-s_i$$$, тогда получили двух одинаковых соседей. А если $$$i=1$$$, тогда эта пара лежит в первом блоке одинаковых элементов. Тогда правее этого блока либо есть следующий блок из противоложных элементов, либо блока нет. Если блок есть, тогда мы можем самую правую пару соседей из первого блока, тогда новый элемент будет равен первому элементу следующего блока. А если у нас блок всего один?

Тогда $$$n \ge 4$$$, потому что мы рассматриваем случай $$$n \ge 3$$$, то $$$n$$$ не равно $$$3$$$, так как иначе сумма будет равна нулю. Тогда после применений операции в блоке будет $$$n - 2 \ge 2$$$ элемента, значит будет хотя бы одна пара одинаковых соседей.

Можем ли мы восстановить однозначно некоторые элементы $$$b_i$$$?

Рассмотрим $$$i$$$, что $$$b_i \neq -1$$$, тогда мы знаем, что $$$a[b_i] = b[a_i]$$$, тогда мы точно знаем, чему равен элемент в $$$a_i$$$, и наоборот, если мы знаем значение $$$b$$$ в индексе $$$a_i$$$, то знаем и в индексе $$$i$$$. Как тогда можно посмотреть на перестановку?

Очень часто помогает посмотреть на перестановку в виде набора циклов, То есть например берем $$$1 \rightarrow a[1] \rightarrow a[a[1]], \ldots$$$. Что тогда следует из предыдущего шага?

Получается, что если на цикле у какого-то элемента мы знаем значение $$$b$$$, то во всех остальных иднексах, лежащих в этом же цикле мы тоже можем однозначно восстановить значения. Что будет после восстановления

После восстановления у нас будет набор незаполненных циклов. То есть мы знаем, какие индексы мы хотим заполнить. А какими числами мы можем это сделать?

Мы можем заполнить их еще неиспользованными числами из $$$b$$$. Тогда как получить ответ?

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

Переформулируем задачу. Мы хотим выбрать максимальный набор индексов $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n$$$, что мы можем раскрасить элементы массива $$$a$$$ на позициях $$$i_j$$$ без возникновения каких-либо противоречий.

Как раскрасить элемент $$$a_i$$$? Каким отрезком?

Мы можем раскрасить этот элемент только отрезком $$$[i - a_i + 1, i + m - a_i]$$$, обозначим его за $$$[L_i,R_i]$$$. Какие тогда самые простые противоречия могут быть?

Если есть $$$i_j$$$, что $$$L_{i_j} \lt 1$$$ или $$$R_{i_j} \gt n$$$, тогда точно не может раскрасить эти элементы. Хорошо, а в каком порядке красить элементы? Какие могут быть проблемы?

Когда мы красим какой-то отрезок $$$[L_i, R_i]$$$, то мы также закрашиваем и элемента на всем этом отрезке, то есть все $$$j$$$, что $$$L_i \le j \le R_i$$$, тогда если $$$L_j \neq L_i$$$, то мы затрем элемент $$$j$$$, значит нам надо будет его опять красить. О чем это говорит, в каком порядке нужно красить элементы $$$a_i, a_j$$$?

Если отрезок $$$[L_i,R_i]$$$ покрывает $$$j$$$, причем $$$L_i \neq L_j$$$, то мы обязаны красить элемент $$$j$$$ после $$$i$$$. А если окажется так, чтобы $$$[L_j,R_j]$$$ изменит $$$i$$$?

Тогда мы не сможем покрасить одновременно два элемента $$$i,j$$$. Хорошо, а что если теперь нет таких плохих пар, в каком порядке красить элементы?

Если отрезок $$$[L_i,R_i]$$$ покрывает $$$j$$$ проведем ребро из $$$i$$$ в $$$j$$$, раз у нас нет плохих пар, то в таком графе не будет циклов, т.к. все отрезки имеют одинаковую длину, значит если был цикл, то была и пара плохих элементов. Тогда этот граф можно топологически отсортировать и получить порядок, в котором нужно красить элементы.

Нужно ли нам проверять все пары индексов из множества?

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

Мы хотим найти максимальную подпоследовательность $$$i_1 \lt i_2 \lt \ldots$$$, что никакие два соседа не являются плохими. Будем решать с помощью динамического программирования. Заведем $$$dp_i$$$ — максимальная поледовательность, которая заканчивается в $$$i$$$. База $$$dp_i=1$$$, если $$$1 \le L_i \le R_i \le n$$$. Ответ: $$$\max(dp_i)$$$. Как сделать переход?

Зафиксируем $$$i$$$, мы хотим найти $$$j \lt i$$$, что либо $$$L_j = L_i$$$, либо $$$R_j \lt i$$$, либо $$$j \lt L_i$$$. Тогда по всем таким $$$j$$$ нужно обновить $$$dp_i$$$ значением $$$\max(dp_i, dp_j+1)$$$. Первый случай легко обрабатывается: просто для каждого $$$L_i$$$ поддерживаем максимальное $$$dp_i$$$, а два последних случая обрабатываются с помощью Дерева Фенвика или Дерева Отрезков.

В этой задаче если бы можно было задавать запросы $$$i = j$$$, то можно было бы просто сделать $$$b = a$$$. Но здесь это сделать не получится. Рассмотрим какой-нибудь сложный предельный случай. Какой?

Если все числа — это разные простые числа в некоторых степенях? То есть $$$a = (p_1^{\alpha_1}, p_2^{\alpha_2},\ldots)$$$?

Тогда нам нужно как-то закодировать весь массив, причем никакие два элемента исходного массива не содержат информации друг о друге. Значит нам нужно какое-то дополнительное знание. Какое?

Например, можно взять первые 150 простых чисел в максимальных степенях, что эта степень не больше $$$10^6$$$. Тогда как мы могли бы восстановить массив, если бы все $$$p_i$$$ были бы среди этих 150 простых?

Мы могли для каждого $$$i$$$ взять $$$gcd(a_i, p_j)$$$ для всех простых и перемножить. Но что если у некоторых $$$a_i$$$ есть простые в разложении, которые не встречаются среди первых 150 простых чисел?

Если посчитать количество хороших чисел, которые можно восстановить, то их больше $$$3\cdot 10^5$$$, а это число больше $$$2^{18}$$$, но наши числа могут быть больше $$$2^{18}$$$, но не больше чего?

Все числа не больше $$$2^{20}$$$. На что похожи числа $$$18,20,9,10$$$?

На то, что $$$\frac{10}{9}=\frac{20}{18}$$$, тогда что мы можем сделать?

Мы можем выписать все числа массива в ряд из $$$20n$$$ бит, а дальше перегруппировать эти биты в блоки по 18 бит, получив массив из $$$\lceil\frac{20n}{18}\rceil = \lceil\frac{10n}{9}\rceil$$$ чисел, каждое из которых не больше $$$2^{18}$$$. А что дальше?

Тогда каждое число — это по сути индекс хорошего элемента. Тогда как решать всю задачу.

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

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