Попробуйте посмотреть в сторону крайних элементов (с индексами $$$0$$$ и $$$n-1$$$) и в сторону экстремальных (очень больших или очень маленьких

Давайте посмотрим на последний элемент. Что будет, если он очень большой по сравнению с остальными? Наверняка мы могли бы его "протащить" операциями усреднения до начала массива. Что я имею в виду:

Пусть $$$a_{n-1} = INF$$$ — очень большое число, невероятно более большое, чем $$$a_i$$$. Тогда давайте усредним $$$a_{n-2}$$$ и $$$a_{n-1}$$$, после чего оба этих числа будут порядка $$$\frac{INF}{2}$$$ (я намеренно игнорирую $$$\frac{a_{n-2}}{2}$$$, так как мы договорились, что $$$INF$$$ сильно больше $$$a_i$$$. Дальше усредним $$$a_{n-2}$$$ и $$$a_{n-3}$$$, оба этих числа станут $$$\frac{INF}{4}$$$. Продолжим так делать, пока не дойдём до самого начала, где оба числа станут порядка $$$\frac{INF}{2^{n-1}}$$$. Так как у каждого числа, кроме второго, слагаемое с $$$INF$$$ в 2 раза больше, чем у предшественника, а второе числа равно первому, то этот массив неубывающий, а значит ответ "Да"

В рассуждении выше использовалось то, что $$$INF$$$ бесконечно большой. По скромным оценкам, он должен быть хотя бы $$$2 ^ n \cdot \max\limits_{i=0}^{n-2} a_i$$$, что невероятно много для ограничений задачи.

Вот если бы числа $$$a_0, \ldots, a_{n-2}$$$ были бы равны нулю, нам бы хватило любого положительного числа $$$a_{n-1}$$$.

Теперь вопрос к читателю, а если мы ослабим условие и положим, что числа $$$a_0, \ldots, a_{n-2}$$$ равны между собой, то какого $$$a_{n-1}$$$ достаточно, чтобы упорядочить массив?

Несложно увидеть, что "все числа равны" и "все числа равны нулю" — это по своей сути одинаковые утверждения, потому что если мы вычтем из всех чисел некоторый $$$x$$$ до начала операций, то в итоге получится тот же массив, уменьшенный на $$$x$$$, потому что операция усреднения линейна относительно увеличения обоих аргументов на одно и то же число. Иными словами, операции с массивом $$$x, x, \ldots, x, a_{n-1}$$$ эквивалентны операциям с $$$0, 0, \ldots, 0, a_{n-1} - x$$$ и коль скоро $$$a_{n-1} - x \gt 0$$$, наш метод "протаcкивания" большего числа упорядочит массив

К сожалению, не во всех входных массивах так много одинаковых чисел. Можно ли решить эту проблему операциями усреднения?

К сожалению, не во всех входных массивах так много одинаковых чисел. Можно ли решить эту проблему операциями усреднения?

Оказывается, что да! Мы можем все числа сделать почти равными друг другу на любом отрезке операциями усреднения. Это означает, что если $$$mean$$$ — то среднее чисел на отрезке $$$[l, r)$$$, то для любого заранее выбранного $$$eps$$$ мы можем совершить такие операции усреднения, чтобы $$$\forall i \in [l, r) |a_i - mean| \lt eps$$$, то есть чтобы они все одновременно были близки к своему среднему с любой заранее заданной точностью

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

Утверждение выше даёт нам возможность утверждать более сильное условие на $$$a_{n-1}$$$, вне зависимости от конкретной структуры чисел перед ним. Сформулируйте его

Пускай $$$mean$$$ — среднее среди чисел $$$a_0, a_1, \ldots, a_{n-2}$$$, тогда если $$$a_{n-1} \gt mean$$$, то ответ "Да".

Замечание: Критически важно, чтобы знак был строгим

Как же достигать отсортированного массива? Давайте сначала усредним префикс длины $$$n-1$$$ так, чтобы $$$|a_i-mean|$$$ был меньше $$$\frac{a_n-mean}{2^n}$$$. Так как это положительное число, мы можем так сделать. Дальше вычтем $$$mean$$$ из всех чисел и окажется, что последнее число огромное по сравнению со всеми остальными, а такую задачу мы уже умеем решать

Мы рассмотрели выше только последнее число. Теперь попробуйте посмотреть на первое число

Конечно, есть ещё похожий случай, в котором ответ всегда "Да". Это случай, когда первое число очень маленькое, а именно — когда оно строго меньше, чем среднее чисел $$$a_1, a_2, \ldots, a_{n-1}$$$

Действительно, мы умеем упорядочивать массив и в таком случае. Давайте усредним все числа, кроме самого первого, чтобы все они отличались от среднего в $$$2^n$$$ раз меньше, чем разность между средним и $$$a_0$$$. Тогда теперь усреднением $$$a_0, a_1$$$, затем $$$a_1, a_2$$$ и так далее до $$$a_{n-2}, a_{n-1}$$$ мы получим отсортированный массив, похожим "протаскиванием", но только маленького числа

Кажется, что эти два случая — лишь частное какого-то более общего правила, хотя бы потому что крайние числа выделяются. Например, если предпоследнее число очень большое — ответ тоже должен быть "Да". Попробуйте обощить эти два случая и получить ещё больше вариантов, где ответ "Да"

Ранее мы усредняли только первые или последние $$$n-1$$$ чисел. Чтобы обобить этот подход, давайте усредним произвольное количество чисел в начале и в конце

Пускай есть такое $$$t$$$, что среднее на полуинтервале $$$[0, t)$$$ меньше, чем среднее на полуинтервале $$$[t, n)$$$. Тогда мы можем усреднить числа на этих полуинтервалах достаточно точно, чтобы провернуть аналогичное протаскивание:

Сделаем усреднение $$$t-1, t$$$, после чего усредним все пары на левом полуинтервале, справа налево и все пары на правом полуинтервале, слева направо. Для некоторой достаточной точности эти полуинтервалы будут неубывающими. Более того, число $$$a_{t-1}$$$ будет не больше, чем $$$a_{t}$$$, так что в итоге полученный массив будет неубывающим, а значит мы получили следующее:

Если для какого-то $$$t$$$ среднее на полуинтервале $$$[0, t)$$$ строго меньше, чем среднее на $$$[t, n)$$$, то ответ всегда "Да"

Конечно, нет. Если массив изначально состоит из равных чисел, то ответ "Да", хотя все средние равны на любых двух отрезках. Поэтому нужно думать дальше

Давайте попробуем упростить условие для "Да", которое мы вывели

Обозначьте за $$$A_{i}$$$ сумму первых $$$i$$$ чисел и попробуйте его упростить

Условие выглядит так, что левое среднее меньше правого среднего. То есть $$$\frac{A_i}{i} \lt \frac{A_n-A_i}{n - i}$$$. Давайте домножим на знаменатель и раскроем скобки

$$$A_i \cdot n - A_i \cdot i \lt A_n \cdot i - A_i \cdot i$$$ и после упрощений $$$A_i \cdot n \lt A_n \cdot i$$$ то есть $$$\frac{A_i}{i} \lt \frac{A_n}{n}$$$. Простым языком — среднее на префиксе меньше среднего во всём массиве. Даже логично, что это эквивалентно первому условию

Это намного удобнее, потому что теперь мы можем следить только за средними на префиксах, не обращая внимание на средние на суффиксах

Подумайте теперь вот о чём: изначально все средние на префиксах не меньше глобального среднего. Может ли тогда хотя бы одно из них стать больше в результате усреднений?

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

Пускай это было усреднение между $$$i$$$ и $$$i+1$$$, тогда все средние до $$$i-1$$$ и после $$$i+1$$$ не изменились, ведь сумма на этих префиксах осталась та же. То есть, что-то могло произойти только с средним на префиксе длины $$$i$$$

Поймём что именно — раньше сумма была $$$A_i$$$, а теперь $$$A_{i-1} + \frac{a_i + a_{i + 1}}{2}$$$. Если присмотреться, она равна $$$\frac{A_{i-1} + A_{i+1}}{2}$$$, то есть сумма на префиксе стала средним между двумя соседними суммами. А среднее стало средне взвешенным между ними, то есть

$$$\frac{A_{i-1} + A_{i+1}}{2 \cdot i} = \frac{i - 1}{2 \cdot i} \cdot \frac{A_{i-1}}{i-1} + \frac{i + 1}{2 \cdot i} \cdot \frac{A_{i+1}}{i+1}$$$

Но до этого момента все средние на префиксах были не меньше среднего во всём массиве. Тогда и новое среднее не меньше. А значит, нового меньшего среднего появиться не могло

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

Какой вид имеют средние на префиксах для отсортированного по неубыванию массива?

Ответ прост — средние тоже не убывают. А значит, если мы достигли требуемой сортировки, то все средние на префиксах меньше либо равны глобальному среднему (что в то же время равно среднему на последнем префиксе, $$$\frac{A_n}{n}$$$). Но, если изначально они все были больше либо равны, то меньшими уже не станут. Значит они должны быть все равны

Но также дело в том, что среднее на префиксе будет равно $$$\frac{A_n}{n}$$$ только если оно изначально равно, либо оба соседа были равны (иначе в оценке выше будет строгий знак неравенства)

Замечание: В данном случае положим нулевое среднее $$$\frac{A_0}{0}$$$ равное $$$\frac{A_n}{n}$$$ из-за того, что операция усреднения для чисел $$$a_0, a_1$$$ ведёт себя согласованно с этим определением

Итого, мы можем получить нужное равенство на позиции $$$i$$$, если оно выполнено на обеих позициях $$$i-1$$$ и $$$i+1$$$. Нам нужно проверить, можно ли получить равенства на всех позициях

Это задача уровня В Div 2

Давайте выпишем $$$n + 1$$$ число, 0 или 1, где 0 означает равенство среднего на префиксе общему среднему, а 1 — неравенство. Первое и последнее числа — нули. Мы можем выбрать два нуля через одну позицию и сделать среднее между ними число нулём. Можно ли получить все нули?

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

Поймите, что ответ зависит только от $$$pos[k]$$$, а не от самого $$$k$$$

Действительно, бинарный поиск будет искать элемент, находящийся на позиции $$$pos[k]$$$ и сделает точно такие же шаги вне зависимости от самого значения $$$k$$$, если массив $$$a$$$ отсортирован. Осталось только посчитать для каждой позиции за сколько шагов бинпоиск до неё дойдёт

Это совсем уж не сложно :)

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

Попробуйте посмотреть на эту сумму не через значения $$$k$$$, а через их позиции в массиве

Так как $$$f(a,k,1, n)$$$ зависит только от позиции числа $$$k$$$ в массиве и мы считаем сумму по всем $$$k$$$, это аналогично сумме по всем позициям для массива из различных чисел, так что

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

Действительно, для каждого строго возрастающего массива сумма значений $$$f$$$ одинакова, поэтому нужно будет лишь умножить сумму для одного массива на количество таких массивов. Здесь становится понятно, что нужно возвращаться к массивам с повторяющимися числами

В более простом случае нам помогал взгляд на сумму через позицию в массиве, на которой бинпоиск останавливается. Давайте попробуем здесь посчитать, на скольких массивах бинпоиск остановится ровно на позиции $$$i$$$

В отличие от строго возрастающих массивов, где для каждой позиции есть бинпоиск, который в ней останавливается, в общем случае это неверно. Например, если массив состоит только из единиц, бинпоиск остановится только на индексе $$$\frac{n - 1}{2}$$$ (в 0-нумерации). На самом деле, бинпоиск, который ищет число $$$k$$$, остановится в позиции $$$i$$$, если $$$a_i = k$$$ и он не остановился ранее. К счастью, до того, как прийти в позицию $$$i$$$, бинпоиск проверял конкретный набор позиций, зависящий только от $$$i$$$. Обозначим его $$$Poses(i)$$$

Итого, нам нужно научиться считать количество массивов, в которых элемент с индексом $$$i$$$ не совпадает ни с одним из элементов с индексом из $$$Poses(i)$$$. Как бы это посчитать?

Давайте сначала попробуем упростить условие. Несмотря на то, что $$$|Poses(i)|$$$ порядка $$$log(n)$$$, это всё равно много и неудобно

Заметим, что массив $$$a$$$ монотонный, а значит, что если для некоторого $$$j \in Poses(i)$$$ и $$$j \lt i$$$ выполнено $$$a_j = a_i$$$, то и для самого правого $$$j \lt i$$$ тоже, а значит можно оставить только его. Аналогично выкинем все $$$j \gt i, j \in Poses(i)$$$, кроме самого левого из них. У нас останется лишь два индекса, обозначим их за $$$l_i$$$ и $$$r_i$$$ соответственно. Замечу также, что они могут и не быть определены. В конце концов, индексов $$$j \lt i$$$ может не существовать

Кажется, что посчитать количество массивов с условием, что значения на каких-то двух индексах не равны значению на третьем индексе — сложновато. А если условие заменить на равенство, то, наоборот, мы уже будем знать, что все промежуточные числа тоже совпадают с $$$a_i$$$. Давайте попробуем посчитать количество всех массивов и вычесть из них неподходящие

Количество всех массивов считается довольно стандартным образом. Давайте сделаем разумую вещь для монотонным массивов — перейдём к массиву разностей $$$d$$$, где $$$d_0$$$ = $$$a_0 - 1$$$, $$$d_i = a_i - a_{i-1}$$$, $$$d_n = m - a_{n-1}$$$. На него есть два условия: $$$d_i \geq 0$$$ и $$$\sum\limits_{i=0}^n d_i = m - 1$$$. А уже количество таких массивов можно вычислить через задачу о шарах и перегородках, по сути это она и есть — если не слышали ранее — обязательно ознакомьтесь, это очень стандартная комбинаторная задача. При помощи предподсчёта факториалов мы сможем считать число сочетаний $$$C(n, k)$$$ за $$$O(1)$$$ и без труда найдём общее число массивов.

А что насчёт количества неподходящих массивов? Если все элементы с $$$a_{l_i}$$$ по $$$a_i$$$ равны, это означает, что в массиве разностей $$$d_{l_i+1} = d_{l_i + 2} = \ldots = d_i$$$, а значит это количество равно количеству массивов с той же суммой $$$m-1$$$, но уже не из $$$n$$$, а из $$$n - (i - l_i)$$$ элементов, так как все оставшиеся равны нулю. И, чтобы формула стала полностью верной, нужно вычесть такое же количество для $$$r_i$$$. Но при этом мы два раза вычтем количество массивов, для которых все элементы с $$$l_i$$$ по $$$r_i$$$ совпадают. Давайте добавим их обратно, посчитав по уже знакомой формуле

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

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

Значит, мы нашли некоторые $$$k$$$ и максимальное $$$k$$$ не меньше всех их

На прошлом шаге мы нашли достаточно простые примеры значений $$$k$$$, а именно — расстояния между клетками с одинаковым значением. А может быть мы сможем доказать, что максимальное $$$k$$$ получается именно так и является расстоянием между двумя клетками с одинаковым значением?

Давайте попробуем это доказать, для этого рассмотрим два произвольных отрезка равной $$$k_{max}(a)$$$ длины с одинаковым мультимножеством значений. Заметим, что они должны пересекаться или быть соседними, так как иначе мы можем добавить к ним все те позиции, которые находятся между ними. На рисунке ниже такие отрезки выделены красным и зелёным, а синие клетки обозначают то, что значения в них, как в мультимножествах, совпадают

Значит, если мы посмотрим на самый левый элемент синего левого отрезка, то такой же элемент есть в синем правом отрезке. Где же он может быть? А он может быть только самым левым элементом правго отрезка, иначе данное $$$k$$$ не максимальное, ведь оно будет меньше, чем расстояние между позициями с одинаковыми значениями

А это, в свою очередь, значит, что такое $$$k$$$ мы представили как расстояние между равными элементами, которые выделены на картинке фиолетовым

Итак, мы поняли, что $$$k_{max}(a)$$$ — это максимально расстояние между двумя равными элементами массива. Как его считать быстро?

Нас интересует только максимальное расстояние, так что для каждого значения $$$x$$$ элемента массива мы выберем максимальный и минимальный индекс — их разность будет максимальным расстоянием между элементами, равными $$$x$$$. И теперь, чтобы найти ответ, нужно взять максимальное из получившихся для каждого $$$x$$$ значений. Нетрудно заметить, что такое решение работает за $$$O(n)$$$ при ограничениях задачи

Попробуйте развить идею из доказательства того, что максимальное $$$k$$$ — это максимальное расстояние между двумя одинаковыми элементами

Вспомним и продолжим доказательство того, что $$$k$$$ — это максимальное расстояние между двумя одинаковыми элементами. Всё также рассматриваем два отрезка длины $$$k$$$. Мы уже поняли, что два элемента на фиолетовых (след рис) позициях совпадают. Но тогда и два красных элемента совпадают, иначе $$$k$$$ не максимальное. Тогда расстояния между всеми соответствующими элементами непересекающихся отрезков равно $$$k$$$

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

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

Остался последний шаг — как посчитать количество таких отрезков за $$$O(n)$$$?

Давайте разделим все элементы на те, у которых через $$$k$$$ клеток одинаковый элемент и остальные. Нас интересует количество подотрезков целиком из первого множества клеток. Довольно стандартный шаг для такой подзадачи — давайте рассмотрим непрерывные отрезки из первого множества. Заметим, что интересующий нас отрезок целиком лежит в каком-то одном непрерывном отрезке. Всего различных подотрезков в отрезке длины $$$len$$$ ровно $$$\frac{len \cdot (len - 1)}{2}$$$

Итого, нам требуется разбить первое множество клеток на отрезки и сложить значения $$$\frac{len \cdot (len - 1)}{2}$$$, где $$$len$$$ — длина отрезка

Нам нужно считать количество подотрезков из элементов, удовлетворяющих свойству. Но свойство "элемент с индексом на $$$k$$$ больше равен данному элементу" довольно редкое, если $$$k$$$ — это максимум. К тому же, оно не может поменяться у большого числа элементов

А если быть точнее, для каждого $$$x$$$ этому свойству удовлетворяет не более одного элемента, равного $$$x$$$. Это значит, что если мы меняем $$$a_i$$$ на $$$x$$$, а до этого значение $$$a_i = y$$$, то свойство могло поменяться лишь на четырёх позициях — на том элементе со значением $$$y$$$, который раньше удовлетворял условию, на том, который теперь удовлетворяет условию и аналогично для элементов $$$x$$$.

Осталось лишь быстро пересчитывать ответ при изменении условия в одной клетке

Может быть, стоит хранить значения услвоия в какой-то структуре данных, которая поддерживает изменения в точке и подсчёт ответа на всём массиве?

Давайте хранить значения условия в дереве отрезков. Пусть в массиве стоит 1, если условие выполнено, и 0 иначе. В такой постановке нам нужно посчитать количество непрерывных подотрезков их единиц. Тогда нам нужно хранить ответ для отрезка и описать операцию $$$merge$$$, которая будет отвечать за пересчёт ответа при объединении отрезков

Итак, если два отрезка $$$[l, m)$$$ и $$$[m, r)$$$ массива условий объединяются, но элементы $$$st[m-1]$$$ и $$$st[m]$$$ не являются одновременно единицами, то их ответы нужно просто сложить, так как новых отрезков из единиц не добавилось. А вот если оба элемента равны 1, тогда нужно произвести более сложное объединение. На самом деле видно, что нам нужно знать длины максимального суффикса $$$[l, m)$$$ из единиц и максимального префикса $$$[m, r)$$$ из единиц. Пусть их длины $$$len_1$$$ и $$$len_2$$$, соответственно. Тогда в отрезке $$$[l, r)$$$ появляется $$$len_1 \cdot len_2$$$ новых непрерывных отрезков из единиц

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

Приведу пример как мы посчитаем длину максимального префикса из единиц, длина максимального суффикса считается симметрично. Если длина максимального префикса отрезка $$$[l, m)$$$ ровно $$$m - l$$$, то длина максимального префикса отрезка $$$[l, r)$$$ равна длине максимального префикса $$$[m, r)$$$ плюс $$$m - l$$$. В противном случае это просто длина максимального префикса $$$[l, m)$$$ и он не продляется

На самом деле условие, равное 0 или 1 — это некоторое упрощение. Мы для каждого $$$x$$$ знаем расстояние между первым и последним элементами, равными $$$x$$$. Давайте переформулируем условие в чуть более гибком виде

Ранее мы записывали в самый левый элемент, равный $$$x$$$ 0, если расстояние до самого правого $$$x$$$ меньше $$$k$$$, а иначе записывали $$$1$$$. Давайте просто записывать в элемент наибольшее такое $$$k$$$, что элемент с индексом на $$$k$$$ больше ему равен

И так как нас интересует только равно значение в элементе максимальному написанному $$$k$$$ или нет, можно по-прежнему записывать не нули только в самый левый элемент, равный $$$x$$$

Теперь сформулируйте задачу для нового массива условий и доработайте ДО для её решения

Теперь, как мы видим, мы всё ещё должны посчитать количество непрерывных отрезков, только не со значением 1, а с максимальным в массиве значением. Это очень похоже на задачу поиска количества максимумов в дереве отрезков

Теперь мы будем хранить помимо всех предыдущих значений в вершине то, какой элемент на её подотрезке максимальный и, соответственно, для какого элемента посчитано количество непрерывных отрезков

А в операции $$$merge$$$, если максимальные элементы обоих отрезков совпадают, мы просто делаем такой же $$$merge$$$ как и раньше. А если нет, то обнуляем всё, посчитанное для отрезка с меньшим максимумом. В частности, ответ на объединённом отрезке будет равен ответу на отрезке с большим максимумом

Достаточно даже решения, например, за $$$O(n^2 \cdot m^2)$$$

Можно явным образом поменять каждый элемент матрицы $$$a$$$ на противоположный и для каждой замены решить задачу о черепашке. Замен будет $$$n \cdot m$$$, одна черепашка решается за $$$O(n \cdot m)$$$, итого решение за $$$O(n^2 \cdot m^2)$$$

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

Если мы изменим значение в клетке $$$(i, j)$$$, то изменятся только награды тех путей, которые проходят через клетку $$$(i, j)$$$. Также несложно понять, что награда каждого такого пути уменьшится на $$$2 \cdot {a_i}_j$$$ по сравнению с изначальной задачей

Теперь мы поняли, что нам достаточно посчитать максимальный по награде путь, проходящий через клетку $$$(i, j)$$$ и максимальный по награде путь, не проходящий через неё. Но, так как такие значения придётся считать для каждой клетки, нужно это делать быстро. Начнём с простого: как посчитать максимальный путь из $$$(0, 0)$$$ в $$$(n - 1, m - 1)$$$, проходящий через $$$(i, j)$$$?

Любой такой путь разбивается на два пути — из $$$(0, 0)$$$ в $$$(i, j)$$$ и из $$$(i, j)$$$ в $$$(n - 1, m - 1)$$$, поэтому нам нужно посчитать максимальный путь из $$$(0, 0)$$$ в $$$(i, j)$$$ и максимальный путь из $$$(i, j)$$$ в $$$(n - 1, m - 1)$$$ по-отдельности, сложить и вычесть $$${a_i}_j$$$ (так как мы учли это значение как награду обоих путей. Нам повезло, что в задаче о черепашке мы считаем максимальную награду пути от $$$(0, 0)$$$ до всех клеток $$$(i, j)$$$ разом! Давайте тогда запустим две черепашки — одну из клетки $$$(0, 0)$$$ и назовём её $$$turtle1$$$. То есть $$${turtle_i}_j$$$ будет максимальной наградой пути из $$$(0, 0)$$$ до $$$(i, j)$$$. Вторую же черепашку запустим из клетки $$$(n - 1, m - 1)$$$ с возможностью ходить только вверх и влево и назовём её $$$turtle2$$$. Таким образом, $$${turtle2_i}_j$$$ будет равно максимальной награде пути из $$$(n - 1, m - 1)$$$ в $$$(i, j)$$$, что равно максимальной награде пути из $$$(i, j)$$$ в $$$(n - 1, m - 1)$$$

Теперь мы можем выразить интересующую нас величину как $$${turtle1_i}_j + {turtle2_i}_j - {a_i}_j$$$

Нам осталось лишь посчитать награду максимального пути, не проходящего через клетку $$$(i, j)$$$. Давайте подумаем, можно ли это значение выразить через длины путей, проходящих через какие-то другие клетки доски?

Оказывается, что можно. Давайте заметим, что путь не может проходить одновременно через клетку $$$(i, j)$$$ и через клетки, которые находятся слева снизу или справа сверху от неё. Такие клетки выделены на рисунке ниже

Тогда нам достаточно посчитать максимальную награду пути, проходящую через одну из таких клеток.

Но этих клеток очень много! Поэтому давайте сократим множество до диагонали? Путь черепашки проходит через ровно одну клетку диагонали, поэтому, если он не проходит через $$$(i, j)$$$, то проходит через одну из остальных клеток!

Это значит, что максимальный путь, не проходящий через $$$(i, j)$$$ — это максимум из максимальных путей, проходящих через другие клетки той же диагонали.

Давайте посчитаем ответ для каждой диагонали отдельно за $$$O(L)$$$, где $$$L$$$ — это длина диагонали. Чтобы понять, как прийти к такому решению, попробуйте выразить ответ для одной клетки диагонали формулой

Как и было сказано, давайте выразим ответ понятной формулой. Пускай $$$(i, j)$$$ — самая нижняя клетка данной диагонали, тогда все клетки диагонали имеют координаты $$$(i - d, j + d)$$$, где $$$0 \leq d \lt L$$$. Обозначим за $$$f_d$$$ награду наибольшего пути, проходящего через $$$(i - d, j + d)$$$. Мы знаем, что $$$f_d = {turtle1_{i-d,}}_{j+d} + {turtle2_{i-d,}}_{j+d} - {a_{i-d,}}_{j+d}$$$. Как было замечено, награда наибольшего пути, не проходящего через $$$(i - d, j + d)$$$ равна $$$\max\limits_{0 \leq t \lt L, t \neq d} f_t$$$, или, что то же самое, $$$max(\max\limits_{0 \leq t \lt d} f_t, \max\limits_{t + 1 \leq t \lt L} f_t)$$$, то есть максимум на префиксе и суффиксе. А для вычисления ответа необходимо также взять максимум полученного значения с максимальным путём, проходящим через клетку $$$(i - d, j + d)$$$, что равно $$$f_d - 2 \cdot {a_{i - d,}}_{j + d}$$$

Имея перед глазами формулу в таком виде, несложно догадаться, что нам достаточно посчитать префиксные и суффиксные максимумы из значений $$$f_d$$$, чтобы посчитать ответ в каждой точке за $$$O(1)$$$.

Формально, пускай нам дан массив $$$a$$$ размера $$$n$$$, такой, что для $$$0 \leq i \lt n$$$ верно $$$0 \leq a[i] \lt N$$$. Требуется найти длину наибольшей возрастающей подпоследовательности массива $$$a$$$

Конечно же решение использует метод динамического программирования. Мы будем рассматривать элементы $$$a[i]$$$ в порядке увеличения индекса $$$i$$$ и хранить массив $$$dp$$$ размера $$$N$$$, так, что $$$dp[x]$$$ равно наибольшей возрастающей подпоследовательности, последний элемент которой ровно $$$x$$$. Тогда, если массив рассчитан корректно для шага $$$i-1$$$, мы можем посчитать длину наибольшей возрастающей подпоследовательности, которая заканчивается в $$$a[i]$$$ как $$$cnt = 1 + \max\limits_{0 \leq x \lt a[i]} (dp[x])$$$, так как предыдущее число в подпоследовательности должно быть меньше $$$a[i]$$$. Теперь, если $$$cnt \gt dp[a[i]]$$$, нужно обновить $$$dp[a[i]] := cnt$$$

В процессе пересчёта массива $$$dp$$$ нам потребовалось две операции: получение максимума элементов массива на отрезке и изменение одного элемента. Обе эти операции можно делать деревом отрезков за $$$O(log(N))$$$ на одну операцию

Так как мы каждую операцию вызываем не более $$$n$$$ раз, получается сложность по времени $$$O(n \cdot log(N))$$$

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

Посмотрите "Решение задачи о нахождении LIS", чтобы понять, как обрабатывать удлинение префикса/суффикса

Если мы добавляем элемент $$$a[cur]$$$ к префиксу $$$A$$$, то нам нужно посчитать $$$cnt = 1 + \max\limits_{0 \leq x \lt a[cur]} sta[x]$$$. Если $$$cnt \gt sta[a[cur]]$$$, обновляем $$$sta[a[cur]] := cnt$$$

Если мы добавляем элемент $$$a[cur]$$$ к суффиксу $$$B$$$, то нам, аналогично, нужно посчитать $$$cnt = 1 + \max\limits_{a[cur] + 1 \leq y \lt N} stb[y]$$$. Если $$$cur \gt stb[a[cur]]$$$, обновляем $$$stb[a[cur]] := cnt$$$

Заметим, что когда мы удаляем элемент из префикса/суффикса, мы "откатываем" последнее обновление, которое сделали. А именно — увеличение максимума. Поэтому давайте придумаем, как хранить историю изменений прямо в Дереве отрезков

Давайте запоминать в листе Дерева отрезков не только текущее значение, но и все такие значения, которые не меньше своих предшественников. Будем хранить их в стэке, чтобы было удобно изменять значение на предыдущее. Теперь $$$sta[x]$$$ — это верхнее значение в вершине дерева, соответствующего индексу $$$x$$$. Изначально в стэке лежит только $$$0$$$

Теперь наша операция изменения распалась на две разные операции:

$$$add(x, val)$$$ — если $$$sta[x] \leq val$$$ — добавляем val в стэк вершины x сверху $$$del(x, val)$$$ — если $$$sta[x] == val$$$ — убираем из стэка вершины x элемент

А процедура удаления элемента $$$a[cur - 1]$$$ из префикса $$$A$$$ выглядит совсем просто. Посчитаем уже запомнившееся всем $$$cnt = 1 + \max\limits_{0 \leq x \lt a[cur - 1]} sta[x]$$$ — это ровно то значение, которое мы считали при добавлении $$$a[cur - 1]$$$ в префикс. Теперь если $$$sta[a[cur - 1]] == cnt$$$, значит мы делали соответствующее обновление операцией $$$add(a[cur - 1], cnt)$$$ и его нужно удалить со стэка, иначе значение не обновлялось и стэк трогать не нужно

Для массива $$$stb$$$ требуются аналогичные действия

Замечание. Попробуйте понять почему в операции $$$add$$$ нельзя заменить условие $$$sta[x] \leq val$$$ на $$$sta[x] \lt val$$$

Заметим, что если подпоследовательность проходит через $$$a[cur]$$$, то все её элементы в $$$A$$$ строго меньше $$$a[cur]$$$, а все элементы в $$$B$$$ строго больше, чем $$$a[cur]$$$

Из подсказки следует вывод о том, что длина такой последовательности равна $$$1 + \max\limits_{0 \leq x \lt a[cur]} sta[x] + \max\limits_{a[cur] + 1 \leq x \lt N} stb[x]$$$, так как часть такой подпоследовательности, находящейся в $$$A$$$, заканчивается на элемент $$$x \lt a[cur]$$$, а часть в $$$B$$$ начинается на элемент $$$y \gt a[cur]$$$. И $$$+1$$$ за счёт того, что сам элемент также участвует в последовательности

Обозначим последний элемент подпоследовательности, находящийся в $$$A$$$, через $$$x$$$. А первый элемент подпоследовательности, находящийся в $$$B$$$, через $$$y$$$. При этом $$$x \lt y$$$. Поэтому длина максимальной возрастающей подпоследовательности равна $$$\max\limits_{0 \leq x \lt y \lt N} sta[x] + stb[y]$$$

Давайте расположим естественным образом в квадрате $$$N \times N$$$ наши элементы $$$sta[x] + stb[y]$$$ — в клетке $$$(x, y)$$$ расположено значение $$$sta[x] + stb[y]$$$. Ниже на рисунке нарисована такая таблица и оба массива $$$sta$$$ и $$$stb$$$, в тех клетках, где $$$x \lt y$$$ написана сумма. Нам нужно вычислить максимум на таком треугольнике из клеточек

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

Для ответа на вопрос выше воспользуемся необычным устройством нашей таблицы. Если бы нам нужно было бы вычислить максимум на прямоугольнике $$$[lx, rx) \times [ly, ry)$$$, нужно было просто посчитать $$$\max\limits_{lx \leq x \lt rx} sta[x] + \max\limits_{ly \leq y \lt ry} stb[y]$$$, так как чтобы посчитать максимальную сумму в такой таблице — достаточно вычислить максимумы слагаемых

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

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

Замечание. Так как в задаче в качестве $$$N$$$ мы можем выбрать любое число, большее $$$10^6$$$, давайте выберем степень двойки для удобства

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

Запустим рекурсивный подсчёт, в котором будет $$$log(N)$$$ уровней. На первом уровне мы вычислим максимум на $$$1$$$ прямоугольнике, на втором уровне на $$$2$$$ прямоугольниках, на третьем на $$$4$$$-ех и так далее. Итого мы вычислим ответ на $$$O(N)$$$ (а если быть совсем уж точным, то на N — 1 прямоугольнике, смотри рисунок) прямоугольниках

Каждое вычисление работает за $$$O(log(N))$$$, так как у нас построены деревья отрезков на массивах $$$sta$$$ и $$$stb$$$. Итого пересчёт работает за $$$O(N \cdot log(N))$$$

Как избавиться от логарифмического множителя в асимптотике? Заметим, что он получается из-за запросов в Дерево Отрезков. А ещё заметим тот факт, что наши запросы имеют чёткую структуру

Обратим внимание на то, что так как при переходе к меньшему прямоугольнику мы делим сторону ровно пополам, ответ на наш запрос всегда целиком находится в одной вершине дерева отрезков для массива $$$sta$$$ и $$$stb$$$, поэтому максимум на таких отрезках мы можем вычислять за $$$O(1)$$$. Итого получается подсчёт максимума на треугольнике за $$$O(N)$$$

При таком действии в таблице меняется один столбец или одна строка. Сколько треугольников задевает такое изменение?

Наверняка Вы поняли по подсказке, что такое изменение задевает не более $$$log(N)$$$ треугольников, потому что строка или столбец пересекает максимум один треугольник на каждом уровне построения треугольников (ответ 4.3). Получается, теоретически возможно пересчитать ответ во всех изменившихся треугольниках за $$$O(log(N))$$$

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

Заметим, что если изменился маленький треугольник, то изменился треугольник вдвое большего размера, который его содержит. Тогда нам достаточно найти наименьший изменившийся треугольник и проитерироваться по всем содержащим его треугольникам. Кстати, это тоже можно реализовать через дерево отрезков

Тогда мы можем пересчитывать ответ за $$$O(log(N))$$$ на запрос, что нам и требовалось