Cuente elementos más pequeños en el lado derecho usando Set en C++ STL

Escribe una función para contar el número de elementos más pequeños a la derecha de cada elemento en una array. Dada una array no ordenada arr[] de enteros distintos, construya otra array countSmaller[] tal que countSmaller[i] contenga el recuento de elementos más pequeños en el lado derecho del elemento arr[i] en la array. 
Ejemplos: 
 

Input : arr[] =  {12, 1, 2, 3, 0, 11, 4}
Output :countSmaller[]  =  {6, 1, 1, 1, 0, 1, 0} 

Input :arr[]={5, 4, 3, 2, 1}
Output :countSmaller[]={4, 3, 2, 1, 0}

En esta publicación se analiza una implementación sencilla de https://www.geeksforgeeks.org/count-smaller-elements-on-right-side/ . Cree un conjunto
vacío en C++ STL (tenga en cuenta que el conjunto en C++ STL se implementa mediante el árbol de búsqueda binario autoequilibrado). 
 

1. Recorra el elemento de la array de i=len-1 a 0 e inserte cada elemento en un conjunto.
2. Encuentra el primer elemento que es más bajo que A[i] usando la función lower_bound.
3. Encuentre la distancia entre el elemento encontrado arriba y el comienzo del conjunto usando la función de distancia.
4. Almacene la distancia en otra array, digamos CountSmaller[].
5. Imprime esa array.

// CPP program to find count of smaller
// elements on right side using set in C++
// STL.
#include <bits/stdc++.h>
using namespace std;
void countSmallerRight(int A[], int len)
{
    set<int> s;
    int countSmaller[len];
    for (int i = len - 1; i >= 0; i--) {
        s.insert(A[i]);
        auto it = s.lower_bound(A[i]);
        countSmaller[i] = distance(s.begin(), it);
    }
 
    for (int i = 0; i < len; i++)
        cout << countSmaller[i] << " ";
}
 
// Driver code
int main()
{
    int A[] = {12, 1, 2, 3, 0, 11, 4};
    int len = sizeof(A) / sizeof(int);
    countSmallerRight(A, len);
    return 0;
}

6 1 1 1 0 1 0 

Tenga en cuenta que la implementación anterior toma la complejidad de tiempo en el peor de los casos O (n ^ 2) ya que la complejidad de tiempo de la función de distancia en el peor de los casos es O (n), pero la implementación anterior es muy simple y funciona mejor que el algoritmo ingenuo en el caso promedio.
El enfoque anterior funciona para elementos únicos, pero para elementos duplicados simplemente reemplace Set con Multiset .

Enfoque eficiente: Uso de estructuras de datos basadas en políticas en C++ STL.

Mantenga una estructura de datos basada en políticas de pares solo para resolver problemas duplicados.

• Recorreremos la array desde el final y cada vez que encontremos order_of_key del elemento actual para encontrar el número de elementos más pequeños a la derecha de él.
• Luego, insertaremos el elemento actual en nuestra estructura de datos basada en políticas.  

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds                                               \
    tree<pair<int, int>, null_type, less<pair<int, int> >, \
         rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
 
// Function to find number of smaller elements
// to the right of every element
void countSmallerRight(int arr[], int n)
{
    pbds s;
    // stores the answer
    vector<int> ans;
    for (int i = n - 1; i >= 0; i--) {
        if (i == n - 1) { // for the last element answer is
                          // zero
            ans.push_back(0);
        }
        else { // insert number of the smaller elements
            // to the right of current element into the ans
            ans.push_back(s.order_of_key({ arr[i], i }));
        }
        // insert current element
        s.insert({ arr[i], i });
    }
 
    reverse(ans.begin(), ans.end());
    for (auto x : ans)
        cout << x << " ";
}
 
// Driver Code
int main()
{
    int n = 7;
    int arr[] = { 12, 1, 2, 3, 0, 11, 4 };
    countSmallerRight(arr, n);
    return 0;
}

6 1 1 1 0 1 0 

Complejidad de tiempo: O(N*LogN)