Рассмори одну полоску длины $$$k$$$ из символов '#'. Сколько времени нужно, чтобы ее стереть? Что происходит за одну секунду?

За одну секунду мы стираем 2 символа '#' (или 1, если был всего один символ). Тогда через сколько времени мы все сотрем?

Через $$$\lceil\frac{k}{2}\rceil$$$ секунд. Тогда чему равен ответ?

Мы должны найти самую длинную полоску из подряд идущих символов '#' и вычислить ответ по формуле из предыдущего шага.

В условии написано, что мы можем перекладывать единицы слева направо, тогда что логичнее всего можно сделать?

Логичнее всего строить последовательность слева направо. Пойдем слева направо. Пусть мы стоим в позиции $$$i$$$, тогда какую оптимальную высоту мы хотим получить здесь?

Какое ограничение снизу на $$$a_i$$$ мы можем записать?

Запишем последовательность $$$(1,2,\ldots, n)$$$ -- это возрастающая последовательность с минимальными выстоами башен, тогда $$$a_i \ge i$$$, то есть мы хотим сделать $$$a_i$$$ равным $$$i$$$.

Тогда будем поддерживать количество единиц $$$S$$$, которые мы можем перенести с башен до $$$i$$$-й. Что делаем, если $$$a_i \gt i$$$?

Если $$$a_i \gt i$$$, тогда мы можем увеличить $$$S$$$ на $$$(a_i - i)$$$ и пойти дальше (и уменьшить $$$a_i$$$ до $$$i$$$). А что если $$$a_i \lt i$$$?

Тогда нам нужно увелчить высоту башни, потратив $$$(i - a_i)$$$. Тогда если $$$S \lt (i - a_i)$$$, то ответа нет, а иначе уменьшаем $$$S$$$ на $$$(i - a_i)$$$ и идем дальше.

В задачах на сортировку очень часто помогает придумать способ обменять местами какие-то две элемента $$$(i,j)$$$. Попробуем поприменять описанные в условии операции несколько раз.

Мы можем обменивать $$$(i, i + x)$$$ и $$$(i, i + y)$$$, тогда какие два элемента мы еще можем обменять?

Тогда мы можем обменять $$$(i, i + x)$$$, дальше обменять $$$(i, i + y)$$$, а затем опять $$$(i, i + x)$$$, тогда мы по сути обменяли местами $$$(i + x, i + y)$$$ или другими словами $$$(i, i + (x - y))$$$. На что это похоже?

Как работает простейший алгоритм Евклида?

Алгоритм Евклида гласит, что $$$gcd(x, y) = gcd(x, y - x) = \ldots$$$. А если хотите больше узнать о нетривиальных применениях этого алгоритма, рекомендую прочитать ЭТОТ ПОСТ и присоединиться к нам в сообщество)

Из шагов выше получаем, что мы можем обменять местами любые два индекса $$$(i,j)$$$, что $$$|i - j|$$$ делится на $$$gcd(x, y)$$$. Как нам это помогает?

Это значит, что мы можем отсортировать подпоследовательности $$$i_1 \lt i_2 \lt \ldots$$$, которые имеют одинаковые остаток от деления на $$$gcd(x, y)$$$. Сдеаем это и проверим, что итоговая последовательность отсортировалась.

Решим задачу попроще: допустим мы можем изменить знак любого префикса, чему тогда равен ответ?

Тогда ответ равен \sum |a_i|, как его получить?

Если $$$a_n \lt 0$$$, то мы можем поменять знак у префикса $$$[1 \ldots n]$$$ и перейти к вычислению ответа на массиве $$$(a_1,a_2,\ldots,a_{n-1})$$$, потому дальнейшие изменения никак не повлияют на $$$a_n$$$.

Возвращаемся к нашей задаче. Какие элементы мы никогда не сможем изменить?

Пусть $$$B = \max b_j$$$ — максимальный префикс, который мы можем изменить. Тогда все элемент $$$a_i$$$, что $$$i \gt B$$$ мы не можем изменить, значит мы можем добавить к ответу их сумму и забыть про них, теперь считаем, что мы можем поменять все элементы местами. Идем дальше. Какие элементы всегда будут меняться одинаково? (то есть нельзя изменить знак одного элемента без изменения второго)

Пусть $$$b_1 \lt b_2 \lt \ldots \lt b_m$$$, тогда элементы $$$[1,b_1]$$$ всегда будут меняться одинаково, а еще какие?

Рассмотрим блоки $$$[1, b_1], [b_1+1,b_2], [b_2+1,b_3], \ldots,[b_{m-1}+1,b_m]$$$. Элементы в каждом блоке всегда будут меняться одинаково, тогда что мы можем сделать?

Тогда мы можем вычислить сумму элементов в каждом блоке и перейти к задаче из Шага 1, тогда как посчитать ответ?

Пусть $$$S_i$$$ — сумма элементов в блоке $$$[b_{i-1}+1,b_i]$$$, тогда ответ $$$\sum |S_i|$$$

Давайте формально запишем, что то нас хотят в условии. Пусть $$$f_i = 1$$$, если $$$s_i = s_{i-1}$$$ и $$$f_i = 0$$$ иначе. Тогда что от нас хотят в условии? Что означает операция выбора отрезка $$$[l,r]$$$? Что при этом меняется и как?

Такая оперция изменяет $$$f_l$$$ с 0 на 1 и наоборот, а также меняет $$$f_{r+1}$$$ с 0 на 1 и наоборот. То есть по сути за одну операцию мы можем изменить какие-то два элемента $$$f_i,f_j$$$ (или один, если отрезок — это префикс или суффикс). Как нам это помогает?

Пусть к нам пришел запрос

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

В таком случае минимальное количество операций равно

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]