Problem statement

https://binarysearch.com/problems/Ticket-Order/

Solution

The idea is to use BIT here. Let us start from the smallest values and keep in our BIT activated bits, that is numbers we already delete from our queue. Then on each step we can recalculate how many steps we need to take. Imagine, that we have values 1, 4, 2, 4, 8, 5, 2 and we now processing the second 4. How many steps we need to take? We need to take several full loops (ignoring empty elements): in this case 3 loops. And also we need to take one part of loop to reach element 4, for this we use our bit. Also in fact we have loops with empty elements and we need to undertand how many times we skip them. We can show that number of skips will be j * (val - 1) - ps, where ps is cumulative sum of all previous values.

Complexity

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

Code

class BIT:
    def __init__(self, n):
        self.sums = [0] * (n+1)
    
    def update(self, i, delta):
        while i < len(self.sums):
            self.sums[i] += delta
            i += i & (-i)
    
    def query(self, i):
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= i & (-i)
        return res

class Solution:
    def solve(self, T):
        n = len(T)
        bit = BIT(n)
        data = sorted((t, i) for i, t in enumerate(T))
        ans, ps = [0] * n, 0

        for j, (val, i) in enumerate(data):
            ans[i] = ps + (n - j) * (val - 1) + (i + 1 - bit.query(i))
            bit.update(i + 1, 1)
            ps += val

        return ans

Remark

There is also O(n log n) time complexity solution, using SortedList.