Más operaciones sobre conjuntos ordenados

Recursos

C++Java

Recursos
Fuente	Recurso	Notas
IUSACO	4.4 - Sets & Maps	este módulo se basa en esto
CP2	2.2.2 - Non-Linear Data Structures	ver la descripción de BSTs y heaps

Recursos
Fuente	Recurso	Notas
IUSACO	4.3 - Sets & Maps	este módulo se basa en esto
CP2	2.2.2 - Non-Linear Data Structures	ver la descripción de BSTs y heaps

Video de YouTube (HOPDUbcAmQM)

En conjuntos y mapas donde las claves (o elementos) se almacenan en orden ordenado, se soporta acceder o eliminar la siguiente clave mayor o menor que alguna clave de entrada k.

Hay que tener en cuenta que la inserción y el borrado tomarán tiempo $\mathcal{O}(\log N)$ para conjuntos ordenados, que es más que la inserción y el borrado promedio $\mathcal{O}(1)$ de los conjuntos hash, pero menos que la inserción y el borrado de peor caso $\mathcal{O}(N)$ de los conjuntos hash.

Usando iteradores

En Bronce evitamos discutir cualquier operación de conjuntos que involucre iteradores.

C++JavaPython

Recursos
Fuente	Recurso	Notas
CPH	4.4 - Set Iterators

En Java, los iteradores son útiles para recorrer conjuntos.

Los iteradores usados con HashSet devolverían los elementos en orden aleatorio:


Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(3);
set.add(0);
set.add(-2);
Iterator it = set.iterator();
while (it.hasNext()) {
	Integer i = (Integer)it.next();
	System.out.print(i + " ");  // returns some random order
}

Pero con TreeSet los elementos están en orden ordenado:


Set<Integer> set = new TreeSet<Integer>();
set.add(1);
set.add(3);
set.add(0);
set.add(-2);
Iterator it = set.iterator();
while (it.hasNext()) {
	Integer i = (Integer)it.next();
	System.out.print(i + " ");  // returns -2 0 1 3
}

En lugar de crear un iterador y recorrerlo como en C++, Java proporciona un bucle for-each que crea un iterador oculto y recorre con él automáticamente:


Set<Integer> set = new TreeSet<Integer>();
set.add(1);
set.add(3);
set.add(0);
set.add(-2);
for (int i : set) {
	System.out.print(i + " ");  // returns -2 0 1 3
}

En Python, podemos usar iter() para obtener el objeto iterador de cualquier iterable. Usar next() sobre el iterador permite recorrer el iterable. Abajo se usa un diccionario en lugar de un conjunto porque los diccionarios conservan el orden.

Recorrer una representación en diccionario de un conjunto ordenado (por inserción):


nums = {0: None, 1: None, 2: None, 4: None, 7: None}
iterator = iter(nums)
 
print(next(iterator))  # 0
print(next(iterator))  # 1
print(next(iterator))  # 2
print(next(iterator))  # 4
print(next(iterator))  # 7

Los iteradores de Python son fundamentales para la iteración y se usan en sus bucles for y en el desempaquetado de tuplas. Esto es útil cuando se quiere más control sobre la iteración. También se puede usar simplemente en casos en los que solo se quiere el primer elemento o cualquier elemento.

Conjuntos ordenados

C++JavaPython

El std::set ordenado también soporta:

lower_bound: devuelve un iterador al menor elemento mayor o igual que algún elemento k.
upper_bound: devuelve un iterador al menor elemento estrictamente mayor que algún elemento k.


set<int> s;
s.insert(1);                        // [1]
s.insert(14);                       // [1, 14]
s.insert(9);                        // [1, 9, 14]
s.insert(2);                        // [1, 2, 9, 14]
cout << *s.upper_bound(7) << '\n';  // 9
cout << *s.upper_bound(9) << '\n';  // 14
cout << *s.lower_bound(5) << '\n';  // 9
cout << *s.lower_bound(9) << '\n';  // 9
cout << *s.begin() << '\n';         // 1
auto it = s.end();
cout << *(--it) << '\n';    // 14
s.erase(s.upper_bound(6));  // [1, 2, 14]

Los TreeSet en Java permiten una multitud de operaciones adicionales:

first(): devuelve el menor elemento del conjunto
last(): devuelve el mayor elemento del conjunto
lower(E v): devuelve el mayor elemento estrictamente menor que v
floor(E v): devuelve el mayor elemento menor o igual que v
higher(E v): devuelve el menor elemento estrictamente mayor que v
ceiling(E v): devuelve el menor elemento mayor o igual que v


