Problem statement

https://binarysearch.com/problems/Inverted-Inversions/

Solution

Let us fix index b. Then we need to find two values:

  1. Number of elements to the left, which are smaller than nums[b]. For this we can use sorted list to which we add element by element.
  2. Number of inverstions to the right, for this we can again use sorted list, starting from the end. Each time we add new element, we calculate cumulative sum.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        suff = [0]
        suff_set = SortedList([])
        for num in nums[::-1]:
            suff += [suff[-1] + suff_set.bisect(num)]
            suff_set.add(num)

        suff = suff[1:][::-1]

        pref_set = SortedList([])
        pref = [0]
        for i in range(len(nums) - 1):
            pref_set.add(nums[i])
            pref += [pref_set.bisect(nums[i+1])]

        return sum(x*y for x, y in zip(pref, suff[1:])) % (10**9 + 7)

Remark

If sorted list is not allowed, we can use Segment Tree or Binary Indexed Tree with the same complexity.