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)[1] = [8, 24]
Query(Min_i, Max_i)[2] = [8, 12]
Query(Min_i, Max_i)[3] = [6, 18]
Query(Min_i, Max_i)[4] = [10, 14]
Query(Min_i, Max_i)[5] = [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)])