Answering Queries in sub-linear time

Revision en1, by SriniV, 2023-08-15 06:46:51

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 :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SriniV 2023-08-15 06:46:51 710 Initial revision (published)