I’ve though about this for a couple hours but I’m unable to make much headway. It goes like this :
You have an array of size n and q queries. Each query is of the form (l, r, k). The answer to each query is the index (1-based) of the leftmost number in the range [l, r] which is greater than or equal to k. If there is no such value, return -1. Constraints: n, q <= 1e5, l <= r and the elements can be from 0 to 1e9. The program should run within a second.
Example input :
n = 5, q = 2
7 4 6 9
3 4 7
2 4 5
I feel like a maximum segment tree might work here, but I am unable to put it together. Please help. Obviously, a O(n^2) solution would not run in time. I think the intended solution is O(nlogn).