Comparadores personalizados y compresión de coordenadas

Recursos

Recursos
Fuente	Recurso	Notas
IUSACO	8 - Sorting & Comparators	parcialmente basado en esto
CPH	3.2 - User-Defined Structs, Comparison Functions	panorama breve

Video de YouTube (FHLot4pa-D4)

Introducción

El ordenamiento no se aplica solo a números. Por ejemplo, muchas soluciones de Wormhole Sort involucran primero ordenar la lista de aristas por su peso.

Por ejemplo, el caso de ejemplo nos da las siguientes aristas:

Después de ordenar, debería verse así

A continuación describimos varias formas de hacerlo.

C++JavaPython

Estructuras de datos de la librería

Pares

El método más directo es usar un pair<int, pair<int, int>>. Al compararlos, C++ mira el primer elemento y solo usa el segundo como desempate.


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	constexpr int edge_num = 4;
 
	vector<pair<int, pair<int, int>>> edges(edge_num);
	for (auto &[width, edge] : edges) { cin >> edge.first >> edge.second >> width; }
	sort(edges.begin(), edges.end());
 
	for (const auto &[width, edge] : edges) {
		printf("(%i, %i): %i\n", edge.first, edge.second, width);
	}
}

Arreglos

Una alternativa es usar std::array o std::vector:


#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	constexpr int edge_num = 4;
 
	vector<array<int, 3>> edges;
	// vector<vector<int>> edges;  // also works, but is slower
	for (int e = 0; e < edge_num; e++) {
		int a, b;
		int width;
		cin >> a >> b >> width;
		edges.push_back({width, a, b});
	}
	sort(edges.begin(), edges.end());
 
	for (const auto &e : edges) { printf("(%i, %i): %i\n", e[1], e[2], e[0]); }
}

Lamentablemente, Java no tiene mucho soporte de librería para ordenar colecciones de varios elementos; en su mayoría nos limita a ordenar arreglos de enteros crudos y similares.

Para implementar el ordenamiento por valores personalizados en Java, necesitamos usar comparadores, que se cubren más abajo.

Hay varias formas de hacer esto. En Python, podemos usar una lista de listas:


edge_num = 4
 
edges = []
for _ in range(edge_num):
	a, b, width = [int(i) for i in input().split()]
	edges.append((width, a, b))
edges.sort()
 
for e in edges:
	print(f"({e[1]}, {e[2]}): {e[0]}")

Otra opción sería un Tuple[int, Tuple[int]], pero eso haría la indexación más enredada.

Comparadores

La mayoría de las funciones de ordenamiento se basan en mover objetos con un valor más bajo delante de objetos con un valor más alto si se ordena de forma ascendente, y viceversa si es descendente. Esto se hace comparando dos objetos a la vez.

C++JavaPython

En C++, sus comparadores deben obedecer un conjunto de comportamientos. Llamemos a este comparador compare, y a los objetos que compara x e y.

Si x es menor que y, devolver true.
Si x es mayor que o igual a y, devolver false.
Si compare(x, y) es true, entonces compare(y, x) debe ser falso. (antisimetría)
Si compare(x, y) es true y compare(y, z) es true, entonces compare(x, z) debe ser verdadero. (transitividad)

En esencia, el comparador determina si $x$ pertenece a la izquierda de $y$ en un ordenamiento.

Sobrecarga de `operator<`

Esta es la más fácil de implementar. Sin embargo, solo funciona para objetos (no primitivos) y no permite definir varias formas de comparar el mismo tipo de clase.

Ordenemos esas cuatro aristas otra vez con este nuevo método:


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
struct Edge {
	int a, b;
	int width;
 
	// see https://stackoverflow.com/a/11805395/12128483 for why we use const Edge&
	bool operator<(const Edge &y) { return width < y.width; }
};
 
int main() {
	constexpr int edge_num = 4;
 
	vector<Edge> edges(edge_num);
	for (Edge &e : edges) { cin >> e.a >> e.b >> e.width; }
	sort(edges.begin(), edges.end());
 
	for (const Edge &e : edges) { printf("(%i, %i): %i\n", e.a, e.b, e.width); }
}

