Problem:
Given an array of n integers and q queries of the form: Q(L, R, x). For each query Q(L, R, x), you have to say "How many integers in the range L to R(inclusive) which are less than x".
There is no update operation.
Constraints:
- 1 ≤ n ≤ 1900000
- 1 ≤ q ≤ 105
If I use Square Root Decomposition, complexity will be O(q * sqrt(n) * logn)
Can you please suggest any better solution for this problem ?
Thanks in advance.