Given N marbles which are numbered between 1..10000. The numbers may contain duplicates and not ordered.
You have to sort the marbles numbers in non decreasing order.
For each Q queries, you have to determine the position of the specified marbles in the sorted marble numbers.
count[X] be the number of occurrence of marble X
Using the information on array count, we can create another array (it's basically a counting sort):
marble[position], the marble number which resides in position position of the sorted marbles
Since we want the inverse of the marble[position], we just loop 1..10000 to make an inverse array:
position[marble], the position of the marble in the sorted marbles
The complexity of having the array marble[position] and position[marble] is O(2*10000).
After having the array position[marble] we can answer all the queries easily in O(1).
--Felix halim 23:46, 29 Nov 2005 (EST)