También es posible definir operator< fuera de la clase:


struct Edge {
	int a, b;
	int width;
};
 
bool operator<(const Edge &x, const Edge &y) { return x.width < y.width; }

Función de comparación

También podemos pasar el comparador como una lambda directamente a std::sort. Esto tiene la ventaja de funcionar tanto con primitivos como con clases.


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
struct Edge {
	int a, b;
	int width;
};
 
int main() {
	constexpr int edge_num = 4;
 
	vector<Edge> edges(edge_num);
	for (Edge &e : edges) { cin >> e.a >> e.b >> e.width; }
	sort(edges.begin(), edges.end(),
	     [](const Edge &x, const Edge &y) { return x.width < y.width; });
 
	for (const Edge &e : edges) { printf("(%i, %i): %i\n", e.a, e.b, e.width); }
}

En Java, sus comparadores deben obedecer un conjunto de comportamientos. Llamemos a este comparador compare, y a los objetos que compara x e y. Para que compare sea válido, debe cumplirse lo siguiente:

Si x es menor que y, devolver -1.
Si x es mayor que y, devolver 1.
Si los dos son iguales, devolver 0.
Si compare(x, y) > 0, entonces compare(y, x) < 0. (antisimetría)
Si compare(x, y) > 0 y compare(y, z) > 0, entonces compare(x, z) > 0. (transitividad)

En esencia, el comparador determina si $x$ pertenece a la izquierda de $y$ en un ordenamiento.

Java tiene algunos comparables de librería como Integer.compare y Arrays.compare, pero a menudo tenemos que definir los nuestros.

Implementar `Comparable<T>`

Para que una clase T sea ordenable, tenemos que hacer que extienda Comparable<T>. Después de eso, también hay que implementar el método compareTo que toma una instancia de otra clase y devuelve un número según las reglas descritas arriba.

Al usar Comparable, podemos llamar a Arrays.sort(arr) o Collections.sort(list) sobre el arreglo o la lista como de costumbre.


import java.io.*;
import java.util.*;
 
class Edge implements Comparable<Edge> {
	public int a, b;
	public int width;
 
	public Edge(int a, int b, int width) {
		this.a = a;
		this.b = b;
		this.width = width;
	}
 
	@Override
	public int compareTo(Edge e) {
		return width - e.width;
	}
}
 
public class SortingDemo {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
 
		final int edgeNum = 4;
		Edge[] edges = new Edge[edgeNum];
		for (int e = 0; e < edgeNum; e++) {
			edges[e] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(edges);
 
		for (Edge e : edges) { System.out.printf("(%d, %d): %d\n", e.a, e.b, e.width); }
 
		sc.close();
	}
}

Función comparadora

También podemos pasar una función comparadora directamente a Arrays.sort (o Collections.sort, si estamos ordenando un ArrayList).


import java.io.*;
import java.util.*;
 
class Edge {
	public int a, b;
	public int width;
 
	public Edge(int a, int b, int width) {
		this.a = a;
		this.b = b;
		this.width = width;
	}
}
 
public class SortingDemo {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		final int edgeNum = 4;
		Edge[] edges = new Edge[edgeNum];
		for (int e = 0; e < edgeNum; e++) {
			edges[e] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(edges, (x, y) -> x.width - y.width);
 
		for (Edge e : edges) { System.out.printf("(%d, %d): %d\n", e.a, e.b, e.width); }
 
		sc.close();
	}
}

Función key

Las funciones de ordenamiento de Python toman un argumento key que recibe un objeto y devuelve un tipo comparable como un int.


class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width
 
 
edge_num = 4
edges = [Edge(*[int(i) for i in input().split()]) for _ in range(edge_num)]
edges.sort(key=lambda e: e.width)
 
for e in edges:
	print(f"({e.a}, {e.b}): {e.width}")

Comparador

Una forma menos idiomática pero igualmente soportada de ordenar objetos en Python es con comparadores que devuelven el orden relativo de dos objetos.

Llamemos a este comparador compare, y a los objetos que compara x e y. Para que compare sea válido, debe cumplirse lo siguiente:

