Imagine the situation when we want to find such $$$a_j$$$ for any $$$a_i$$$ which will satisfy this:
$$$a_i > a_j$$$ $$$i < j$$$Thanks to shufl999dka we know solution for this task with $$$O(n)$$$ complexity.
SolutionLet's use stack. For every element from right to left we will erase elements which are not lower than our current and find the answer when the process stops or understand that is no answer. After that we add current and continue. Every element is added and erased once so it is $$$O(n)$$$ complexity.
Imagine now the situation, when we want to find such $$$a_j$$$ for any $$$x$$$ and $$$[l; r)$$$, which will satisfy this:
$$$a_j < x$$$ $$$l \leq j < r$$$ $$$j\;is\;less\;possible$$$First solution I developed was $$$O(n\log^2{n})$$$ complexity and had such algorithm:
SolutionLet's build simple Segments Tree with minimums. Now we can recursively do this:
- Base: if we are in the leaf and value is lower than $$$x$$$, then return the value, else return $$$-1$$$ or $$$INF$$$ or etc.
- Let
m = (l + r) / 2
- Is minimum on $$$[l; m)$$$ is lower than $$$x$$$?
- If not, then is minimum on $$$[m; r)$$$ is lower than $$$x$$$?
- If not $$$2$$$ and not $$$3$$$ then answer does not exist, else let's call it recursively.
We take $$$O(\log{n})$$$ steps because of dividing array by two every step and on every step we make two requests to minimum segment tree, so we have $$$O(n\log^2{n})$$$ solution for both tasks.
But thanks to MrDindows and bicsi we have solution with $$$O(\log{n})$$$ complexity.
SolutionLet's understand that we do not need any recursive function except finding minimum in segments tree. Let's watch on every step if our left son has minimum lower than our $$$x$$$ and intersects our search segment than let's call this function recursively from it, else or if answer was not found (for example when minimum is not in intersection) let's call this function with our second child.
This will take $$$O(\log{n})$$$ complexity because of the fact, that we visit no more than two leafs, the very left and if we did not found the answer — the second leaf — the leaf with the answer.
It is possible to see this algorithms working on concrete task: 1237D - Balanced Playlist
Solution $$$O(n\log^2{n})$$$ complexity is 732 ms — 62741630
Solution $$$O(n\log{n})$$$ complexity is 77 ms — 62881402
If you have more efficient solution for any of these two tasks then write here in comments.
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).