TreeSet<Integer> set = new TreeSet<Integer>();
set.add(1);                          // [1]
set.add(14);                         // [1, 14]
set.add(9);                          // [1, 9, 14]
set.add(2);                          // [1, 2, 9, 14]
System.out.println(set.higher(7));   // 9
System.out.println(set.higher(9));   // 14
System.out.println(set.lower(5));    // 2
System.out.println(set.first());     // 1
System.out.println(set.last());      // 14
set.remove(set.higher(6));           // [1, 2, 14]
System.out.println(set.higher(23));  // ERROR, no such element exists

Python no tiene un conjunto ordenado ni un mapa ordenado, así que ver C++ o Java si se quiere una implementación de la librería estándar. Sin embargo, si aún se tiene curiosidad por la implementación en Python, se puede encontrar abajo una representación de un conjunto ordenado con un árbol AVL.

Recursos
Fuente	Recurso	Notas
DSA Python	AVL Trees	definición e implementación de árboles AVL en Python

Como algunos jueces online incluyen librerías adicionales, abajo se muestra una implementación de conjuntos ordenados de la librería sortedcontainers (que no está incluida en la mayoría de los jueces online como USACO). Todas las operaciones de abajo son tiempo $\mathcal{O}(\log N)$ , excepto su inicialización $\mathcal{O}(N \log N)$ .


from sortedcontainers import SortedSet
 
sorted_set = SortedSet([5, 1, 3, 2])
print(sorted_set)  # SortedSet([1, 2, 3, 4, 7])
 
# Add elements
sorted_set.add(4)
sorted_set.add(6)
print(sorted_set)  # SortedSet([1, 2, 3, 4, 5, 6])
 
# Remove elements
sorted_set.discard(3)
sorted_set.discard(5)
print(sorted_set)  # SortedSet([1, 2, 4, 6])
 
# Check if an element is in the sorted set
print(2 in sorted_set)  # True
print(100 in sorted_set)  # False
 
# Access elements by it's index
print(sorted_set[0])  # 1 (smallest element, first index)
print(sorted_set[-1])  # 6 (largest element, last index)
print(sorted_set[2])  # 4
 
# Get the index of an element
print(sorted_set.index(4))  # 2
 
# Find the index to insert the given value
print(sorted_set.bisect_left(2))  # 1
print(sorted_set.bisect_right(2))  # 2

Una limitación de los conjuntos ordenados es que no podemos acceder de forma eficiente al $k$ -ésimo elemento más grande del conjunto, ni hallar el número de elementos del conjunto mayores que algún $x$ arbitrario. En C++, estas operaciones se pueden manejar usando una estructura de datos llamada árbol de estadísticas de orden.

Mapas ordenados

C++JavaPython

El map ordenado también permite:

lower_bound: devuelve el iterador que apunta a la entrada más baja no menor que la clave especificada
upper_bound: devuelve el iterador que apunta a la entrada más baja estrictamente mayor que la clave especificada.


map<int, int> m;
m[3] = 5;     // [(3, 5)]
m[11] = 4;    // [(3, 5); (11, 4)]
m[10] = 491;  // [(3, 5); (10, 491); (11, 4)]
cout << m.lower_bound(10)->first << " " << m.lower_bound(10)->second << '\n';  // 10 491
cout << m.upper_bound(10)->first << " " << m.upper_bound(10)->second << '\n';  // 11 4
m.erase(11);  // [(3, 5); (10, 491)]
if (m.upper_bound(10) == m.end()) {
	cout << "end" << endl;  // Prints end
}

El mapa ordenado además soporta firstKey / firstEntry y lastKey / lastEntry, que devuelven la clave/entrada más baja y la clave/entrada más alta, así como higherKey / higherEntry y lowerKey / lowerEntry, que devuelven la clave/entrada más baja estrictamente mayor que la clave especificada, o la clave/entrada más alta estrictamente menor que la clave especificada.


TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
map.put(3, 5);                           // [(3, 5)]
map.put(11, 4);                          // [(3, 5); (11, 4)]
map.put(10, 491);                        // [(3, 5); (10, 491); (11, 4)]
System.out.println(map.firstKey());      // 3
System.out.println(map.firstEntry());    // (3, 5)
System.out.println(map.lastEntry());     // (11, 4)
System.out.println(map.higherEntry(4));  // (10, 491)
map.remove(11);                          // [(3, 5); (10, 491)]
System.out.println(map.lowerKey(4));     // 3
System.out.println(map.lowerKey(3));     // ERROR

