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
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
Auto comment: topic has been updated by Sahu_1402 (previous revision, new revision, compare).
Binary search on suffix maximum.
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 ??
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
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
Thanks a lot, mate