RMQ offline с СНМ: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «Строго рекомендуется сначала прочитать про RMQ в окне. ==От RMQ в окне к RMQ-offline== Раньше, ре...») |
KiKoS (обсуждение | вклад) м |
||
Строка 17: | Строка 17: | ||
* Нахождение первого элемента справа, находящегося в последовательности. | * Нахождение первого элемента справа, находящегося в последовательности. | ||
− | Заметим, что при добавлении элемента он всегда оказывается в последовательности. Возможно, он рушит какие-то другие элементы. Тогда все индексы, которые раньше относились к этим элементам, теперь относятся к новому элементу. Это значит, что происходит слияние множеств. Такое слияние можно поддерживать с помощью [[ | + | Заметим, что при добавлении элемента он всегда оказывается в последовательности. Возможно, он рушит какие-то другие элементы. Тогда все индексы, которые раньше относились к этим элементам, теперь относятся к новому элементу. Это значит, что происходит слияние множеств. Такое слияние можно поддерживать с помощью [[СНМ]], если внутри множества хранить еще и максимум в множестве. |
Текущая версия на 18:21, 19 ноября 2020
Строго рекомендуется сначала прочитать про RMQ в окне.
От RMQ в окне к RMQ-offline
Раньше, решая задачу про RMQ в окне, мы хранили окно, в котором элементы были расположены по убыванию. Мы пользовались тем, что при добавлении элемента у нас двигается правая граница, а при удалении --- левая.
Теперь же сделаем сканлайн по правым границам. При их сдвиге элемент точно так же будет добавляться. К сожалению, у нас нарушилось условие на удаление при сдвиге $l$, потому что левые границы теперь двигаются в обе стороны.
СНМ
Тем не менее, мы все еще будем хранить элементы по убыванию в нашей структуре, но просто не будем делать никаких удалений. Вместо этого мы мысленно присоединим левую границу запроса к первому элементу справа от него. Этот элемент, очевидно, будет являться максимумом на текущем суффиксе массива --- от границы $l$ до границы $r$.
Таким образом, мы получаем следующие требования к структуре:
- Добавление элемента.
- Поддерживание убывающей последовательности как в RMQ в окне.
- Нахождение первого элемента справа, находящегося в последовательности.
Заметим, что при добавлении элемента он всегда оказывается в последовательности. Возможно, он рушит какие-то другие элементы. Тогда все индексы, которые раньше относились к этим элементам, теперь относятся к новому элементу. Это значит, что происходит слияние множеств. Такое слияние можно поддерживать с помощью СНМ, если внутри множества хранить еще и максимум в множестве.