RMQ with "Push Update"
Difference between en1 and en2, changed 132 character(s)
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. 

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English zscoder 2016-07-18 14:07:13 132
en1 English zscoder 2016-07-18 11:13:35 626 Initial revision (published)