Problem statement

https://binarysearch.com/problems/Delete-Integers-In-Ascending-Order/

Solution

Similar to Leetcode 0315. Count of Smaller Numbers After Self, keep BIT of activated elements.

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, nums):
        P = [(x, i) for i, x in enumerate(nums)]

        n = len(nums)
        bit, ans = BIT(n), []
        for _, i in sorted(P):
            c = bit.query(i + 1)
            ans += [i - c]
            bit.update(i + 1, 1)

        return ans