RMQ в окне
Предварительно рекомендуется разобраться в задаче $RMQ$.
Постановка задачи
Дана задача $RMQ$ с ограничением на запросы:
$$l_i \le l_{i + 1}, r_i \le r_{i + 1}$$
Это значит, что при упорядочивании запросов по правой границе, они окажутся также упорядочены и по левой.
Решение задачи за $O(n)$
Будем идти по запросам в порядке сортировки и поддерживать элементы в окне. Заметим, что если элемент сейчас является максимальным в очереди, то все элементы левее него уже никогда не станут оптимальным ответом --- ведь они раньше удалятся из очереди. Значит, можно хранить не всю очередь, а только ее убывающую последовательность из суффиксных максимумов.
Как ее поддерживать? При сдвиге левой границы у нас иногда просто удалится один элемент. При сдвиге правой границы у нас добавится элемент, который может сломать условие суффиксного максимума для всех чисел, меньших его. Это какой-то суффикс очереди. Тогда мы честно его удалим и потом добавим элемент.
Поддерживать очередь можно с помощью deque, а работает алгоритм за $O(n)$ амортизированно, потому что каждый элемент добавится один раз и удалится один раз.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s