 Range Count

Hi,

I would like to know if there is a good approach to solve the following problem

I am given an input array A[1...n]
and n queries of range [Min_i, Max_i]
(It is also guarantee that (Min_i+Max_i)/2=A[i])
I am supposed to calculate
for every query Q_i, find the count C_i of numbers of A[1...(i-1)]
that is in the range of [Min_i, Max_i]
I only need to output the sum of all C_i

For example

Array[1-5]={ 16 10 12 12 6 }
Query(Min_i, Max_i) = [8, 24]
Query(Min_i, Max_i) = [8, 12]
Query(Min_i, Max_i) = [6, 18]
Query(Min_i, Max_i) = [10, 14]
Query(Min_i, Max_i) = [0, 12]
(guarantee that every (Min_i+Max_i)/2=A[i])

count C_1 = the count of numbers in A[1...0] in range [8, 24], which is 0 (none)
count C_2 = the count of numbers in A[1...1] in range [8, 12], which is 0
count C_3 = the count of numbers in A[1...2] in range [6, 18], which is 2
count C_4 = the count of numbers in A[1...3] in range [10, 14], which is 2
count C_5 = the count of numbers in A[1...4] in range [0, 12], which is 3

So the output should be 7 (2+2+3)

I would like to know if there is a good data structure or algorithm to approach this problem

Thanks!

Edit 1
From a higher perspective,
The problem could be generalize as
Given Array A[1...n]
for every given numbers A[i] find the count of numbers before itself (A[1...(i-1)] ) that is in a specific range [Min_i, Max_i]

Or you could see it this way
Given n queries [Min_i, Max_i]
Find how many elements in A[1...(i-1)] (only to i-1 not n-1)
that is >= Min_i and <= Max_i

another example
Given array A = { 9 5 8 3 7 }
query 1 [6, 12]  => find count in {} that is in range [6, 12] => 0
query 2 [4, 6]   => find count  in {9} that is in range [4, 6] => 0
query 3 [7, 9]  => find count  in {9 5} that is in range [7, 9] => 1
query 4 [-2, 8]  => find count in {9 5 8} that is in range [-2, 8] =>2
query 5 [5, 9]  => find count in {9 5 8 3} that is in range [5, 9] => 3

So the answer should be 6   (0+0+1+2+3)

Note
I found this is similar to SPOJ KQUERY problem
https://www.spoj.com/problems/KQUERY/

the differences are
1. in KQUERY problem we need to find numbers larger than K
in this problem we need to find numbers between Min_i and Max_i
2. in KQUERY problem the range (i, j) is random
in this problem for each query Q_i we need to find in range (1, (i-1))   (A[1...(i-1)])
1 Like

Can you post the question link?

1 Like

Its not in English,
but I think its my fault not to let others know the problems easily
I’ll try to format and add examples right away
Thanks for your help

I’ve added a few more examples and tried not to format the problem ambiguous