Si x es menor que y, devolver -1.
Si x es mayor que y, devolver 1.
Si los dos son iguales, devolver 0.
Si compare(x, y) > 0, entonces compare(y, x) < 0. (antisimetría)
Si compare(x, y) > 0 y compare(y, z) > 0, entonces compare(x, z) > 0. (transitividad)

Las funciones de ordenamiento de Python no toman comparadores de forma directa. Hay que convertirlos a algo que key pueda tomar con functools.cmp_to_key así:


from functools import cmp_to_key
 
 
class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width
 
 
edge_num = 4
edges = [Edge(*[int(i) for i in input().split()]) for _ in range(edge_num)]
edges.sort(key=cmp_to_key(lambda x, y: x.width - y.width))
 
for e in edges:
	print(f"({e.a}, {e.b}): {e.width}")

Ver este post de SO para una explicación de cómo funciona cmp_to_key.

Variantes

Ordenamiento descendente

C++JavaPython

Hay muchas formas de hacer esto.

Ordenar y luego invertir:


sort(begin(edges), end(edges));
reverse(begin(edges), end(edges));

Ordenar usando iteradores inversos:


sort(rbegin(edges), rend(edges));

Para estructuras de datos (como pares y arreglos) donde está definido operator>:


sort(edges.begin(), edges.end(), greater<>());

Si sobrecargamos operator< nosotros mismos, podemos reemplazar todas las ocurrencias de x.w < y.w por x.w > y.w.

Podemos reemplazar todas las ocurrencias de Integer.compare(x, y) por -Integer.compare(x, y) en nuestro código de Java.

En Python, podemos pasar el parámetro reverse=True a la función sort o sorted.

Ordenar por múltiples criterios

Ahora, supongamos que queremos ordenar una lista de Edges en orden ascendente, principalmente por ancho y secundariamente por el primer vértice (a). Podemos hacerlo de forma bastante similar a como manejamos el ordenamiento por un criterio antes. Lo que la función comparadora necesita hacer es comparar los pesos si los pesos no son iguales, y en caso contrario comparar los primeros vértices.

C++JavaPython


#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
struct Edge {
	int a, b;
	int width;
 
	bool operator<(const Edge &y) {
		if (width != y.width) { return width < y.width; }
		return a < y.a;
	}
};
 
int main() {
	constexpr int edge_num = 4;
 
	vector<Edge> edges(edge_num);
	for (Edge &e : edges) { cin >> e.a >> e.b >> e.width; }
	sort(edges.begin(), edges.end());
 
	for (const Edge &e : edges) { printf("(%i, %i): %i\n", e.a, e.b, e.width); }
}


import java.io.*;
import java.util.*;
 
class Edge implements Comparable<Edge> {
	public int a, b;
	public int width;
 
	public Edge(int a, int b, int width) {
		this.a = a;
		this.b = b;
		this.width = width;
	}
 
	@Override
	public int compareTo(Edge e) {
		if (width != e.width) { return width - e.width; }
		return a - e.a;
	}
}
 
public class SortingDemo {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
 
		final int edgeNum = 4;
		Edge[] edges = new Edge[edgeNum];
		for (int e = 0; e < edgeNum; e++) {
			edges[e] = new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt());
		}
		Arrays.sort(edges);
 
		for (Edge e : edges) { System.out.printf("(%d, %d): %d\n", e.a, e.b, e.width); }
 
		sc.close();
	}
}

En Python, las tuplas tienen un orden natural basado en sus elementos en orden. Podemos aprovechar esto para escribir un comparador:


from functools import cmp_to_key
 
 
class Edge:
	def __init__(self, a: int, b: int, width: int):
		self.a = a
		self.b = b
		self.width = width
 
 
edge_num = 4
edges = [Edge(*[int(i) for i in input().split()]) for _ in range(edge_num)]
edges.sort(key=lambda edge: (edge.width, edge.a))
 
for e in edges:
	print(f"({e.a}, {e.b}): {e.width}")

Probemos esta versión ligeramente modificada de la entrada de ejemplo:

Aunque las aristas con ancho $3$ y $10$ seguirán ocupando las mismas posiciones, las aristas $\{2, 2, 7\}$ y $\{1, 3, 7\}$ se intercambiarán en el ordenamiento final al incluir el segundo criterio.

