Привет, codeforces!
У меня вопрос:
Если у нас есть массив $$$a$$$ длины $$$n$$$ (не обязательно перестановка), $$$L_i$$$ — индекс ближайшего слева от $$$i$$$ элемента массива, который $$$≥$$$ чем $$$a_i$$$, а $$$R_i$$$ — индекс ближайшего $$$>$$$ (строго большего!) справа, то какая хорошая оценка сверху на: $$$\sum\limits_{i=1}^n min(i - L_i, R_i - i)$$$?
Я знаю, что если $$$R_i$$$ — больше или равный, то это $$$O(n log n)$$$.
Буду рад услышать ваши ответы!
Кажется, что оценка должна быть такая же. Построим перестановку, где достигается: максимальный элемент в центр, остальные поровну распределяем между половинами и рекурсивно.
В итоге получаем, что есть 2 элемента со значением около $$$n/2$$$, 4 элемента со значением $$$n/4$$$, и так далее, в итоге что-то вроде $$$\log n$$$ слагаемых порядка $$$n$$$.
Если ввести порядок на одинаковых значениях слева направо, то получится сведение к предыдущему случаю.
Спасибо!
Если я не ошибаюсь, доказательство в блоге по ссылке неверно. Оно доказывает, что для каждого i есть не больше логарифма различных j, но этого недостаточно: на примере $$$1, 0, \ldots, 0, 1$$$ у каждого нуля одна единица слева и справа (если мы ищем первый слева и справа больший себя), то есть факт про логарифм различных выполнен (в данном случае ровно 1), но сумма минимумов квадратична.
Правильное доказательство можно получить так, считаем что дана перестановка. Построим декартово дерево на максимум по значениям на парах ключ значение $$$(i, a_i)$$$, тогда у вершины $$$i$$$ левый сын это отрезок до ближайшего большего слева, правый сын это отрезок до ближайшего большего справа, взяв меньшее из поддеревьев получаем оценку как в меньшем к большему на дереве, то есть $$$O(n \log n)$$$.
Еще, кажется так можно: будем поддерживать набор множеств из отрезков подряд идущих чисел, которые меньше текущего $$$x$$$. Перебираем $$$x$$$ в порядке возрастания, при увеличении $$$x$$$ объединим какие-то отрезки в один. Сделаем объединение, перелив меньшее множество в большее. Так как всего элементов $$$n$$$, суммарный размер всех множеств $$$n$$$, и при перемещении элемента из одного множества в другое размер множества перекидываемого элемента увеличивается хотя бы вдвое, следовательно, суммарно перекидываний, с одной стороны, $$$O(nlogn)$$$, с другой, та формула.
Я там в комментах нормально пруфанул)