Sahu_1402's blog

A QUERY PROBLEM
By Sahu_1402, history, 2 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
  • +2
  • Vote: I do not like it

»
2 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
»
2 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
»
2 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

Binary search on suffix maximum.

→ Reply
»
117 minutes ago, # |
  Vote: I like it +1 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
  • »
    »
    114 minutes ago, # ^ |
      Vote: I like it +1 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