Hello guys,
The problem consists of a vector with size N (0 < N <1e6), a position i is chosen to determine how many elements are greater than the element v [i] in the interval [1, i -1]. In the problem there will be 1e6 queries. I would like to know how to solve this kind of problem with complexity close to O (log n) per query.
Sample:
1 7 4 5 6 7 8
Choosing the element in the 5th position (value 6) in the range [1, 5 — 1] there are 2 elements greater than 6.
Tks. :D
Sort the queries in ascending order. Then iterate i from 1 to N, and keep adding elements to BIT . While going from i to i+1, you can successfully answer the query for position i using BIT.
You can solve all querys in one scan, compress the vector and use a BIT to know how many elements less or equal than v[i] is on the left, now the anwser is (i — how many elements less on the left) , you can keep all the querys in a vector and anwser in O(1) , total complexity : O(nlog(n)). Here's the code
I think, perhaps, this can be solved by using the Segment Tree technique...(I am not sure)
For the given array a[n], we calculate the required number of elements from left to right one by one. At first, we deal with a[1] (I think the implementation of segment tree might be more simple if we count from 1 rather than 0). Thus, we should calculate the sum of the segment tree with range [a[1]+1, N], and the answer is just the number of elements that are exactly larger than a[1]. Next, we put a[1] "into" the segment tree, and move on to deal with a[2]. For a[2], we also calculate the sum of the segment tree with range [a[2]+1, N], and the result is the required answer for a[2]. The above steps are repeated until the last element a[N] has been visited.
As the calculation of sum in segment tree is O(logN), the total complexity should be O(NlogN) as far as I consider. Sometimes, the range of the values in a[N] might be quite large compared with the total number of elements. For this case, we should first "remap" the original values into a feasible range (for most of the time, I think the range is just [1, N]).
I think perhaps you can check problem 61E - Enemy is weak, which is a very nice problem to practice Segment Tree technique. :D
Other than the solution with the segment tree/BIT, you can also add the elements to an order statistics tree, in order left to right. After adding each element check it's index. If you use this to implement it, it will be much shorter than even a BIT(a bit slower but that usually doesn't matter as time complexity is the same).
I believe we can do this by implementing a merge sort tree where each node is a vector storing elements in a particular range. In each query we can take an upper bound of the number to calculate values bigger than that number.
You can do this for online queries (what is the rank of my number in a range?), if it is needed for another problem.
Create a segment tree and in each node have a BBST. To find the position of a value in a range just query all the BBSTs covered. This is O(log^2 N) per query. However, you need to create a custom BBST as the standard set does not support rank.
Be cool, solve it offline with merge sort :)