Compresión de coordenadas

La compresión de coordenadas (coordinate compression) describe el proceso de mapear cada valor de una lista a su índice si esa lista estuviera ordenada. Por ejemplo, la lista $\{7, 3, 4, 1\}$ se comprimiría a $\{3, 1, 2, 0\}$ . Observemos que $1$ es el menor valor de la primera lista, así que se convierte en $0$ , y $7$ es el mayor valor, así que se convierte en $3$ , el índice más grande de la lista.

Cuando tenemos valores de un rango grande, pero solo nos importa su orden relativo (por ejemplo, si tenemos que saber si un valor está por encima de otro), la compresión de coordenadas es una forma simple de ayudar con la implementación. Por ejemplo, si tenemos un conjunto de enteros que van de $0$ a $10^9$ , no podemos usarlos como índices de arreglo porque tendríamos que crear un arreglo de tamaño $10^9$ , lo que daría un veredicto MLE. Sin embargo, si solo hay $N \leq 10^6$ de esos enteros, podemos comprimir sus coordenadas, lo que garantiza que los valores estarán todos en el rango de $0$ a $N-1$ , que sí se pueden usar como índices de arreglo.

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	Silver	Rectangular Pasture	Difícil	2D Prefix Sums	Solución

Ejemplo 1

Un buen ejemplo de compresión de coordenadas en acción está en la solución de USACO Rectangular Pasture. Otra vez, no entraremos en la solución completa sino que discutiremos cómo se aplica la compresión de coordenadas. Como la solución usa sumas de prefijos 2D (otro tema de Plata), es útil si todas las coordenadas de los puntos están comprimidas al rango $0$ a $N-1$ para poder usarlas como índices de arreglo. Sin compresión de coordenadas, crear un arreglo lo suficientemente grande resultaría en un veredicto Memory Limit Exceeded.

Abajo se encuentra la solución de Rectangular Pasture, que usa compresión de coordenadas al principio. Observemos cómo se usa un comparador personalizado para ordenar los puntos:

C++JavaPython


#include <algorithm>
#include <iostream>
 
using namespace std;
 
typedef pair<int, int> Point;
bool ycomp(Point p, Point q) { return p.second < q.second; }
 
const int MAX_N = 2500;
int pref[MAX_N + 1][MAX_N + 1];
Point p[MAX_N];
 
int rsum(int x1, int y1, int x2, int y2) {
	return pref[x2 + 1][y2 + 1] - pref[x2 + 1][y1] - pref[x1][y2 + 1] + pref[x1][y1];
}
 
int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		p[i] = make_pair(x, y);
	}
 
	sort(p, p + n);
	for (int i = 0; i < n; i++) { p[i].first = i + 1; }
	sort(p, p + n, ycomp);
	for (int i = 0; i < n; i++) { p[i].second = i + 1; }
 
	for (int i = 0; i < n; i++) { pref[p[i].first][p[i].second] = 1; }
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
		}
	}
	long long answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			int x1 = min(p[i].first, p[j].first) - 1;
			int x2 = max(p[i].first, p[j].first) - 1;
			answer += rsum(0, i, x1, j) * rsum(x2, i, n - 1, j);
		}
	}
 
	cout << answer + 1 << endl;
}


