RMQ offline с СНМ
Строго рекомендуется сначала прочитать про RMQ в окне.
От RMQ в окне к RMQ-offline
Раньше, решая задачу про RMQ в окне, мы хранили окно, в котором элементы были расположены по убыванию. Мы пользовались тем, что при добавлении элемента у нас двигается правая граница, а при удалении --- левая.
Теперь же сделаем сканлайн по правым границам. При их сдвиге элемент точно так же будет добавляться. К сожалению, у нас нарушилось условие на удаление при сдвиге $l$, потому что левые границы теперь двигаются в обе стороны.
СНМ
Тем не менее, мы все еще будем хранить элементы по убыванию в нашей структуре, но просто не будем делать никаких удалений. Вместо этого мы мысленно присоединим левую границу запроса к первому элементу справа от него. Этот элемент, очевидно, будет являться максимумом на текущем суффиксе массива --- от границы $l$ до границы $r$.
Таким образом, мы получаем следующие требования к структуре:
- Добавление элемента.
- Поддерживание убывающей последовательности как в RMQ в окне.
- Нахождение первого элемента справа, находящегося в последовательности.
Заметим, что при добавлении элемента он всегда оказывается в последовательности. Возможно, он рушит какие-то другие элементы. Тогда все индексы, которые раньше относились к этим элементам, теперь относятся к новому элементу. Это значит, что происходит слияние множеств. Такое слияние можно поддерживать с помощью СНМ, если внутри множества хранить еще и максимум в множестве.