Contar inversiones usando conjunto ordenado y GNU C++ PBDS

Dada una array arr[] de N enteros. La tarea es encontrar el número de inversión. Dos elementos arr[i] y arr[j] forman una inversión si arr[i] > arr[j] e i < j . 

Ejemplos 

Entrada: arr[] = {8, 4, 2, 1} 
Salida: 6 
Explicación: 
la array dada tiene seis inversiones:  

• (8, 4): arr[0] > arr[1] y 0 < 1
• (8, 2): arr[0] > arr[2] y 0 < 2
• (8, 1): arr[0] > arr[3] y 0 < 3
• (4, 2): arr[1] > arr[2] y 1 < 2
• (4, 1): arr[1] > arr[3] y 1 < 3
• (2, 1): arr[2] > arr[3] y 2 < 3

Entrada: arr[] = {2, 3} 
Salida: 0 
Explicación: 
No existe tal par tal que arr[i] > arr[j] e i < j.
 

Ya hemos discutido los siguientes enfoques:  

• Contar inversiones en una array | Conjunto 1 (usando la ordenación por combinación)
• Contar inversiones en una array | Conjunto 2 (usando BST de autoequilibrio)
• Contando inversiones usando Set en C++ STL
• Contar inversiones en una array | Conjunto 3 (usando BIT)

En esta publicación, analizaremos un enfoque que utiliza Conjunto ordenado y GNU C++ PBDS.

Enfoque: 
Usaremos la función order_of_key(K) que devuelve un número de elementos estrictamente menor que K en log N time.  

1. Inserte el primer elemento de la array en Ordered_Set.
2. Para todos los elementos restantes en arr[] , haga lo siguiente: 
   • Inserta el elemento actual en el Ordered_Set.
   • Encuentre el número de elementos estrictamente menor que el elemento actual + 1 en Ordered_Set usando la función order_of_key(arr[i]+1) .
   • La diferencia entre el tamaño de Ordered_Set y order_of_key(current_element + 1) dará el recuento de inversión para el elemento actual.

Por ejemplo:

arr[] = {8, 4, 2, 1}
Ordered_Set S = {8}
For remaining element in arr[]:
At index 1, the element is  4
S = {4, 8}
key = order_of_key(5) = 1
The difference between size of S and key gives the total 
number of inversion count for that current element.
inversion_count = S.size() - key =  2 - 1 = 1
Inversion Pairs are: (8, 4)

At index 2, the element is  2
S = {2, 4, 8}
key = order_of_key(3) = 1
inversion_count = S.size() - key =  3 - 1 = 2
Inversion Pairs are: (8, 2) and (4, 2)

At index 3, the element is 1
S = {1, 2, 4, 8}
key = order_of_key(2) = 1
inversion_count = S.size() - key =  4 - 1 = 3
Inversion Pairs are: (8, 1), (4, 1) and (2, 1)

Total inversion count = 1 + 2 + 3 = 6

A continuación se muestra la implementación del enfoque anterior: 

// Ordered set in GNU C++ based
// approach for inversion count
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
 
// Ordered Set Tree
typedef tree<int, null_type, less_equal<int>,
             rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
 
// Returns inversion count in
// arr[0..n-1]
int getInvCount(int arr[], int n)
{
    int key;
    // Initialise the ordered_set
    ordered_set set1;
 
    // Insert the first
    // element in set
    set1.insert(arr[0]);
 
    // Initialise inversion
    // count to zero
    int invcount = 0;
 
    // Finding the inversion
    // count for current element
    for (int i = 1; i < n; i++) {
        set1.insert(arr[i]);
 
        // Number of elements strictly
        // less than arr[i]+1
        key = set1.order_of_key(arr[i] + 1);
 
        // Difference between set size
        // and key will give the
        // inversion count
        invcount += set1.size() - key;
    }
    return invcount;
}
 
// Driver's Code
int main()
{
    int arr[] = { 8, 4, 2, 1 };
    int n = sizeof(arr) / sizeof(int);
 
    // Function call to count
    // inversion
    cout << getInvCount(arr, n);
    return 0;
}

6

Complejidad de tiempo: O (Nlog N)