Sahu_1402's blog

A QUERY PROBLEM
By Sahu_1402, history, 4 hours ago, In English

I was going through a problem and got stuck in its sub-problem. In simple terms, the sub-problem is ---

Given an array of size n and q queries.
In each query you will get an element x and you have to return the largest index idx such that arr[idx] >= x or state that such index does not exists. If such an index exists, then update its value to x.

Constraints :
1 <= n,q <= 1e5
1 <= arr[i],x <= 1e9

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

It can be done offline with sweepline. I recently created a blog and practice contest on this.

Online version of a similar problem on Atcoder

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Sahu_1402 (previous revision, new revision, compare).

→ Reply
»
4 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

Binary search on suffix maximum.

→ Reply
  • »
    »
    3 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the answer.
    but, what if we have another type of query which updates the element at given index, then how do we approach this ??

    → Reply
»
4 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

Can't this be solved with a segment tree? for each node we save it's max, let's say max is in the [mid, right] segment, we keep jumping until it's not, else we jump to the left segment until l==r

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Or we can just even use suffix maximum like the guy said, notice that max is strictly increasing from right to left, find the first element such that it's >= x

    → Reply
  • »
    »
    1 minute ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot, mate

    → Reply