Первое, на что я обратил внимание — на то, что в условии сказано, что мы хотим в итоге сделать так, чтобы все элементы стали равны некоторому числу $$$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 = {}$$$