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

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

Через $$$|a_i - x|$$$ операций. Тогда через сколько операций все элементы станут равны $$$x$$$?

Через $$$\max\limits_{i=1}^{n}|a_i - x|$$$. Хорошо. Дальше, я смотрю на ограничения задачи. Я вижу, что $$$1 \le a_i \le 1000$$$. А еще $$$2 \le n \le 1000$$$. Тогда какие $$$x$$$ мне нужно перебрать?

Мне нужно перебрать $$$1 \le x \le 1000$$$, потому что сами $$$1 \le a_i \le 1000$$$. Тогда все будет работать за $$$1000\cdot n$$$. При заданных ограничениях задачи, такое решение будет работать меньше 1 сек.

Первое, что я делаю — это рисую массив $$$a$$$, а под ним массив $$$b$$$. Я вижу из условия, что мы меняем местами элементы $$$a_i$$$ и $$$b_i$$$. Влияет ли эта операция на другие элементы?

Нет, не влияет. То есть мне нужно для каждого $$$i$$$ выбрать, какой из двух элементов $$${a_i,b_i}$$$ пойдет в массив $$$a$$$, а какой в массив $$$b$$$. Дальше я смотрю на выражение, которое мне нужно максимизировать и на ограничения задачи. Вижу, что $$$1 \le a_i, b_i$$$ — положительные числа. В выражении есть слагаемое $$$\max(a)$$$, в таком случае мне удобно предположить, что максимум лежит где-нибудь в элементе $$$a_j$$$. Тогда как будет выглядеть выражение?

Выражение будет равно $$$a_j + \sum\limits_{i=1}^{n}b_i$$$. Раз я зафиксировал $$$a_j$$$, то я знаю $$$b_j$$$, а вот остальные $$$b_i, i\neq j$$$ я не знаю. Как мне выбрать остальные элементы $$$b_i$$$?

В качестве остальных элементов мне выгодно выбрать $$$max(a_i, b_i)$$$. Хоршо, тогда мне удобно в начале сделать так, чтобы $$$a_i \le b_i$$$ (с помощью операции из условия). Тогда я могу посчитать заранее $$$S = \sum\limits_{i=1}^{n}\max(a_i, b_i)$$$. Я ее считаю, потому что в будушем мне нужно будет вычислить второе слагаемое в выражении. Теперь, допустим, я считаю, что максимум лежит в $$$j$$$-м элементе. Причем возможно я опять сделаю операцию к $$$j$$$-му элементу. Тогда чему будет равна сумма $$$b$$$?

Она будет равна $$$S' = S - \max(a_i,b_i)+b_i$$$ — здесь я беру предподсчитанную сумму $$$S$$$, убираю $$$\max(a_i,b_i)$$$, потому что это слагаемое было в случае, если я предполагаю, что $$$a_i \le b_i$$$. А дальше добавляю текущий элемент $$$b_j$$$. Хорошо, тогда я могу обновить ответ с помощью числа $$$a_j + S'$$$. Но погодите. А что если $$$a_j$$$ не максимум? Все сломалось?

Нет, ничего не сломалось. Потому что наше выражение $$$a_j + S' \le ANS$$$, где ANS — ответ, потому что $$$a_j \le max(a)$$$. Но с другой стороны, в какой-то момент наш $$$a_j$$$ будет максимумом в оптимальном ответе и мы получим результат. Это частый метод — если мы хотим максимизировать что-то, где есть слагаемое $$$\max(a)$$$, то мы не обязаны делать так, чтобы $$$a_j$$$ был максимумом, а можем просто перебрать все возможные $$$a_i$$$, чтобы получить ответ.

Я очень часто в задачах в голове представляю оптимальный ответ. Как он может выглядеть в этой задаче?

В этой задаче в оптимальном ответе все $$$a_i \lt 0$$$. Могу ли я получить такой ответ?

Точно не знаю, но попробую его получить. Какое простое действие я могу сделать? Я могу взять например самый левый $$$i$$$, что $$$a_i \gt 0$$$ и поменять знак на префиксе, но тогда $$$a_i$$$ станет отрицательным а все элементы левее него станут положительными, нам это не подходит. Что еще могу простого сделать? Какой $$$a_i \gt 0$$$ выбрать?

Могу взять самый правый $$$i$$$, что $$$a_i \gt 0$$$, тогда правее него все элементы $$$a_j \lt 0, j \gt i$$$. Тогда после применения этой операции $$$a_i$$$ станет отрицательным, все элементы левее него поменяют знак, а элементы правее останутся отрицательными. Тогда где будет следующий положительный элемент?

Следующий положительный элемент будет левее $$$i$$$, а именно в некотором индексе $$$k \lt i$$$, потому что мы сделали $$$a_i \lt 0$$$, причем $$$a_j \lt 0$$$ для всех $$$j \gt i$$$. Что мы можем тогда сделать?

Мы можем опять взять самый правый положительный элемент и применить операцию к нему. Тогда в итоге мы получим все $$$a_i \lt 0$$$. Посмотрю на ограничения. $$$n \le 2\cdot 10^5$$$, здесь не зайдет $$$O(n^2)$$$, но зайдет $$$O(n)$$$. Как я буду тогда действиовать?

Раз индекс самого правого положительного элемента у меня уменьшается, то есть двигается влево, то как мне выгодно обходить массив?

