2725 - Aib

Aveți la dispoziție un număr natural nenul n și o permutare a = (a[1], a[2], ..., a[n]) a mulțimii {1, 2, ..., n}.

Cerința

Pentru fiecare număr a[i] trebuie să determinați câte numere mai mici decât a[i] se află la stânga sa, adică în secvența a[1], a[2], ..., a[i-1].

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale separate prin spații reprezentând permutarea.

Date de ieșire

Programul va afișa pe ecran pentru fiecare i=1..n câte numere mai mici decât a[i] se află la stânga sa.

Restricții și precizări

• 3 ≤ n ≤ 100.000

Exemplu:

Intrare

7
3 1 6 5 2 7 4

Ieșire

0 0 2 2 1 5 3

Explicație

Sunt 0 numere mai mici decât 3 și aflate la stânga lui 3.

Sunt 0 numere mai mici decât 1 și aflate la stânga lui 1

Sunt 2 numere mai mici decât 6 și aflate la stânga lui 6 (acestea sunt primele două numere din șir, adică 3 și 1)

Rezolvare

def count_smaller(arr):
    n = len(arr)
    result = [0] * n
    bit = [0] * (n + 1)

    def update(x, val):
        while x <= n:
            bit[x] += val
            x += x & -x

    def query(x):
        s = 0
        while x > 0:
            s += bit[x]
            x -= x & -x
        return s

    for i in range(n - 1, -1, -1):
        result[i] = query(arr[i])
        update(arr[i], 1)

    return result

def main():
    n = int(input("Introduceti n: "))
    arr = list(map(int, input("Introduceti permutarea: ").split()))

    smaller_counts = count_smaller(arr)
    for count in smaller_counts:
        print(count, end=" ")

if __name__ == "__main__":
    main()