Los mapas ordenados en Python se pueden crear añadiendo un diccionario a un conjunto ordenado, donde cada elemento del conjunto ordenado es una clave en el diccionario y los valores se pueden asignar con el diccionario. Esta es la implementación más directa, y la implementación desde cero de un conjunto ordenado se puede encontrar en la sección de arriba.

Además, se puede implementar un SortedDict con la librería sortedcontainers. Todas las operaciones de abajo son tiempo $\mathcal{O}(\log N)$ , excepto una inicialización $\mathcal{O}(N \log N)$ y tiempo $\mathcal{O}(N)$ para obtener todos los items, claves o valores.


from sortedcontainers import SortedDict
 
sorted_map = SortedDict({1: "one", 4: "four", 3: "three"})
print(sorted_map)  # SortedDict({1: 'one', 3: 'three', 4: 'four'})
 
# Add elements
sorted_map[2] = "two"
sorted_map[5] = "five"
 
# Output SortedDict({1: 'one', 2: 'two', 3: 'three', 4: 'four', 5: 'five'})
print(sorted_map)
 
# Remove elements
del sorted_map[3]
print(sorted_map)  # SortedDict({1: 'one', 2: 'two', 4: 'four', 5: 'five'})
 
# Check if a key is in the sorted dict
print(1 in sorted_map)  # True
print(100 in sorted_map)  # False
 
# Get the key's value
print(sorted_map[2])  # two
print(sorted_map[4])  # four
 
# Get all items (key value pairs), keys, or values below
print(*sorted_map.items())  # (1, 'one') (2, 'two') (4, 'four') (5, 'five')
print(*sorted_map.keys())  # 1 2 4 5
print(*sorted_map.values())  # one two four five
 
# Find the index of an existing key
print(sorted_map.index(2))  # 1
 
# Find the index to insert a given key
print(sorted_map.bisect_left(3))  # 2
print(sorted_map.bisect_right(6))  # 4

Multiconjuntos

Un multiconjunto (multiset) es un conjunto ordenado que permite varias copias del mismo elemento.

PythonC++Java

Aunque no hay multiconjuntos en Python, podemos implementar uno usando la estructura de datos collections.Counter que mapea valores a sus respectivas frecuencias. Todos los valores empiezan con un conteo de 0, y funciona de forma similar a un diccionario.


from collections import Counter
 
ms = Counter()
ms[1] += 1  # {1: 1}
ms[14] += 1  # {1: 1, 14: 1}
ms[9] += 1  # {1: 1, 14: 1, 9: 1}
ms[2] += 1  # {1: 1, 14: 1, 9: 1, 2: 1}
ms[9] += 1  # {1: 1, 14: 1, 9: 2, 2: 1}
ms[9] += 1  # {1: 1, 14: 1, 9: 3, 2: 1}
 
print(ms[4])  # 0
print(ms[9])  # 3
print(ms[14])  # 1
ms[9] -= 1  # remove an occurence of 9
print(ms[9])  # 2
del ms[9]  # remove all occurences of 9
print(ms[9])  # 0

Además de todas las operaciones regulares de conjuntos,

el método count() devuelve el número de veces que un elemento está presente en el multiconjunto. Sin embargo, este método toma tiempo lineal en el número de coincidencias, así que no se debería usar en un contest.
Para eliminar un valor una vez, usar ms.erase(ms.find(val)).
Para eliminar todas las ocurrencias de un valor, usar ms.erase(val).


multiset<int> ms;
ms.insert(1);                  // [1]
ms.insert(14);                 // [1, 14]
ms.insert(9);                  // [1, 9, 14]
ms.insert(2);                  // [1, 2, 9, 14]
ms.insert(9);                  // [1, 2, 9, 9, 14]
ms.insert(9);                  // [1, 2, 9, 9, 9, 14]
cout << ms.count(4) << '\n';   // 0
cout << ms.count(9) << '\n';   // 3
cout << ms.count(14) << '\n';  // 1
ms.erase(ms.find(9));
cout << ms.count(9) << '\n';  // 2
ms.erase(9);
cout << ms.count(9) << '\n';  // 0

Aunque no hay multiconjunto en Java, podemos implementar uno usando el TreeMap de valores a sus respectivas frecuencias. Declaramos la implementación del TreeMap de forma global para poder escribir funciones para añadir y eliminar elementos. Las operaciones first, last, higher y lower siguen funcionando como se espera; basta usar firstKey, lastKey, higherKey y lowerKey respectivamente.


static TreeMap<Integer, Integer> multiset = new TreeMap<Integer, Integer>();
 
public static void main(String[] args) { ... }
 
