Lista de probleme 11

nrinversiuni

#3206

Se dă șirul a₁, a₂, …, a_n care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j]. Să se determine numărul inversiunilor permutării.

Consola Folclorul informatic medie Clasa 10 Divide et Impera Algoritmi de sortare Inversiunile unei permutari Arbori indexați binar Șmenul lui Batog (Square Root Decomposition)