import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class RectangularPasture {
	static int[][] sums;
 
	static int getSum(int fromX, int toX, int fromY, int toY) {
		return sums[toX][toY] - sums[fromX - 1][toY] - sums[toX][fromY - 1] +
		    sums[fromX - 1][fromY - 1];
	}
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
 
		int[] xs = new int[n];
		int[] ys = new int[n];
 
		Integer[] cows = new Integer[n];
		for (int j = 0; j < n; j++) {
			xs[j] = in.nextInt();
			ys[j] = in.nextInt();
			cows[j] = j;
		}
 
		Arrays.sort(cows, Comparator.comparingInt(j -> xs[j]));
		for (int x = 1; x <= n; x++) { xs[cows[x - 1]] = x; }
		Arrays.sort(cows, Comparator.comparingInt(j -> ys[j]));
		for (int y = 1; y <= n; y++) { ys[cows[y - 1]] = y; }
 
		sums = new int[n + 1][n + 1];
		for (int j = 0; j < n; j++) { sums[xs[j]][ys[j]]++; }
		for (int x = 0; x <= n; x++) {
			for (int y = 0; y <= n; y++) {
				if (x > 0) { sums[x][y] += sums[x - 1][y]; }
				if (y > 0) { sums[x][y] += sums[x][y - 1]; }
				if (x > 0 && y > 0) { sums[x][y] -= sums[x - 1][y - 1]; }
			}
		}
 
		long answer = n + 1;
		for (int j = 0; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				answer += getSum(Math.min(xs[j], xs[k]), Math.max(xs[j], xs[k]), 1,
				                 Math.min(ys[j], ys[k])) *
				          getSum(Math.min(xs[j], xs[k]), Math.max(xs[j], xs[k]),
				                 Math.max(ys[j], ys[k]), n);
			}
		}
 
		System.out.println(answer);
	}
}


import sys
 
input = sys.stdin.readline
 
n = int(input().strip())
points = [list(map(int, input().strip().split())) for _ in range(n)]
 
points.sort(key=lambda i: i[1])
for i in range(n):
	points[i][1] = i + 1
 
points.sort(key=lambda i: i[0])
for i in range(n):
	points[i][0] = i + 1
 
psa = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for x, y in points:
	psa[x][y] = 1
 
for x in range(1, n + 1):
	for y in range(1, n + 1):
		psa[x][y] += psa[x - 1][y] + psa[x][y - 1] - psa[x - 1][y - 1]
 
ans = n + 1
 
for s in range(n):
	for e in range(s + 1, n):
		srt, end = points[s][0], points[e][0]
		top = max(points[s][1], points[e][1])
		bottom = min(points[s][1], points[e][1])
 
		above = psa[end][n] - psa[srt - 1][n] - psa[end][top] + psa[srt - 1][top]
		below = psa[end][bottom - 1] - psa[srt - 1][bottom - 1]
		ans += (above + 1) * (below + 1)
 
print(ans)

La solución de Rectangular Pasture reemplaza las coordenadas directamente por sus valores comprimidos y olvida los valores reales de las coordenadas porque son innecesarios. Sin embargo, puede haber problemas para los que también necesitemos recordar los valores originales de las coordenadas que comprimimos.

Ejemplo 2

Hecho	Fuente	Nombre	Dificultad	Tags	Solución
	CF	Static Range Queries	Difícil		en el módulo

Este problema requerirá sumas de prefijos y compresión de coordenadas. Sin embargo, la implementación de la compresión de coordenadas en esta solución también requerirá recordar valores además de comprimirlos (a diferencia de simplemente reemplazar los valores originales, como en el problema anterior). Si solo se quiere enfocar en la implementación de la compresión de coordenadas y cómo puede cambiar entre índices comprimidos y valores originales, ver el código contraído de abajo. indices es una lista de valores que hay que comprimir. Después de ordenarla y eliminar los valores duplicados, está lista para usarse. El método getCompressedIndex toma un valor original y hace búsqueda binaria de su posición en indices para obtener su índice comprimido correspondiente. Para ir de un índice comprimido a un valor original, el código puede simplemente acceder a ese índice en indices.

También damos una explicación más detallada:

Explicación detallada

Primero, veamos cómo hallar el valor en cada índice del arreglo $a$ . Sería demasiado lento recorrer cada índice en cada intervalo de actualización y también cada índice en un intervalo de consulta (la complejidad sería $O(C(N+Q))$ , donde $C$ es la coordenada máxima dada en la entrada). Al mismo tiempo, ese enfoque tomaría $O(C)$ de memoria, que también es demasiado. En su lugar, hacemos una observación que hará que las sumas de prefijos juntas con la compresión de coordenadas sean una opción viable.

