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

<syntaxhighlight lang="python3"> 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()

</syntaxhighlight>