<p>Given an integer array <code>nums</code>, return<em> an integer array </em><code>counts</code><em> where </em><code>counts[i]</code><em> is the number of smaller elements to the right of </em><code>nums[i]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,2,6,1]
<strong>Output:</strong> [2,1,1,0]
<strong>Explanation:</strong>
To the right of 5 there are <b>2</b> smaller elements (2 and 1).
To the right of 2 there is only <b>1</b> smaller element (1).
To the right of 6 there is <b>1</b> smaller element (1).
To the right of 1 there is <b>0</b> smaller element.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1]
<strong>Output:</strong> [0]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [-1,-1]
<strong>Output:</strong> [0,0]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

from sortedcontainers import SortedList
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # binary search
        # Time: O(nlogn)
        # Space: O(n)
        s = SortedList()
        output = []

        for n in nums[::-1]:
            ans = SortedList.bisect_left(s, n)
            output.append(ans)
            s.add(n)
        return reversed(output)
        #bisect_left 是 SortedList 提供的一种二分查找方法，它的作用是找到一个插入点，使得在这个插入点之前的所有元素都小于 n。如果有多个元素等于 n，bisect_left 会返回第一个出现的位置。
        #具体来说，bisect_left(s, n) 返回一个整数值，这个值是 n 应该插入的索引位置，使得 SortedList 中依然保持有序。
        # 假设 s = [1, 2, 5, 6]，并且我们要插入 n = 3：
        # ans = SortedList.bisect_left(s, 3)
        # bisect_left(s, 3) 会返回 2，因为 3 应该插入在 5 之前的位置，以保持列表的有序性。
        # 这个返回值 2 代表 s 中有 2 个元素（1 和 2）比 3 小。
        # n = 1 -> ans = 0, s = [1], output = [0]
        # n = 6 -> ans = 1, s = [1, 6], output = [0, 1]
        # n = 2 -> ans = 1, s = [1, 2, 6], output = [0, 1, 1]
        # n = 5 -> ans = 2, s = [1, 2, 5, 6], output = [0, 1, 1, 2]
1285