No todos los índices del rango completo $1...10^9$ se usan en las actualizaciones. De hecho, puede haber intervalos grandes de índices que tienen todos el mismo valor. Llamemos a cada índice que se nombra en la entrada un «índice especial». Ahora, notemos que el valor en cada índice del intervalo entre dos índices especiales consecutivos es el mismo. Esto se debe a que es imposible que haya una actualización que corte entre dos índices especiales consecutivos, porque eso implicaría la existencia de otro índice especial entre dos índices especiales consecutivos, es decir, una contradicción. Llamaremos al intervalo entre dos índices especiales consecutivos un «intervalo especial», y el «valor de un intervalo especial» será el valor que toma cada uno de los elementos dentro de él.

Ahora veamos cómo ayudan las sumas de prefijos (junto con la compresión de coordenadas).

Olvidemos temporalmente los índices especiales. Cuando una actualización nos pide sumar $+v$ al intervalo $[l, r)$ , podemos marcar el índice $l$ con $+v$ y el índice $r$ con $-v$ en un «arreglo de diferencias». Lo llamamos arreglo de diferencias porque nos dice el cambio de valor al ir de un índice al siguiente. Tomar las sumas de prefijos del arreglo de diferencias resultará en los valores reales del arreglo $a$ (conviene tomarse un momento para convencerse de esto antes de seguir).

Como los índices que tenemos que marcar van de $0...10^9$ , usaría demasiada memoria usar esos índices de forma directa. Sin embargo, solo se usan de verdad los índices especiales, así que nos motiva cambiar el significado del arreglo de diferencias para ahorrar memoria (notemos que hay a lo sumo $2 \cdot (N+Q)$ índices especiales porque se dan $2$ índices por cada actualización y consulta). En lugar de que el arreglo de diferencias represente el cambio de valor de un índice especial al siguiente, que represente el cambio de valor de un intervalo especial al siguiente. Ahora solo tiene que tener tamaño $2 \cdot (N+Q)$ . Tomar las sumas de prefijos de este arreglo de diferencias dará los valores de todos los intervalos especiales.

Solo tenemos que comprimir las coordenadas de los índices especiales para poder usarlos cómodamente como índices de arreglo para el arreglo de diferencias. Hacemos esta compresión de coordenadas manteniendo una lista ordenada de todos los índices especiales, y usando la posición de cada índice especial en esa lista como su índice comprimido. Para hallar la posición de un índice especial en la lista ordenada (es decir, su índice comprimido), podemos hacer búsqueda binaria sobre la lista. La siguiente parte de la solución mostrará por qué era importante guardar los índices originales.

Así, con sumas de prefijos y compresión de coordenadas, es posible hallar el valor de cada intervalo especial. Ahora terminemos el problema. Sea la «suma de un intervalo especial» la suma de cada elemento dentro del intervalo especial, o en otras palabras, la longitud del intervalo por su valor. Ya conocemos el valor de cada intervalo especial, pero también podemos obtener su longitud porque guardamos los índices originales. La longitud de un intervalo es su índice derecho menos su índice izquierdo, que podemos hallar accediendo a la lista ordenada. Como resultado, también podemos hallar la suma de cada intervalo especial con la información que tenemos. Cuando el problema nos consulta la suma entre dos índices especiales, sumamos las sumas de los intervalos especiales entre esos dos índices especiales. Así, si creamos otro arreglo de sumas de prefijos sobre las sumas de los intervalos especiales, podemos responder estas consultas de suma de rango en O(1) cada una.

C++JavaPython


#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll difference_array[400005];
// difference_array[i] = the difference of the values between special intervals
// i-1 and i
 
int widths[400005];         // width[i] = the length of special interval i
ll interval_value[400005];  // interval_value[i] = the value of special interval
                            // i
// the sum of a special interval is interval_value[i] * width[i]
 
ll prefix_sums[400005];  // prefix_sums[i] = prefix sum of the sums of special
                         // intervals up to i
 
vector<int> indices;                        // sorted list of special indices
pair<int, int> queries[100005];             // queries given in the input <l, r>
pair<pair<int, int>, int> updates[100005];  // updates in given in the input <<l, r>, v>
 
// EndCodeSnip
 
/** @return the compressed index of a special index (it), aka its index in the
 * compressed list */
int getCompressedIndex(int a) {
	return lower_bound(indices.begin(), indices.end(), a) - indices.begin();
}
 
