Задача минимума на отрезке (RMQ) имеет множество решений. Это может решаться ДО, разрeженными таблицами, корневой декомпозицией и т.п.
Реализация каждой структуры занимает немало строк кода, какие-то асимптотические ограничения, ограничения по памяти и т.п.
Хорошо бы научиться делать запросы в оффлайн за \(O(n)\) в сумме.
Давайте перебирать все элементы и поддерживать монотонный стек/стек минимумов.
То есть перебираем по возрастанию \(i\) и поддерживаем стек минимумов.
Если в текущей точке есть запрос \([l;r], r=i\), то давайте рассмотрим стек минимумов, который мы нагенерировали.
Во-первых, значения стека возрастают, значит нам нужен первый элемент, который входит в промежуток. Во-вторых, кроме самих значений возрастают и индексы этих значений.
Значит можно использовать бинпоиск! Найдем самый левый элемент, индекс которого больше либо равен \(l\).
Почему минимум на отрезке точно есть в стеке? Так как мы рассмотрели только элементы до \(r\), то после минимума не может быть ни одного элемента больше него. Следовательно никакой элемент не мог "выкинуть" наш минимум.
Общая асимптотика: \(O(n \log{n})\)
Пусть мы также поддерживали стек минимумов. Для каждого элемента будем запоминать, кто его "выкинул" из стека, назовем это \(p_i\).
Когда мы обработали \(r\) элементов и нужно ответить на запрос \([l;r]\), рекурсивно запустимся от \(l\) и пока не найдем элемент, который никто не выкинул. Такой алгоритм будет работать за \(O(n^2)\)
Теперь применим эвристику сжатия путей - вызывая рекурсию, после нахождения минимума проставим всем посещенным элементам индекс минимума. В следующий раз мы за одну операцию окажемся сразу в нем.
Конечно, в худшем случае такой алгоритм будет работать все-таки за \(O(n\log{n})\), но фактически почти никогда не бывает такого варианта, а, если асимптотика так волнует, можно применить ранговую эвристику.
// todo: написать код