Сегодня я придумал такую оптимизацию: если сейчас запрос сведён к [l, r], то можно брать за mid не (l + r) / 2, а l + (r — l) / 3, то есть треть отрезка. Тогда если ответ в этом запросе окажется в первой трети, то мы уменьшились в 3 раза, а не в 2, что очевидно лучше. Если же ответ окажется в другой части, то мы уменьшимся всего на 1/3, но тогда позже мы пройдёмся по новому mid этого запроса в той же итерации, и тогда мы сократимся ещё хотя-бы на 1/3. В таком случае останется как максимум 2/3*2/3=4/9 (даже меньше, т.к. в этом случае мы опять его сократим на этой итерации) части запроса, что меньше 1/2, то есть количество итерации сократится. Это должно достаточно часто ускорять решение. Ещё можно попробовать брать не треть, а допустим четверть, пятую или две пятых отрезка.