Given an array of numbers (size n , ( 1<= n <= 1e6 ) ), answer q queries ( 1 <= q <= 1e5 ) of the type: How many numbers in the range [l,r] are within the range [l,r].
Example
If it helps, an additional constraint is that half the array will be -1, and for any value $$$a_i$$$ such that $$$a_i != -1$$$ , $$$a_i > i$$$
I am not sure how to efficiently answer such queries.
This comes from trying to solve this problem :380C - Sereja and Brackets :)
It can be solved offline in $$$O(N log N).$$$ Add the elements from smallest to largest. When you added all numbers $$$a_i \le r$$$ for some query, you can calculate the number of elements from $$$l$$$ to $$$r$$$ which are $$$\le r$$$. Also calculate the number of elements in $$$[l, r]$$$ that are $$$\le l - 1$$$ and subtract it from answer.
Or add the elements from left to right and calculate the sum in "vertical" segments (the number of elements with values from $$$l$$$ to $$$r$$$).
It can be also solved online in $$$O(N log^2 N)$$$ using mergesort tree.