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

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

Значит, мы нашли некоторые $$$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$$$ как и раньше. А если нет, то обнуляем всё, посчитанное для отрезка с меньшим максимумом. В частности, ответ на объединённом отрезке будет равен ответу на отрезке с большим максимумом