1649.-create-sorted-array-through-instructions.md

1649. Create Sorted Array through Instructions

{% tabs %} {% tab title="会用API 就不是hard" %}

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        from sortedcontainers import SortedList
        sl = SortedList()
        ans = 0
        mod = 10**9 + 7
        for n in instructions:
            
            left = sl.bisect_left(n)
            right = len(sl) - sl.bisect_right(n)
            # print(left,right)
            ans += min(left, right)
            sl.add(n)
            
        return ans% mod

{% endtab %}

{% tab title="会理论和不会理论" %}

class Solution:
    def createSortedArray(self, A):
        m = max(A)
        c = [0] * (m + 1)

        def update(x):
            while (x <= m):
                c[x] += 1
                x += x & -x

        def get(x):
            res = 0
            while (x > 0):
                res += c[x]
                x -= x & -x
            return res

        res = 0
        for i, a in enumerate(A):
            res += min(get(a - 1), i - get(a))
            update(a)
        return res % (10**9 + 7)

{% endtab %} {% endtabs %}