int main() {
	int N, Q;
	cin >> N >> Q;
 
	for (int i = 0; i < N; i++) {
		int l, r, v;
		cin >> l >> r >> v;
		indices.push_back(l);
		indices.push_back(r);
		updates[i] = {{l, r}, v};
	}
	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r;
		indices.push_back(l);
		indices.push_back(r);
		queries[i] = {l, r};
	}
 
	// Perform coordinate compression by sorting and removing duplicates
	sort(indices.begin(), indices.end());
	indices.erase(unique(indices.begin(), indices.end()), indices.end());
 
	// We create the difference array, using coordinate compression and binary
	// search to get the compressed index of each special index Note the 1-based
	// indexing for convenience
	for (int i = 0; i < N; i++) {
		auto a = updates[i];
 
		difference_array[getCompressedIndex(a.first.first) + 1] += a.second;
		difference_array[getCompressedIndex(a.first.second) + 1] -= a.second;
	}
 
	// By keeping track of the original values of the special indices, we can
	// also figure out the lengths of each special interval
	for (int i = 0; i < indices.size() - 1; i++) {
		widths[i + 1] = indices[i + 1] - indices[i];
	}
 
	// We use prefix sums of the difference array to get the values of the
	// intervals
	for (int i = 1; i < indices.size(); i++) {
		interval_value[i] = interval_value[i - 1] + difference_array[i];
	}
 
	// We use prefix sums over the sums of the special intervals to be able to
	// answer queries quickly
	for (int i = 1; i < indices.size(); i++) {
		prefix_sums[i] = prefix_sums[i - 1] + interval_value[i] * widths[i];
	}
 
	// Classic use of prefix sum array to answer range sum queries
	for (int i = 0; i < Q; i++) {
		cout << prefix_sums[getCompressedIndex(queries[i].second)] -
		            prefix_sums[getCompressedIndex(queries[i].first)]
		     << "\n";
	}
}


import java.io.*;
import java.util.*;
 
public class StaticRangeQueries {
	// custom class that stores a few integers (used for directly storing the
	// queries and updates given in the input)
	static class Query {
		int l, r, v;
		public Query(int l, int r, int v) {
			this.l = l;
			this.r = r;
			this.v = v;
		}
 
		public Query(int l, int r) {
			this.l = l;
			this.r = r;
		}
	}
 
	static long difference_array[];
	// difference_array[i] = the difference of the values between special
	// intervals i-1 and i
 
	static int widths[];           // width[i] = the length of special interval i
	static long interval_value[];  // interval_value[i] = the value of special
	                               // interval i
 
	static long prefix_sums[];  // prefix_sums[i] = prefix sum of the sums of
	                            // special intervals up to i
 
	static ArrayList<Integer> indices;  // sorted list of special indices
	static Query queries[];             // queries given in the input <l, r>
	static Query updates[];             // updates in given in the input <l, r, v>
 
