2725 - Aib
De la Universitas MediaWiki
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()