Problem with queries

Revision en3, by Doritos4, 2018-07-05 17:56:15

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

Queries : 3 4 7

2 4 5 Output: 4

3 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). 1.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Doritos4 2018-07-05 18:29:14 4 Tiny change: ' O(nlogn). 1. \n' -> ' O(nlogn).\n'
en4 English Doritos4 2018-07-05 17:56:46 8
en3 English Doritos4 2018-07-05 17:56:15 4 Tiny change: '\n3 4 7 \n2 4 5\nOutput:\n4\n3\nI fee' -> '\n3 4 7 \n\n2 4 5\nOutput:\n4\n\n3\nI fee'
en2 English Doritos4 2018-07-05 17:55:47 4 Tiny change: '5, q = 2\n7 4 6 9 \nQueries ' -> '5, q = 2\n\n7 4 6 9 \n\nQueries '
en1 English Doritos4 2018-07-05 17:55:13 769 Initial revision (published)