Given an integer n and array a, I need to find for each i, 1≤ i ≤ n, how many elements on the left are less than or equal to a_i

Example:

    5 
    1 2 1 1 2

Output

    0 1 1 2 4

I can do it in O(N²) but I want to ask if there is any way to do it faster, since N is very large (N ≤ 10⁶)?

CodePudding user response：

You can use a segment tree, you just need to use a modified version called a range tree. Range trees allow rectangle queries, so you can make the dimensions be index and value, and ask "What has value more than x, and index between 1 and n?" Queries can be accomplished in O(log n) assuming certain common optimizations.

Either way O(N^2) is completely fine with N < 10^6.