RMQ offline: вариация алгоритма Тарьяна
Общеизвестен Алгоритм Тарьяна для поиска LCA offline. Можно построить аналогичный алгоритм для решения задачи RMQ. Обратите внимание, что в статье по ссылке написано, что алгоритм работает за $O(n + m)$, что не совсем верно. Однако из-за того, что обратная функция Аккермана не больше $5$ для любых практически возможных ограничений ($n, m \le 10^{10^{10^{19500}}}$), можно считать, что это константа. Не смотря на это, в данной статье мы попытаемся соблюдать формальность.
Так как задача нам дана в оффлайне, мы можем отвечать на запросы в любом порядке. Давайте для каждого индекса массива сохраним все запросы, для которых этот индекс является правой границей. После чего пройдемся по массиву слева направо, постепенно отвечая на запросы для текущей правой границы. При этом будем еще поддерживать стек минимумов (не путать со стеком с минимумом), или как его еще называют «стек рекордов».
Заметим, что стек минимумов делит массив на отрезки: каждый элемент стека минимумов является минимумом на любом отрезке с левой границей от текущего элемента стека минимумов до следующего влево. Тогда чтобы найти минимум на отрезке, достаточно для левой границы отрезка найти ближайший справа элемент стека минимумов, он и будет являться минимумом на отрезке.
Как же мы будем находить этот самый ближайший элемент в стеке минимумов? Это можно делать при помощи бинпоиска по стеку, однако в таком решении асимптотика будет $O(n + m \log n)$, что нас не устраивает. Давайте поддерживать СНМ (систему непересекающихся множеств), в которой элементами будут являться индексы массива, а множествами — отрезки, высекаемые стеком минимумов, на которых минимум фиксирован. Тогда если мы в корне каждого дерева СНМ будем еще поддерживать минимум на множестве, то для данной левой границы достаточно дойти до корня ее дерева и там узнать ответ. Обратите внимание, что множества объединяются очень простым образом. Когда к нам пришел новый элемент, он сначала находится один в своем множестве, но когда мы удаляем со стека элемент, мы объединяем соответствующее множество с множеством текущей правой границы. Каждый элемент будет добавлен в стек (а следовательно, и удален) не более одного раза, так что мы сделаем $O(n)$ операций с СНМом. Асимптотика получается равной $O((n + q) \alpha(n))$, если использовать и эвристику сжатия путей, и ранговую эвристику.
Реализация доступна по ссылке.
Наиболее эффективная реализация доступна по ссылке.
Задачи для практики
- Задача на поиск максимума на отрезке.
- ОСТОРОЖНО! СПОЙЛЕРЫ К РОИ! Эту задачу можно очень просто сдать на высокий балл при помощи предложенного алгоритма.