static void add(int x) {
	if (multiset.containsKey(x)) {
		multiset.put(x, multiset.get(x) + 1);
	} else {
		multiset.put(x, 1);
	}
}
 
static void remove(int x) {
	multiset.put(x, multiset.get(x) - 1);
	if (multiset.get(x) == 0) { multiset.remove(x); }
}

Problemas introductorios

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Concert Tickets	Fácil	Sorted Set	Solución
YS	Double-Ended Priority Queue	Fácil	Sorted Set	Solución
CSES	★ Traffic Lights	Fácil	Sorted Set	Solución
CSES	★ Towers	Fácil	Sorted Set, Greedy, LIS, Binary Search	Solución

Ejemplo más difícil - Bit Inversions

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CSES	Bit Inversions	Difícil	Sorted Set	Solución

Solución

Usaremos iteradores de forma extensiva.

Sea el string de bits $s=s_0s_1s_2\ldots,s_{n-1}$ . En el conjunto dif, guardamos todos los índices $i$ tales que $s_i\neq s_{i-1}$ (incluyendo $i=0$ e $i=n$ ). Si los elementos de dif son $0=dif_1<dif_2<\cdots<dif_k=n$ , entonces la longitud más larga es igual a

\max(dif_2-dif_1,dif_3-dif_2,\ldots,dif_k-dif_{k-1}).

Podemos guardar cada una de estas diferencias en un multiconjunto ret; después de cada inversión, habrá que imprimir el elemento máximo de ret.

Invertir un bit en una posición x indexada desde cero corresponde a insertar x en dif si no está presente actualmente o eliminar x si lo está, y luego hacer lo mismo con x+1. Cada vez que insertamos o eliminamos un elemento de dif, debemos actualizar ret en consecuencia.

C++Java


#include <bits/stdc++.h>
using namespace std;
 
#define sz(x) (x).size()
 
string s;
int m;
set<int> dif;
multiset<int> ret;
 
