L'objectif est de compter le nombre d'inversions dans une séquence d'entiers. Une inversion est une paire d'indices (i, j) telle que i < j et arr[i] > arr[j]. Nous allons explorer deux approches principales, toutes deux offrant une complexité temporelle de O(log n) après prétraitement.

Approche par Division et Fusion (Merge Sort)

Cette méthode est considérée comme "offline" car elle nécessite l'intégralité des données avant de commencer et modifie le tableau d'origine. Son avantage est qu'elle n'est pas limitée par la plage des valeurs des éléments.

Le principe repose sur la modification de l'algorithme de tri fusion. Lors de la fusion de deux sous-tableaux triés, nous comptons les inversions. Si nous fusionnons le sous-tableau gauche [l, m] avec le sous-tableau droit [m+1, r], et que nous prenons un élément arr[i] du sous-tableau gauche, alors tous les éléments arr[j] restants dans le sous-tableau droit (où j > m) et qui sont plus petits que arr[i] forment des inversions avec arr[i].

Voici une implémentation conceptuelle :

#include <vector>

// Tableau d'assistance pour la fusion
int temp_storage[500005];

long long count_inversions_merge(std::vector<int>& arr, int left, int mid, int right) {
    long long inversions = 0;
    
    // Compter les inversions pendant la fusion
    for (int i = mid, j = right; i >= left; --i) {
        while (j > mid && arr[i] <= arr[j]) {
            j--;
        }
        inversions += (j - mid);
    }

    // Fusionner les deux sous-tableaux
    int i = left, p1 = left, p2 = mid + 1;
    while (p1 <= mid && p2 <= right) {
        temp_storage[i++] = (arr[p1] < arr[p2]) ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) {
        temp_storage[i++] = arr[p1++];
    }
    while (p2 <= right) {
        temp_storage[i++] = arr[p2++];
    }

    // Copier les éléments triés dans le tableau d'origine
    for (int k = left; k <= right; ++k) {
        arr[k] = temp_storage[k];
    }
    return inversions;
}

long long solve_inversions_recursive(std::vector<int>& arr, int left, int right) {
    if (left >= right) {
        return 0;
    }
    int mid_point = left + (right - left) / 2;
    long long total_inversions = 0;
    total_inversions += solve_inversions_recursive(arr, left, mid_point);
    total_inversions += solve_inversions_recursive(arr, mid_point + 1, right);
    total_inversions += count_inversions_merge(arr, left, mid_point, right);
    return total_inversions;
}

Approche par Arbre de Fenwick (Fenwick Tree / BIT)

Cette méthode est dite "online" car elle permet d'obtenir le compte d'inversions en temps réel à mesure que les éléments sont traités. Elle ne modifie pas le tableau d'origine et est plus efficace en termes de complexité spatiale pour certains problèmes. Cependant, elle est sensible à la plage des valeurs des données.

L'idée est de parcourir le tableau de droite à gauche. Pour chaque élément arr[i], nous voulons savoir combien d'éléments à sa droite sont plus petits que lui. Si nous parcourons de droite à gauche, pour un élément arr[i], nous devons compter les éléments arr[j] avec j > i tels que arr[j] < arr[i].

Un arbre de Fenwick est idéal ici. Il permet d'effectuer deux opérations efficaces :

1. Mise à jour ponctuelle : Incrémenter la fréquence d'une valeur.
2. Requête de somme préfixée : Calculer la somme des fréquences jusqu'à une certaine valeur.

Lorsque nous traitons arr[i] (en parcourant de droite à gauche), nous interrogeons l'arbre de Fenwick pour obtenir la somme des fréquences des nombres strictement inférieurs à arr[i]. Cette somme correspond au nombre d'inversions où arr[i] est le plus grand élément. Ensuite, nous mettons à jour l'arbre de Fenwick en ajoutant arr[i] pour les éléments suivants.

