Recently I encountered a problem which is very similar to RMQ. ↵
↵
Abridged Statement : First, you have an empty array. You have two operations :↵
↵
1. Insert a value $v$ between positions $x - 1$ and $x$ $(1 \le x \le k + 1)$ where $k$ is the current size of the array.(positions are 1-indexed)↵
↵
2. Find the maximum in the range [l, r] (i.e. the maximum from the positions $l$ to $r$ inclusive)↵
↵
There are at most $Q \le 250000$ queries.↵
↵
My current solution uses SQRT decomposition but it was not fast enough to get AC. I was wondering if there is an $O(Q\log Q)$ or $O(Q\log^{2}Q)$ solution.↵
↵
Edit : Forgot to mention that the queries must be answered online (it's actually function call), so offline solutions doesn't work.
↵
Abridged Statement : First, you have an empty array. You have two operations :↵
↵
1. Insert a value $v$ between positions $x - 1$ and $x$ $(1 \le x \le k + 1)$ where $k$ is the current size of the array.(positions are 1-indexed)↵
↵
2. Find the maximum in the range [l, r] (i.e. the maximum from the positions $l$ to $r$ inclusive)↵
↵
There are at most $Q \le 250000$ queries.↵
↵
My current solution uses SQRT decomposition but it was not fast enough to get AC. I was wondering if there is an $O(Q\log Q)$ or $O(Q\log^{2}Q)$ solution.↵
↵
Edit : Forgot to mention that the queries must be answered online (it's actually function call), so offline solutions doesn't work.
