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.
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