Gestion de la plage des valeurs : Discrétisation

Les valeurs dans le tableau peuvent être très grandes (jusqu'à 10^9), ce qui rend impossible l'utilisation directe d'un arbre de Fenwick dont la taille dépendrait de cette plage. La solution est la discrétisation. Nous n'avons besoin que des relations d'ordre entre les nombres, pas de leurs valeurs absolues.

Le processus de discrétisation se déroule comme suit :

1. Créer une copie du tableau original.
2. Trier cette copie par ordre croissant.
3. Supprimer les doublons pour obtenir une liste unique des valeurs distincets.
4. Remplacer chaque élément du tableau original par son rang (son indice dans la liste triée et unique des valeurs). L'objectif est de mapper les valeurs originales à des entiers plus petits, idéalement dans la plage [1, N], où N est la taille du tableau.

Voici le code pour la discrétisation et l'utilisation de l'arbre de Fenwick :

#include <vector>
#include <algorithm>
#include <iostream>

const int MAX_N = 5e5 + 7;
int original_values[MAX_N];
int mapped_values[MAX_N]; // Pour stocker les valeurs après discrétisation
int fenwick_tree[MAX_N];
int distinct_values_count;

// Fonction pour discrétiser les valeurs
void discretize(int n) {
    // Copier les valeurs originales pour ne pas modifier le tableau d'entrée avant la fin
    std::vector<int> temp_arr(n + 1);
    for (int i = 1; i <= n; ++i) {
        temp_arr[i] = original_values[i];
    }

    // Trier pour trouver les valeurs uniques
    std::sort(temp_arr.begin() + 1, temp_arr.begin() + n + 1);

    // Obtenir la liste des valeurs uniques et leur nombre
    distinct_values_count = 1;
    for (int i = 2; i <= n; ++i) {
        if (temp_arr[distinct_values_count] != temp_arr[i]) {
            temp_arr[++distinct_values_count] = temp_arr[i];
        }
    }

    // Mappper les valeurs originales à leurs rangs discrets
    for (int i = 1; i <= n; ++i) {
        // Utilise std::lower_bound pour trouver le rang. Le résultat est un pointeur,
        // on soustrait l'adresse de début du tableau trié pour obtenir l'indice (rang).
        mapped_values[i] = std::lower_bound(temp_arr.begin() + 1, temp_arr.begin() + distinct_values_count + 1, original_values[i]) - temp_arr.begin();
    }
}

// Ajoute une valeur v à l'indice i dans l'arbre de Fenwick
void update_fenwick(int index, int value, int max_index) {
    while (index <= max_index) {
        fenwick_tree[index] += value;
        index += index & (-index); // Déplacement vers le parent suivant
    }
}

// Calcule la somme des valeurs de l'indice 1 à i dans l'arbre de Fenwick
long long query_fenwick(int index) {
    long long sum = 0;
    while (index > 0) {
        sum += fenwick_tree[index];
        index -= index & (-index); // Déplacement vers le parent précédent
    }
    return sum;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    // Lire les valeurs originales et les stocker également dans mapped_values pour la discrétisation
    for (int i = 1; i <= n; ++i) {
        std::cin >> original_values[i];
        mapped_values[i] = original_values[i]; // Copie initiale pour la discrétisation
    }

    // Appliquer la discrétisation
    discretize(n);

    long long inversion_count = 0;
    // Parcourir le tableau des valeurs discrétisées de droite à gauche
    for (int i = n; i > 0; --i) {
        int current_rank = mapped_values[i];
        // Compter les éléments déjà vus (à droite) qui sont plus petits que l'élément courant
        inversion_count += query_fenwick(current_rank - 1);
        // Ajouter l'élément courant à l'arbre de Fenwick
        update_fenwick(current_rank, 1, n); // Le max_index est n car les rangs vont jusqu'à n
    }

    std::cout << inversion_count << "\n";

    return 0;
}