Представьте ситуацию, где мы хотим найти такое $$$a_j$$$, для любого $$$a_i$$$, что оно удовлетворяло бы:
Насколько эффективный способ Вы знаете?
Как подсказал shufl999dka, эту задачу можно решить за $$$O(n)$$$.
Представим теперь несколько более сложную ситуацию, где мы хотим найти такое $$$a_j$$$ для любого $$$x$$$ и полуинтервала $$$[l; r)$$$, который бы удовлетворял теперь таким условиям:
Первое решение, которое пришло мне в голову было за $$$O(n\log^2{n}):$$$
Благодаря MrDindows и bicsi мы знаем решение за $$$O(n\log{n})$$$:
Также можно посмотреть демонстрацию обоих решений в конкретной задаче: 1237D - Сбалансированный плейлист
Решение за $$$O(n\log^2{n})$$$ — 732 мс 62741630
Решение за $$$O(n\log{n})$$$ — 77 мс 62881402
Если вы умеете решать это эффективнее, то я с удовольствием этому научусь из комментариев.
Есть решение за $$$O(n)$$$ памяти и $$$O(n)$$$ операций.
Подумайте про стеки :)
Будем идти по массиву справа налево и поддерживать стек $$$st$$$. Когда встретили какой-то элемент в массиве, удаляем из стека все элементы, пока он не пуст и пока на его вершине лежит элемент, больший или равный $$$a_i$$$. Если стек пуст, то после этого элемента массива не было элементов, которые меньше его, иначе вершина — искомый нами элемент. После — ложим $$$a_i$$$ в стек и продолжаем идти влево.
Это хорошее решение, которое я позже добавлю в запись, но оно, очевидно, решает только первую задачу.
Бинпоиск не нужен, так как структура ДО уже делит интервалы пополам. Поэтому достаточно одного дфс-а по дереву, в котором мы идем в вершину только в том случае, если минимум в нем меньше $$$x$$$ и если интервал, за который отвечает вершина, пересекается с интервалом из запроса.
Я не совсем этого понимаю. Мы ведь в худшем случае будем заходить во все вершины, а это $$$O(n)$$$ операций, разве нет?
Нет, максимум лог вершин на левой границе запроса, такие что частично пересекаются по интервалу, плюс лог вершин чтоб собственно спуститься до листа с ответом.
Мы смотрим на левого сына, ответ там меньше $$$x$$$ и интервал пересекается, пойдем искать туда, а окажется, что интервалы пересекаются, то левая граница отрезка, за который отвечает вершина, меньше запроса, а именно в ней лежит минимум и мы не найдем ответ
Тогда мы вернёмся и пойдем в правого сына
Кажется я понял в чем дело:
Утверждение: Мы посетим в любом случае не более двух листов.
Доказательство: Пусть мы посетили хотя бы 3 листа, какие они могли быть. Лист выходящий за пределы слева и выходящий за пределы справа и ещё какой-то лист. Если лист с ответом между левой и правой границей, то мы не могли зайти в лист, который за границей справа, потому что попросту обходим слева направо, значит он совпадает с каким-то из прошлых двух, чего быть не может, ибо мы посещаем каждую вершину по одному разу.
Из того, что мы посетим не более двух листов, очевидно, следует, что асимптотика такого решения $$$O(\log{n})$$$, поправьте, если был где-то неправ
А как находить ответ, если наш текущий отрезок вложен в отрезок запроса?
Продолжать спускаться вниз, пока не дойдем до листа с ответом
You could binary search directly on segment tree to achieve $$$log(N)$$$ complexity, using your very same method
I think we can use Cartesian tree to solve it in O(n).
Can't you explain me how exactly? It is interesting enough idea.
You can use sparse table which will give minimum in O(1) and it will be total O(NlogN).
Выглядит как D со вчерашнего глобал раунда.. До на минимум+бинпоиск там вроде норм работали, но я всё равно слил )
Она меня и вдохновила на этот пост, мое решение практически так и выглядит