Encuentre el K-ésimo elemento más pequeño en una array para múltiples consultas

Dada una array arr[] de tamaño N y una array Q[][] que consta de M consultas que deben procesarse en la array dada. Se sabe que estas consultas pueden ser de los siguientes dos tipos:

• Tipo 1: si Q = 1, agregue un elemento en la array {tipo, elemento_para_agregar}.
• Tipo 2: Si Q = 2, imprima el K-ésimo elemento más pequeño de la array. {tipo, k}

La tarea es realizar las consultas dadas de tal manera que se den las siguientes restricciones:

• 1 ≤ Número de consultas ≤ 1000000.
• 1 ≤ N ≤ 1000000.
• 1 ≤ arr[i] ≤ 100000000. Y la array puede contener entradas duplicadas.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5, 6}, Q[][] = {{1, 7}, {2, 4}, {1, 5}, {2, 6} }
Salida: 4 5
Explicación:
La primera consulta se usa para agregar 7 en la array. La array arr[] se convierte en: {1, 2, 3, 4, 5, 6, 7}
La segunda consulta es encontrar el ^{4º elemento} más pequeño. Son 4 en este caso.
La tercera consulta se usa para agregar 5 en la array. La array arr[] se convierte en: {1, 2, 3, 4, 5, 5, 6, 7}
La cuarta consulta es encontrar el sexto ^elemento más pequeño. Es 5 en este caso.

Entrada: arr[] = {2, 4, 2, 1, 5, 6, 2, 4}, Q[][] = {{1, 3}, {2, 2}, {1, 10}, { 2, 7}}
Salida: 2 4

Enfoque ingenuo: el enfoque ingenuo para este problema es agregar el elemento en la array y ordenar la array para cada primer tipo de consulta. Y, cada vez que ocurra el segundo tipo de consulta, imprima el elemento K-ésimo en la array ordenada.

Complejidad de tiempo: O(M * (Nlog(N))) donde M es el número de consultas y N es el tamaño de la array.

Enfoque eficiente: la idea es utilizar una estructura de datos basada en políticas . Para este problema, podemos usar la estructura de datos order_of_key para encontrar el K-ésimo elemento más pequeño en la array.

• order_of_key () es una función integrada de Ordered Set, que es una estructura de datos basada en políticas en C++. Las estructuras de datos basadas en políticas no forman parte de la biblioteca estándar de C++, pero el compilador g++ las admite. Esta estructura de datos encuentra el K-ésimo elemento más pequeño en complejidad de tiempo logarítmico.
• Sin embargo, esta estructura de datos no permite claves duplicadas. Para usar la estructura de datos para elementos duplicados, se usa un par .
• Creamos un par del elemento dado y el número de índice para insertarlo en la estructura de datos basada en políticas.
• Los pares se ordenan primero comparando el primer elemento con el segundo. Por ejemplo, (2, 1) se ordena antes que (2, 7).

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

// C++ program to find K-th
// smallest element in an array
// for multiple queries
  
#include <bits/stdc++.h>
using namespace std;
  
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
template <class T>
  
// Defining the policy-based data
// structure
using oset
    = tree<T, null_type,
           less<T>, rb_tree_tag,
           tree_order_statistics_node_update>;
  
// Function to find K-th
// smallest element in an array
// for multiple queries
void Operations(int arr[], int n,
                int query[][2], int k)
{
  
    // Declare the data structure that
    // stores the pairs
    oset<pair<int, int> > s;
  
    int j = 0;
    // Loop to insert the initial array
    // elements into the set
    for (j = 0; j < n; j++) {
        s.insert({ arr[j], j });
    }
  
    // Loop to process the queries
    for (int i = 0; i < k; i++) {
        if (query[i][0] == 1) {
  
            // Inserting the element if the
            // type of query is 1
            s.insert({ query[i][1], j });
            j++;
        }
  
        // Finding the K-th smallest element
        // if the type of the query is 2
        else if (query[i][0] == 2) {
            cout << (*s
                          .find_by_order(
                              query[i][1] - 1))
                        .first
                 << endl;
        }
    }
}
  
// Driver code
int main()
{
    int n = 8;
    int arr[] = { 2, 4, 2, 1, 5, 6, 2, 4 };
  
    int k = 4;
    // Queries. The first element denotes
    // the type of the query
    int query[4][2] = { { 1, 3 },
                        { 2, 2 },
                        { 1, 10 },
                        { 2, 7 } };
  
    Operations(arr, n, query, k);
  
    return 0;
}

2
4

Complejidad de tiempo: O(M * log(N)) , donde M es el número de consultas y N es el tamaño de la array.