Мне выгодно обходить массив справа налево. Но я не могу втупую выполнять операции, потому что в таком случае решение будет работать за $$$O(n^2)$$$. Хорошо, что мне вообще нужно знать?

Мне нужно знать, какой знак у текущего элемента $$$a_i$$$. Что мне для этого нужно?

Раз каждая операция меняет знак на префиксе, то мне нужно знать количство операций, которые я уже сделал. Допустим я сделал $$$C$$$ операций. Какой тогда будет знак у текущего $$$a_i$$$?

Если $$$C$$$ четное, то знак не поменяется, а если нечетное, то поменяется. Тогда я могу определить знак $$$a_i$$$ и если $$$a_i \gt 0$$$, то применить очередную операцию, увеличив $$$C$$$ на единицу.

В этой задаче все немного сложнее. Мы хотим сделать сумму как можно больше. Но применять операции мы можем только к $$$a_i \gt 0$$$. Мы уже знаем, что для любого массива мы можем получить все отрицательные элементы из предыдущей задачи. На какие элементы в массиве я могу посмотреть?

Могу посмотреть на последний элемент в массиве. Что если он отрицательный? То есть $$$a_n \lt 0$$$? Можно ли его сделать положительным?

Если $$$a_n \lt 0$$$, то он навсегда останется отрицательным. То есть по сути мы можем просто выкинуть его из массива и решать задачу для подмассива $$$[a_1, a_2, \ldots, a_{n-1}]$$$. Тогда я могу выкинуть некоторый суффикс отрицательных элементов. И считать, что $$$a_n \gt 0$$$. Какие есть варианты для дальнейших действий?

Я могу либо никогда не применять операцию к $$$a_n$$$ (тогда я могу его просто выкинуть) либо в какой-то момент применить и сделать его отрицательным, но тогда он станет $$$a_n \lt 0$$$ и я уже не смогу вернуть его в положительные числа. Представим, что я применю операцию к $$$a_n$$$. Какая тогда будет максимально возможная сумма?

Максимально возможно сумма может быть достигнута, если $$$a_1 \gt 0, a_2 \gt 0, \ldots, a_{n-1} \gt 0, a_n \lt 0$$$. Могу ли я получить такой массив?

Да, могу. Я могу сначала сделать все элементы $$$a_i \lt 0, i \lt n$$$ как в прошлой задаче, а потом применить операцию к $$$a_n$$$. Как тогда выглядит общее решение?

Общее решение выглядит так: я перебираю $$$i: a_i \gt 0$$$, что сумма $$$|a_1| + |a_2| + \ldots + |a_{i-1}| - a_i + (a_{i+1}+a_{i+2}+\ldots+a_n)$$$ максимальна. А затем строю последовательность операций так, чтобы сначала сделать $$$a_j \lt 0, j \lt i$$$, а затем применяю операцию к $$$a_i$$$. Как мне быстро для каждого $$$i$$$ находить такую сумму?

С помощью префиксных и суффиксных сумм. $$$P_i = P_{i-1}+|a_i|, S_i = S_{i+1}+a_i$$$.

Как я ранее говорил, я во многих задачах, в голове представляю, что у меня уже есть оптимальный ответ. Пусть в этой задаче он равен $$$x = \min(a_1,b_1)$$$. Тогда какие простые условия или наблюдения я могу сделать?

Я могу посмотреть, что написано в условии, получается, что мы хотим, чтобы в конце $$$a_1,b_1 \ge x$$$. То есть в конце остались элементы, не меньшие $$$x$$$. Теперь помотрю на саму операцию, в ней есть операции сравнения. Представим, что в массиве есть элементы $$$x$$$ и $$$x + 1$$$. Важно ли мне, что второй элемент больше первого?

Нет, не важно, я ведь хочу понять, могу ли я сделать ответ равным $$$x$$$. Тогда на какие две группы я могу разделить элементы массивов?

Я могу заменить элементы $$$a_i,b_i \ge x$$$ на $$$1$$$, а элементы $$$a_i,b_i \lt 0$$$ на $$$0$$$. Тогда как выглядит операция из условия?

Точно также, только теперь $$$S$$$ содержит нули и единицы. Тогда какие случаи бывают?

Самый просто случай, когда из обоих массивов мы берем по два нуля, тогда $$$S = (0,0,0,0)$$$ и мы вернем в каждый массив по нулю, то есть мы смогли удалить два нуля. Аналогично, если мы из массивов берем по две единицы. Какой остался случай?

Остался случай, когда из одного массива мы берем один ноль и одну единицу, тогда как выглядит $$$S$$$?

$$$S = (0, A, B, 1)$$$, где $$$0 \le A \le B \le 1$$$. То есть в массивы мы вернем $$$A,B$$$ и удалим один ноль и одну единицу вне зависимости от $$$A,B$$$. А что мы хотим сделать с нулями?

Мы хотим удалить все нулю. Как мы можем это делать?

Во-первых, мы можем удалить два нуля, если из обоих массивов мы берем по два нуля. А еще мы можем удалить один ноль по цене одной единицы. Тогда как нам выгодно поступать?

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

Тогда массивы выглядят как $$$0,1,1,1,1,1,0,1,0,1,0,1,1,1,0,\ldots$$$