Contar pares de inversión en una array

Dada una array A de tamaño NxN , necesitamos encontrar el número de pares de inversión en ella. El conteo de inversión en una array se define como el número de pares que satisfacen las siguientes condiciones:

• X ₁ ≤ X ₂
• y ₁ ≤ y ₂
• A[x ₂ ][y ₂ ] < A[x ₁ ][y ₁ ]

Restricciones:

• 1 ≤ A _{i, j} ≤ 10 ⁹
• 1 ≤ norte ≤ 10 ³

Ejemplos:

For simplicity, let's take a 2x2 matrix :
A = {{7, 5},
     {3, 1}};
The inversion pairs are : (7, 5), (3, 1), (7, 3), (5, 1) and (7, 1)
Output : 5

Para resolver este problema, necesitamos saber lo siguiente:

1. Encontrar el número de pares de inversión en una array 1D utilizando el árbol indexado binario (BIT) https://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit
2. BIT 2D https://www.geeksforgeeks.org/two-dimensional-binary-indexed-tree-or-fenwick-tree

Dado que necesitamos encontrar el número de pares de inversión en una array, lo primero que debemos hacer es almacenar los elementos de la array en otra array, digamos v y ordenar la array v para que podamos comparar los elementos de la array no ordenada con v y encuentre el número de pares de inversión usando BIT. Pero se da que los valores de los elementos son muy grandes (10 ⁹ ), por lo que no podemos utilizar los valores de los elementos de la array como índices en el BIT. Por lo tanto, necesitamos usar la posición de los elementos como índices en el BIT 2D. 

Vamos a usar la tupla (-A[i][j], i, j) para cada elemento de la array y almacenarla en una array, digamos ‘v’. Luego necesitamos ordenar v según el valor de -A[i][j] en orden ascendente, de modo que el elemento más grande de la array se almacene en el índice 0 y el más pequeño en el último índice de v. Ahora, el problema se reduce a encontrar pares de inversión en un arreglo 1D, la única excepción es que vamos a usar un BIT 2D. 

Tenga en cuenta que aquí estamos usando valores negativos de A[i][j], simplemente porque vamos a recorrer v de izquierda a derecha, es decir, desde el número más grande en la array hasta el más pequeño (porque eso es lo que hacemos cuando encontrar pares de inversión en una array 1D usando BIT). También se pueden usar valores positivos y atravesar v de derecha a izquierda, el resultado final seguirá siendo el mismo. 

Algoritmo:

1. Initialize inv_pair_cnt = 0, which will store the number of inversion pairs.
2. Store the tuple (-A[i][j], i, j) in an array, say v, where A[i][j] is the
   element of the matrix A at position (i, j).
3. Sort the array v according to the first element of the tuple, i.e., 
   according to the value of -A[i][j].
4. Traverse the array v and do the following :
       - Initialize an array, say 'pairs' to store the position (i, j)
         of the tuples of v. 
       - while the current tuple of v and all its adjacent tuples whose 
         first value, i.e., -A[i][j] is same, do 
             - Push the current tuple's position pair (i, j) into 'pairs'.
             - Add to inv_pair_cnt,  the number of elements which are less than 
               the current element(i.e., A[i][j]) and lie on the right side 
               in the sorted array v, by calling the query operation of BIT and 
               passing i and j as arguments.
       - For each position pair (i, j) stored in the array 'pairs', 
         update the position (i, j) in the 2D BIT by 1.
5. Finally, inv_pair_cnt will contain the number of inversion pairs.

Implementación:

// C++ program to count the number of inversion
// pairs in a 2D matrix
#include <bits/stdc++.h>
using namespace std;
 
// for simplicity, we are taking N as 4
#define N 4
 
// Function to update a 2D BIT. It updates the
// value of bit[l][r] by adding val to bit[l][r]
void update(int l, int r, int val, int bit[][N + 1])
{
    for (int i = l; i <= N; i += i & -i)
        for (int j = r; j <= N; j += j & -j)
            bit[i][j] += val;
}
 
// function to find cumulative sum upto
// index (l, r) in the 2D BIT
long long query(int l, int r, int bit[][N + 1])
{
    long long ret = 0;
    for (int i = l; i > 0; i -= i & -i)
        for (int j = r; j > 0; j -= j & -j)
            ret += bit[i][j];
 
    return ret;
}
 
