Tri par fusion avec comptage d’inversions

TypeScript Hard sorting

Tâche «Tri par fusion avec comptage d’inversions»

Étant donné un tableau d’entiers. Il faut le trier par ordre croissant à l’aide du tri par fusion, et également compter le nombre d’inversions dans le tableau initial. Une inversion est une paire d’indices (i, j) telle que i < j et a[i] > a[j]. Données d’entrée : la première ligne contient le nombre n (1 ≤ n ≤ 10^5), la deuxième ligne contient n entiers, chacun ne dépassant pas 10^9 en valeur absolue. Données de sortie : la première ligne — le nombre d’inversions, la deuxième ligne — le tableau trié séparé par des espaces.

Format d\ entrée

D’abord un entier n. Ensuite n entiers séparés par des espaces.

Format de sortie

Deux lignes : la première — le nombre d’inversions (un entier), la deuxième — le tableau trié séparé par des espaces.

Exemples

Exemple 1

ENTRÉE

5
3 1 4 2 5

SORTIE

3
1 2 3 4 5

Exemple 2

ENTRÉE

4
4 3 2 1

SORTIE

6
1 2 3 4

Exemple 3

ENTRÉE

123

SORTIE

0

Exemple 4

ENTRÉE

0

SORTIE

0

main.ts