10
правок
Изменения
Нет описания правки
Также пусть запросы приходят в таком порядке, что каждый следующий не меньше, чем предыдущий.
Для ответа на запрос будем использовать левосторонний двоичный поиск.
При этом после того как обработался первый запрос, запомним чему равно <tex>l</tex>, запишем его в переменную <tex>start\_lstartL</tex>. Когда будем обрабатывать следующий запрос, то проинициализируем левую границу как <tex>start\_lstartL</tex>. Заметим, что все элементы, которые лежат не правее <tex>start\_lstartL</tex>, строго меньше текущего искомого элемента, так как они меньше предыдущего запроса, а значит и меньше текущего. Значит инвариант цикла выполнен.
== См. также ==
