Encuentre la array formada al realizar consultas Q en una array vacía

Considere una secuencia de enteros S , que inicialmente está vacía (es decir, S = {}). También se proporcionan consultas Q , cada una de las cuales es uno de los siguientes tipos:

• 1 ab: inserta a y b en la secuencia S.
• 2 ab: En la secuencia S, entre los elementos que son menores o iguales que a, imprime b-ésimo elemento mayor. Si no existe tal elemento, imprima -1.
• 3 ab: En la secuencia S, entre los elementos que son mayores o iguales que a, imprime b-ésimo elemento más pequeño. Si no existe tal elemento, imprima -1

La tarea es imprimir la secuencia final formada después de realizar todas las consultas Q.

Ejemplos:

Entrada: Q = 7, A = {{1, {20, 10}}, {1, {30, 20}}, {3, {15, 1}}, {3, {15, 2}}, { 3, {15, 3}}, {3, {15, 4}}, {2, {100, 5}} }
Salida: 20, 20, 30, -1, -1
Explicación: Inicialmente secuencia S={} . 
=> Después de la ejecución de las 2 consultas iniciales, se convierte en: {20, 10, 30, 20}.
=> En la secuencia, los elementos mayores que 15 son 20, 20 y 30. En la 3ra consulta, tenemos que imprimir el 1er número más pequeño mayor o igual a 15 que es 20.
=> Del mismo modo, el segundo y el tercer entero más pequeño que son mayores que 15 son 20 y 30 respectivamente. Ahora, la sexta consulta nos pide el cuarto entero más pequeño que es mayor o igual a 15. Pero, solo hay 3 enteros mayores que 15, por lo que imprimimos -1. => La última Consulta nos pide el quinto entero más grande entre los enteros menores o iguales a 100. Pero, solo hay 4 enteros (10, 20, 20, 30), que son menores o iguales a 100. Entonces, imprimir -1.

Entrada: Q = 6, A = {{1, {5, 7}}, {1, {2, 15}}, {1, {11, 16}}, {3, {14, 2}}, { 2, {11, 3}}, {2, {10, 10}} }
Salida: 16, 5, -1

Enfoque: El problema se puede resolver usando búsqueda binaria y multiconjunto .

• Inicialice la secuencia como un conjunto múltiple (digamos s).
• Iterar a través del vector A para procesar las consultas.
• Si la consulta es de tipo 1, inserte tanto a como b en el conjunto múltiple.
• Si la consulta es de tipo 2, calculamos el límite inferior de a en s y, a partir de ese límite inferior, decrementamos b veces para obtener el b -ésimo elemento más grande menor o igual que a .
• Si la consulta es de tipo 3, calculamos el límite superior de a en s y, a partir de ese límite superior, incrementamos b veces para obtener el b -ésimo elemento más pequeño mayor o igual que a .
• En consultas de tipo 2 o 3, si el iterador va más allá de s.begin() o s.end(), imprime la respuesta a esa consulta como -1. De lo contrario, imprima la respuesta obtenida a través de los dos pasos anteriores.

El siguiente es el código basado en el enfoque anterior:

// C++ code for Find the sequence after
// performing Q queries
#include <bits/stdc++.h>
using namespace std;
  
// function to perform the given queries on s
void solveQueries(int Q,
                  vector<pair<int, pair<int, int> > >& A)
{
    // initializing variable to store answer
    // to current query and a multiset of integers
    int ans;
    multiset<int> s;
  
    // iterating through all queries
    for (int i = 0; i < Q; i++) {
        int t, a, b;
        t = A[i].first;
        a = A[i].second.first;
        b = A[i].second.second;
  
        // if query is of 1st type, we simply
        // insert both a and b into our sequence
        if (t == 1) {
            s.insert(a);
            s.insert(b);
            continue;
        }
  
        // If query is of the second type, we
        // calculate the lower bound of a
        // and from that lower bound we decrement
        // b times to get the bth largest element
        // less than or equal to a
        if (t == 2) {
            ans = 0;
            auto it = s.upper_bound(a);
            for (int j = 0; j < b; j++) {
                if (it == s.begin()) {
                    ans = -1;
                    break;
                }
                it--;
                ans = *it;
            }
        }
  
        // If query is of the third type,
        // we calculate the upper bound of a and
        // from that upper bound we increment b times
        // to get the bth smallest element greater
        // than or equal to a
        else {
            ans = 0;
            auto it = s.lower_bound(a);
            for (int j = 0; j < b; j++) {
                if (it == s.end()) {
                    ans = -1;
                    break;
                }
                ans = *it;
                it++;
            }
        }
        // printing the answer
        cout << ans << " ";
    }
}
  
// Driver Code
int main()
{
    int Q = 7;
    vector<pair<int, pair<int, int> > > A
        = { { 1, { 20, 10 } }, { 1, { 30, 20 } }, { 3, { 15, 1 } }, { 3, { 15, 2 } }, { 3, { 15, 3 } }, { 3, { 15, 4 } }, { 2, { 100, 5 } } };
    solveQueries(Q, A);
}

20 20 30 -1 -1 

Complejidad de tiempo: O(Q*log(Q)), donde Q es el número de consultas
Espacio auxiliar: O(Q)