RMQ with "Push Update"

Revision en2, by zscoder, 2016-07-18 14:07:13

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 ≤ x ≤ 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 ≤ 250000 queries.

My current solution uses SQRT decomposition but it was not fast enough to get AC. I was wondering if there is an or 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)