	/**
	 * @return the compressed index of a special index (it), aka its index in the
	 *     compressed list
	 */
	static int getCompressedIndex(int a) {
		return Collections.binarySearch(indices, a);
	}
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()), Q = Integer.parseInt(st.nextToken());
 
		indices = new ArrayList<Integer>();
		queries = new Query[Q];
		updates = new Query[N];
 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken()),
			    r = Integer.parseInt(st.nextToken()),
			    v = Integer.parseInt(st.nextToken());
			indices.add(l);
			indices.add(r);
			updates[i] = new Query(l, r, v);
		}
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken()),
			    r = Integer.parseInt(st.nextToken());
			indices.add(l);
			indices.add(r);
			queries[i] = new Query(l, r);
		}
 
		// Coordinate compress by adding the indices to a sorted set and vice versa
		TreeSet<Integer> temp = new TreeSet<Integer>(indices);
		indices.clear();
		indices.addAll(temp);
 
		difference_array = new long[indices.size() + 5];
		widths = new int[indices.size() + 5];
		interval_value = new long[indices.size() + 5];
		prefix_sums = new long[indices.size() + 5];
 
		// We create the difference array, using coordinate compression and
		// binary search to get the index of each special interval Note the
		// 1-based indexing for convenience
		for (int i = 0; i < N; i++) {
			Query a = updates[i];
 
			difference_array[getCompressedIndex(a.l) + 1] += a.v;
			difference_array[getCompressedIndex(a.r) + 1] -= a.v;
		}
 
		// By keeping track of the original values of the special indices, we
		// can also figure out the lengths of each special interval
		for (int i = 0; i < indices.size() - 1; i++) {
			widths[i + 1] = indices.get(i + 1) - indices.get(i);
		}
 
		// We use prefix sums of the difference array to get the actual value of
		// the intervals
		for (int i = 1; i < indices.size(); i++) {
			interval_value[i] = interval_value[i - 1] + difference_array[i];
		}
 
		// We use prefix sums over the sums of the special intervals to be able
		// to answer queries quickly
		for (int i = 1; i < indices.size(); i++) {
			prefix_sums[i] = prefix_sums[i - 1] + interval_value[i] * widths[i];
		}
 
		// Classic use of prefix sum array to answer range sum queries
		for (int i = 0; i < Q; i++) {
			System.out.println(prefix_sums[getCompressedIndex(queries[i].r)] -
			                   prefix_sums[getCompressedIndex(queries[i].l)]);
		}
	}
}


N, Q = map(int, input().split())
 
coordinates = {-1}  # dummy coordinate to the left of everything
updates = dict()
queries = []
 
for n in range(N):  # read updates
	left, right, value = map(int, input().split())
	coordinates.add(left)
	coordinates.add(right)
	updates[left] = updates.get(left, 0) + value
	updates[right] = updates.get(right, 0) - value
 
for q in range(Q):  # read queries
	left, right = map(int, input().split())
	coordinates.add(left)
	coordinates.add(right)
	queries.append((left, right))
 
# create coordinate compression
coordinates = sorted(coordinates)
index = {coordinates[i]: i for i in range(len(coordinates))}
 
# compute prefix sums and store them at compressed coordinates
value = 0
prefix_sum = [0]
for i in range(1, len(coordinates)):
	prefix_sum.append(prefix_sum[-1] + value * (coordinates[i] - coordinates[i - 1]))
	value += updates.get(coordinates[i], 0)
 
# answer range queries by changing coordinates
answers = []
 
for left, right in queries:
	answers.append(prefix_sum[index[right]] - prefix_sum[index[left]])
 
print(*answers)

Problemas

Fuente	Nombre	Dificultad	Tags	Solución
CSES	Restaurant Customers	Fácil	Sorting, Prefix Sums	Solución
CF	Covered Points Count	Normal	Sorting, Prefix Sums, Coordinate Compression	Solución
Silver	Lifeguards	Normal	Sorting, Prefix Sums	Solución
Silver	★ Rental Service	Normal	Sorting, Prefix Sums	Solución
Silver	★ Mountain View	Normal	Sorting	Solución
Silver	Stuck in a Rut	Normal	Sorting	Solución
Gold	★ Splitting the Field	Normal	Sorting, Prefix Sums	Solución
CF	The Smallest String Concatenation	Normal	Sorting	Solución
CF	Nezzar and Symmetric Array	Normal	Sorting, Prefix Sums	—
CF	Correct Placement	Normal	Sorting	—
Silver	Triangles	Difícil	Sorting	Solución
Silver	Out Of Sorts	Difícil	Sorting	Solución
Silver	Meetings	Muy difícil	Sorting	Solución

Quiz

Pregunta 1/2

¿A qué se comprimiría por coordenadas la lista

\{40, 21, -4, 1000, 5\}

Comparadores personalizados y compresión de coordenadas

Recursos

Introducción

Estructuras de datos de la librería

Pares

Arreglos

Comparadores

Sobrecarga de operator<

Función de comparación

Implementar Comparable<T>

Función comparadora

Función key

Comparador

Variantes

Ordenamiento descendente

Ordenar por múltiples criterios

Compresión de coordenadas

Ejemplo 1

Ejemplo 2

Problemas

Quiz

Sobrecarga de `operator<`

Implementar `Comparable<T>`