void modify(int x) {
	if (x == 0 || x == sz(s)) return;
	auto it = dif.find(x);
	if (it != end(dif)) {  // x is currently present in dif, remove it
		int a = *prev(it), b = *next(it);
		ret.erase(ret.find(x - a)), ret.erase(ret.find(b - x));  // update ret
		ret.insert(b - a);
		dif.erase(it);             // remove x from dif
	} else {                       // x is not currently in dif, insert it
		it = dif.insert(x).first;  // insert x into dif
		// it = iterator corresponding to x
		int a = *prev(it), b = *next(it);
		ret.erase(ret.find(b - a));  // update ret
		ret.insert(x - a), ret.insert(b - x);
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s >> m;
	dif.insert(0);
	dif.insert(sz(s));
	for (int i = 0; i < sz(s) - 1; ++i)
		if (s[i] != s[i + 1]) dif.insert(i + 1);  // initialize dif
	for (auto it = dif.begin(); next(it) != dif.end(); it++) {
		ret.insert(*next(it) - *it);  // initialize ret
	}
	for (int i = 0; i < m; ++i) {
		int x;
		cin >> x;  // 1-indexed position
		modify(x - 1);
		modify(x);
		cout << *ret.rbegin() << " ";
	}
}


 
import java.io.*;
import java.util.*;
 
class BitInversion {
	public static TreeMap<Integer, Integer> ret = new TreeMap<Integer, Integer>();
	public static String s;
	public static int m;
	public static Set<Integer> dif = new TreeSet<Integer>();
 
	public static void modify(int x) {
		if (x == 0 || x == s.length()) return;
		if (dif.contains(x)) {  // x is currently present in dif, remove it
			int a = dif.lower(x), b = dif.higher(x);
			remove(x - a);
			remove(b - x);  // update ret
			add(b - a);
			dif.remove(x);  // remove x from dif
		} else {
			dif.add(x);  // insert x into dif
			int a = dif.lower(x), b = dif.higher(x);
			remove(b - a);  // update ret
			add(x - a);
			add(b - x);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		s = sc.readLine();
		m = Integer.parseInt(sc.readLine());
		dif.add(0);
		dif.add(s.length());
		for (int i = 0; i < s.length() - 1; i++) {
			if (s.charAt(i) != s.charAt(i + 1)) dif.add(i + 1);  // initialize dif
		}
		for (int it : dif) {
			if (dif.higher(it) != null) add(dif.higher(it) - it);  // initialize ret
		}
		StringTokenizer st = new StringTokenizer(sc.readLine());
		for (int i = 0; i < m; i++) {
			int x = Integer.parseInt(st.nextToken());  // 1-indexed position
			modify(x - 1);
			modify(x);
			out.println(ret.lastKey());
		}
		out.close();
	}
 
	static void add(int x) {
		if (ret.containsKey(x)) {
			ret.put(x, ret.get(x) + 1);
		} else {
			ret.put(x, 1);
		}
	}
 
	static void remove(int x) {
		ret.put(x, ret.get(x) - 1);
		if (ret.get(x) == 0) { ret.remove(x); }
	}
}

Nótese que el multiconjunto tiene un factor constante alto, así que reemplazar ret por una cola de prioridad y un arreglo que guarda el número de veces que cada entero aparece en la cola de prioridad reduce el tiempo de ejecución por un factor de 2.

C++Java


#include <bits/stdc++.h>
using namespace std;
 
#define sz(x) (int)(x).size()
 
string s;
int m;
set<int> dif;
priority_queue<int> ret;
int cnt[200005];
 
void ad(int x) {
	cnt[x]++;
	ret.push(x);
}
void modify(int x) {
	if (x == 0 || x == sz(s)) return;
	auto it = dif.find(x);
	if (it != end(dif)) {
		int a = *prev(it), b = *next(it);
		dif.erase(it);
		cnt[x - a]--, cnt[b - x]--;
		ad(b - a);
	} else {
		it = dif.insert(x).first;
		int a = *prev(it), b = *next(it);
		cnt[b - a]--, ad(x - a), ad(b - x);
	}
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> s >> m;
	dif.insert(0);
	dif.insert(sz(s));
	for (int i = 0; i < sz(s) - 1; ++i) {
		if (s[i] != s[i + 1]) dif.insert(i + 1);
	}
	for (auto it = dif.begin(); next(it) != dif.end(); it++) { ad(*next(it) - *it); }
	for (int i = 0; i < m; ++i) {
		int x;
		cin >> x;
		modify(x - 1);
		modify(x);
		while (!cnt[ret.top()]) ret.pop();
		// pop elements that should no longer be present in priority queue
		cout << ret.top() << " ";
	}
}


 
import java.io.*;
import java.util.*;
 
class BitInversion {
	public static PriorityQueue<Integer> pq =
	    new PriorityQueue<Integer>(Collections.reverseOrder());
	public static String s;
	public static int m;
	public static TreeSet<Integer> dif = new TreeSet<Integer>();
	public static int cnt[];
	public static void add(int x) {
		cnt[x]++;
		pq.add(x);
	}
	public static void modify(int x) {
		if (x == 0 || x == s.length()) return;
		if (dif.contains(x)) {  // x is currently present in dif, remove it
			int a = dif.lower(x), b = dif.higher(x);
			cnt[x - a]--;
			cnt[b - x]--;  // update ret
			add(b - a);
			dif.remove(x);  // remove x from dif
		} else {
			dif.add(x);  // insert x into dif
			int a = dif.lower(x), b = dif.higher(x);
			cnt[b - a]--;  // update ret
			add(x - a);
			add(b - x);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		s = sc.readLine();
		m = Integer.parseInt(sc.readLine());
		cnt = new int[s.length() + 1];
		dif.add(0);
		dif.add(s.length());
		for (int i = 0; i < s.length() - 1; i++) {
			if (s.charAt(i) != s.charAt(i + 1)) dif.add(i + 1);  // initialize dif
		}
		for (int it : dif) {
			if (dif.higher(it) != null) { add(dif.higher(it) - it); }
		}
		StringTokenizer st = new StringTokenizer(sc.readLine());
		for (int i = 0; i < m; i++) {
			int x = Integer.parseInt(st.nextToken());  // 1-indexed position
			modify(x - 1);
			modify(x);
			while (cnt[pq.peek()] == 0) pq.poll();
			// pop elements that should no longer be present in priority queue
			out.println(pq.peek());
		}
		out.close();
	}
}

Problemas más difíciles

Fuente	Nombre	Dificultad	Tags	Solución
Silver	Milk Measurement	Normal	Sorted Set, Priority Queue	Solución
CF	Array Destruction	Normal	Multiset, Sorting, Greedy	Solución
CSES	★ Movie Festival II	Normal	Sorting, Sorted Set, Greedy	Solución
Gold	★ Snow Boots	Normal	Linked List, Sorted Set	Solución
CF	Buying Gifts	Difícil	Greedy, Sorting, Sorted Set	—
CF	Tournament	Difícil	Sorted Set	—
Gold	Photo Op	Difícil	Sorted Set	—
Gold	Apple Catching	Difícil	Sorting, Greedy, Sorted Set	Solución