RMQ offline: вариация алгоритма Тарьяна



Общеизвестен Алгоритм Тарьяна для поиска LCA offline. Можно построить аналогичный алгоритм для решения задачи RMQ. Обратите внимание, что в статье по ссылке написано, что алгоритм работает за $O(n + m)$, что не совсем верно. Однако из-за того, что обратная функция Аккермана не больше $5$ для любых практически возможных ограничений ($n, m \le 10^{10^{10^{19500}}}$), можно считать, что это константа. Не смотря на это, в данной статье мы попытаемся соблюдать формальность.

Так как задача нам дана в оффлайне, мы можем отвечать на запросы в любом порядке. Давайте для каждого индекса массива сохраним все запросы, для которых этот индекс является правой границей. После чего пройдемся по массиву слева направо, постепенно отвечая на запросы для текущей правой границы. При этом будем еще поддерживать стек минимумов (не путать со стеком с минимумом), или как его еще называют «стек рекордов».

Давайте определим, что это такое. Пускай мы сейчас находимся на позиции $i$ массива. Тогда стек минимумов — это все возможные индексы массива, такие что они будут являться минимумом на каком-то отрезке, правая граница которого — $i$. Если упорядочить эти позиции по возрастанию, то соответствующие значения будут строго возрастать, потому что если постепенно расширять отрезок с фиксированной правой границей $i$ (то есть двигать левую границу налево), то каждый элемент этого стека станет минимумом на отрезке в тот момент, когда мы дойдем до него, а также некоторое время после этого, то есть он точно меньше, чем все числа правее него.

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

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

Как же мы будем находить этот самый ближайший элемент в стеке минимумов? Это можно делать при помощи бинпоиска по стеку, однако в таком решении асимптотика будет $O(n + m \log n)$, что нас не устраивает. Давайте поддерживать СНМ (систему непересекающихся множеств), в которой элементами будут являться индексы массива, а множествами — отрезки, высекаемые стеком минимумов, на которых минимум фиксирован. Тогда если мы в корне каждого дерева СНМ будем еще поддерживать минимум на множестве, то для данной левой границы достаточно дойти до корня ее дерева и там узнать ответ. Обратите внимание, что множества объединяются очень простым образом. Когда к нам пришел новый элемент, он сначала находится один в своем множестве, но когда мы удаляем со стека элемент, мы объединяем соответствующее множество с множеством текущей правой границы. Каждый элемент будет добавлен в стек (а следовательно, и удален) не более одного раза, так что мы сделаем $O(n)$ операций с СНМом. Асимптотика получается равной $O((n + q) \alpha(n))$, если использовать и эвристику сжатия путей, и ранговую эвристику.

Реализация доступна по ссылке.

Наиболее эффективная реализация доступна по ссылке.

Задачи для практики

  • Задача на поиск максимума на отрезке.
  • ОСТОРОЖНО! СПОЙЛЕРЫ К РОИ! Эту задачу можно очень просто сдать на высокий балл при помощи предложенного алгоритма.