### m8.pie's blog

By m8.pie, 10 months ago, ,

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 enabl3d we know solution for this task with $O(n)$ complexity.

Solution

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:

Solution

But thanks to MrDindows and retrograd we have solution with $O(\log{n})$ complexity.

Solution

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.

• +18

 » 10 months ago, # |   +34 You could binary search directly on segment tree to achieve $log(N)$ complexity, using your very same method
 » 10 months ago, # |   +27 I think we can use Cartesian tree to solve it in O(n).
•  » » 10 months ago, # ^ |   +13 Can't you explain me how exactly? It is interesting enough idea.
•  » » 10 months ago, # ^ |   0 Can u please share the implementation .. Thanks in advance..
 » 10 months ago, # |   0 You can use sparse table which will give minimum in O(1) and it will be total O(NlogN).