Requisito previo : conocimiento básico de STL y estructura de conjuntos de datos .
Sobre el conjunto ordenado
El conjunto ordenado es una estructura de datos basada en políticas en g ++ que mantiene los elementos únicos en orden. Realiza todas las operaciones realizadas por la estructura de datos establecida en STL en complejidad log(n) y realiza dos operaciones adicionales también en complejidad log(n).
- order_of_key (k) : Número de elementos estrictamente menores que k .
- find_by_order(k) : K-ésimo elemento en un conjunto (contando desde cero).
Archivos de encabezado necesarios para implementar el conjunto ordenado y su descripción
Para implementar order_set y la biblioteca GNU C++ contiene otras estructuras de datos basadas en políticas que debemos incluir:
- // El archivo común
incluye <ext/pb_ds/assoc_container.hpp> - // Incluyendo tree_order_statistics_node_update
include <ext/pb_ds/tree_policy.hpp>
El primero se usa para incluir los contenedores asociativos o grupos de plantillas como conjunto, mapa múltiple, mapa, etc. Las estructuras de datos basadas en árboles que usaremos a continuación están presentes en este archivo de encabezado.
El segundo archivo de encabezado se usa para incluir la actualización de tree_order_statistics_node que se explica a continuación:
using namespace __gnu_pbds;
Es un espacio de nombres necesario para las estructuras de datos basadas en políticas basadas en GNU .
El contenedor basado en árbol tiene una estructura concreta, pero la estructura necesaria requerida para la implementación del conjunto ordenado es:
tree < int , null_type , less , rb_tree_tag , tree_order_statistics_node_update >
- int : Es el tipo de dato que queremos insertar (KEY). Puede ser entero, float o par de int etc.
- null_type : Es la política mapeada. Aquí es nulo usarlo como un conjunto. Si queremos obtener el mapa pero no el conjunto, como segundo tipo de argumento se debe usar el tipo mapeado.
- menos : Es la base para la comparación de dos funciones.
- rb_tree_tag : tipo de árbol utilizado. Por lo general, son árboles rojos y negros porque se necesita tiempo de registro (n) para la inserción y eliminación, mientras que otros toman tiempo lineal, como splay_tree.
- tree_order_statistics_node__update : se incluye en tree_policy.hpp y contiene varias operaciones para actualizar las variantes de Node de un contenedor basado en árbol, por lo que podemos realizar un seguimiento de metadatos como la cantidad de Nodes en un subárbol
Funciones adicionales en el conjunto ordenado que no sean el conjunto
Junto con las operaciones anteriores del conjunto, admite dos operaciones importantes principales
- find_by_order(k): It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time.To find the first element k must be zero.
Let us assume we have a set s : {1, 5, 6, 17, 88}, then :
*(s.find_by_order(2)) : 3rd element in the set i.e. 6
*(s.find_by_order(4)) : 5th element in the set i.e. 88 - order_of_key(k) : Vuelve a la cantidad de elementos que son estrictamente más pequeños que nuestro elemento k en el tiempo O(logn).
Supongamos que tenemos un conjunto s: {1, 5, 6, 17, 88}, entonces:
s.order_of_key(6): el recuento de elementos estrictamente menor que 6 es 2.
s.order_of_key(25): recuento de elementos estrictamente menor que 25 es 4.
Diferencia entre el conjunto y el conjunto ordenado
No hay tanta diferencia entre el conjunto y el conjunto ordenado, aunque se puede asumir que el conjunto ordenado es una versión extendida del conjunto capaz de realizar algunas funciones más avanzadas (indicadas anteriormente) que se usan ampliamente en la programación competitiva.
NOTA
:
conjunto_pedido
se utiliza aquí como una macro dada a
tree<int, null_type, less, rb_tree_tag, tree_order_statistics_node_update>.
Por lo tanto, se le puede dar cualquier nombre como
macro
que no sea conjunto_ordenado, pero generalmente en el mundo de la programación competitiva se le conoce comúnmente como conjunto ordenado, ya que es un conjunto con operaciones adicionales.
Aplicaciones prácticas:
supongamos que tenemos una situación en la que los elementos se insertan uno por uno en una array y después de cada inserción, se nos da un rango [l, r] y tenemos que determinar el número de elementos en la array mayor que igual a l y menos que igual a r. Inicialmente, la array está vacía.
Ejemplos:
Input : 5
1 2
1
2 5
2
1 5
Output : 0
1
3
Explicación:
- Inicialmente, la array está vacía.
- 5 se inserta.
- El conteo de elementos mayor que igual a 1 y menor que igual a 2 es 0.
- 1 se inserta.
- La cuenta de elementos mayores que iguales a 2 y menores que iguales a 5 es 1, es decir, 5.
- 2 se inserta.
- La cuenta de elementos mayores que iguales a 1 y menores que iguales a 5 es 3, es decir, 5, 1, 2.
Input : 1
1 2
2
3 5
5
1 4
Output : 1
0
2
- 1 se inserta.
- El recuento de elementos mayores que iguales a 1 y menores que iguales a 2 es 1, es decir, 1.
- 2 se inserta.
- El conteo de elementos mayor que igual a 3 y menor que igual a 5 es 0.
- 5 se inserta.
- El recuento de elementos mayores que iguales a 1 y menores que iguales a 4 es 2, es decir, 1, 2.
Inicialmente, la array está vacía.
Si usamos set en STL find upper_bound on set, solo proporciona la dirección del elemento y solo podemos encontrar el valor en esa dirección usando el operador de desreferenciación (*).
Supongamos que si tenemos un conjunto como {0, 1, 2, 7, 8, 20} y encontramos el límite superior de 2, entonces devuelve una dirección correspondiente a la posición del elemento (7 en este caso) en el conjunto y nosotros NO SE PUEDE restar la dirección inicial del conjunto (s.begin()) para encontrar el número de elementos menores que 2 como en el caso del vector.
Entonces, aquí viene la necesidad del conjunto ordenado.
NOTA : Las funciones anteriores se pueden implementar con la ayuda de alguna otra lógica y estructura de datos, pero el uso de un conjunto ordenado hace que el código sea compacto y se pueda implementar con facilidad y rapidez.
Implementación del conjunto ordenado
// C++ program to demonstrate the// ordered set in GNU C++#include <iostream>using namespace std; // Header files, namespaces,// macros as defined above#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> // Driver program to test above functionsint main(){ // Ordered set declared with name o_set ordered_set o_set; // insert function to insert in // ordered set same as SET STL o_set.insert(5); o_set.insert(1); o_set.insert(2); // Finding the second smallest element // in the set using * because // find_by_order returns an iterator cout << *(o_set.find_by_order(1)) << endl; // Finding the number of elements // strictly less than k=4 cout << o_set.order_of_key(4) << endl; // Finding the count of elements less // than or equal to 4 i.e. strictly less // than 5 if integers are present cout << o_set.order_of_key(5) << endl; // Deleting 2 from the set if it exists if (o_set.find(2) != o_set.end()) o_set.erase(o_set.find(2)); // Now after deleting 2 from the set // Finding the second smallest element in the set cout << *(o_set.find_by_order(1)) << endl; // Finding the number of // elements strictly less than k=4 cout << o_set.order_of_key(4) << endl; return 0;} |
Producción
2 2 2 5 1
Por lo tanto, ahora podemos resolver fácilmente el problema anterior, es decir, el recuento de elementos entre l y r se puede encontrar mediante:
o_set.order_of_key(r+1) – o_set.order_of_key(l)
NOTA : Como el conjunto contiene solo los elementos ÚNICOS , para realizar las operaciones en una array que tiene elementos repetidos, podemos tomar la CLAVE como un par de elementos en lugar de un número entero en el que el primer elemento es nuestro elemento requerido de la array y solo el segundo elemento del par debe ser único para que todo el par sea único.
Para obtener más detalles, consulte:
https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html