// function to count and return the number
// of inversion pairs in the matrix
long long countInversionPairs(int mat[][N])
{
    // the 2D bit array and initialize it with 0.
    int bit[N+1][N+1] = {0};
 
    // v will store the tuple (-mat[i][j], i, j)
    vector<pair<int, pair<int, int> > > v;
 
    // store the tuples in the vector v
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
 
            // Note that we are not using the pair
            // (0, 0) because BIT update and query
            // operations are not done on index 0
            v.push_back(make_pair(-mat[i][j],
                        make_pair(i+1, j+1)));
 
    // sort the vector v according to the
    // first element of the tuple, i.e., -mat[i][j]
    sort(v.begin(), v.end());
 
    // inv_pair_cnt will store the number of
    // inversion pairs
    long long inv_pair_cnt = 0;
 
    // traverse all the tuples of vector v
    int i = 0;
    while (i < v.size())
    {
        int curr = i;
 
        // 'pairs' will store the position of each element,
        // i.e., the pair (i, j) of each tuple of the vector v
        vector<pair<int, int> > pairs;
 
        // consider the current tuple in v and all its
        // adjacent tuples whose first value, i.e., the
        // value of –mat[i][j] is same
        while (curr < v.size() &&
               (v[curr].first == v[i].first))
        {
            // push the position of the current element in 'pairs'
            pairs.push_back(make_pair(v[curr].second.first,
                                      v[curr].second.second));
 
            // add the number of elements which are
            // less than the current element and lie on the right
            // side in the vector v
            inv_pair_cnt += query(v[curr].second.first,
                                  v[curr].second.second, bit);
 
            curr++;
        }
 
        vector<pair<int, int> >::iterator it;
 
        // traverse the 'pairs' vector
        for (it = pairs.begin(); it != pairs.end(); ++it)
        {
            int x = it->first;
            int y = it->second;
 
            // update the position (x, y) by 1
            update(x, y, 1, bit);
        }
 
        i = curr;
    }
 
    return inv_pair_cnt;
}
 
// Driver program
int main()
{
    int mat[N][N] = { { 4, 7, 2, 9 },
                      { 6, 4, 1, 7 },
                      { 5, 3, 8, 1 },
                      { 3, 2, 5, 6 } };
 
    long long inv_pair_cnt = countInversionPairs(mat);
 
    cout << "The number of inversion pairs are : "
         << inv_pair_cnt << endl;
 
    return 0;
}

# Python3 program to count the number of inversion
# pairs in a 2D matrix
 
# for simplicity, we are taking N as 4
N = 4
 
# Function to update a 2D BIT. It updates the
# value of bit[l][r] by adding val to bit[l][r]
def update(l, r, val, bit):
    i = l
    while(i <= N):
        j = r
        while(j <= N):
            bit[i][j] += val
            j += j & -j
        i += i & -i
 
# function to find cumulative sum upto
# index (l, r) in the 2D BIT
def query(l, r, bit):
    ret = 0
    i = l
    while(i > 0):
        j = r
        while(j > 0):
            ret += bit[i][j]
            j -= j & -j
        i -= i & -i
     
    return ret
 
# function to count and return the number
# of inversion pairs in the matrix
def countInversionPairs(mat):
     
    # the 2D bit array and initialize it with 0.
    bit = [[0 for i in range(N + 1)] for j in range(N + 1)]
     
    # v will store the tuple (-mat[i][j], i, j)
    v = []
     
    # store the tuples in the vector v
    for i in range(N):
        for j in range(N):
             
            # Note that we are not using the pair
            # (0, 0) because BIT update and query
            # operations are not done on index 0
            v.append([-mat[i][j], [i + 1, j + 1]])
     
    # sort the vector v according to the
    # first element of the tuple, i.e., -mat[i][j]
    v.sort()
     
    # inv_pair_cnt will store the number of
    # inversion pairs
    inv_pair_cnt = 0
     
    # traverse all the tuples of vector v
    i = 0
    while (i < len(v)):
         
        curr = i
         
        # 'pairs' will store the position of each element,
        # i.e., the pair (i, j) of each tuple of the vector v
        pairs = []
         
        # consider the current tuple in v and all its
        # adjacent tuples whose first value, i.e., the
        # value of –mat[i][j] is same
        while (curr < len(v) and (v[curr][0] == v[i][0])):
             
            # push the position of the current element in 'pairs'
            pairs.append([v[curr][1][0], v[curr][1][1]])
             
            # add the number of elements which are
            # less than the current element and lie on the right
            # side in the vector v
            inv_pair_cnt += query(v[curr][1][0], v[curr][1][1], bit)
            curr += 1
             
        # traverse the 'pairs' vector
        for it in pairs:
            x = it[0]
            y = it[1]
             
            # update the position (x, y) by 1
            update(x, y, 1, bit)
             
        i = curr
     
    return inv_pair_cnt
 
# Driver code
mat = [[4, 7, 2, 9 ],[ 6, 4, 1, 7 ],
        [ 5, 3, 8, 1 ],[3, 2, 5, 6]]
 
inv_pair_cnt = countInversionPairs(mat)
 
print("The number of inversion pairs are :", inv_pair_cnt)
 
# This code is contributed by shubhamsingh10

The number of inversion pairs are : 43

Complejidad de tiempo : O(log(NxN)), donde N es el tamaño de la array 
Complejidad de espacio : O(NxN) 

Este artículo es una contribución de Avinash Kumar Saw . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.