Covered Points Count

Solución 1: Compresión de coordenadas

Por las restricciones grandes de $l_i$ y $r_i$ , es imposible hacer fuerza bruta sobre la cantidad de segmentos que se intersectan en cada punto de la recta. Sin embargo, nótese que podemos comprimir las coordenadas y “pretender” que las coordenadas están entre $1$ y $n$ .

Esto nos permite aplicar sumas de prefijos en cada punto de nuestra recta numérica comprimida y retransformar estas coordenadas comprimidas a los extremos originales $l_i$ y $r_i$ . Para comprimir las coordenadas, podemos o bien ordenarlas o usar un mapa ordenado.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int n;
	cin >> n;
	// Guarda los extremos originales para usarlos después en el arreglo de frecuencias
	vector<pair<ll, ll>> segments(n);
	// Guarda solo los extremos únicos en orden
	set<ll> points;
	for (int i = 0; i < n; i++) {
		cin >> segments[i].first >> segments[i].second;
		points.insert(segments[i].first);
		points.insert(segments[i].second + 1);
	}
 
	int cur = 0;
	// Este mapa guarda las coordenadas comprimidas.
	map<ll, int> compressed;
	vector<ll> coords;
	for (const ll c : points) {
		// Asignamos c a cur, donde cur es nuestra coordenada comprimida para "a".
		compressed[c] = cur;
		/*
		 * Todavía hay que recordar los extremos originales para
		 * retransformar las coordenadas comprimidas
		 */
		coords.push_back(c);
		cur++;
	}
	// Guarda la frecuencia de un extremo dado.
	vector<int> freq(2 * n);
	for (int i = 0; i < n; i++) {
		/*
		 * Un segmento va de [l*, r*], así que debemos terminar el segmento
		 * en r* + 1 para asegurar que r* quede incluido en el segmento.
		 */
		freq[compressed[segments[i].first]]++;
		freq[compressed[segments[i].second + 1]]--;
	}
	// sumas de prefijos de la cantidad de puntos en un extremo comprimido dado
	for (int i = 1; i < 2 * n; i++) { freq[i] += freq[i - 1]; }
 
	// covered_num[i] := cantidad de puntos cubiertos por exactamente i segmentos
	vector<ll> covered_num(n + 1);
	for (int i = 1; i < coords.size(); i++) {
		/*
		 * Descomprimimos los extremos de una frecuencia dada y sumamos los puntos
		 * de este rango a la respuesta.
		 */
		covered_num[freq[i - 1]] += coords[i] - coords[i - 1];
	}
 
	for (int i = 1; i <= n; i++) { cout << covered_num[i] << " "; }
	cout << endl;
}


import java.io.*;
import java.util.*;
 
public class CoveredPointsCount {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
 
		Pair[] segments = new Pair[n];
		// Guarda solo los extremos únicos en orden
		SortedSet<Long> points = new TreeSet<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			segments[i] = new Pair(Long.parseLong(st.nextToken()),
			                       Long.parseLong(st.nextToken()));
			points.add(segments[i].first);
			points.add(segments[i].second + 1);
		}
		br.close();
 
		int cur = 0;
		// Este mapa guarda las coordenadas comprimidas.
		Map<Long, Integer> compressed = new HashMap<>();
		List<Long> coords = new ArrayList<>();
		for (long c : points) {
			// Asignamos c a cur, donde cur es nuestra coordenada comprimida para "a".
			compressed.put(c, cur);
			/*
			 * Todavía hay que recordar los extremos originales para
			 * retransformar las coordenadas comprimidas
			 */
			coords.add(c);
			cur++;
		}
		// Guarda la frecuencia de un extremo dado.
		int[] freq = new int[2 * n];
		for (int i = 0; i < n; i++) {
			/*
			 * Un segmento va de [l*, r*], así que debemos terminar el segmento
			 * en r* + 1 para asegurar que r* quede incluido en el segmento.
			 */
			freq[compressed.get(segments[i].first)]++;
			freq[compressed.get(segments[i].second + 1)]--;
		}
		// sumas de prefijos de la cantidad de puntos en un extremo comprimido dado
		for (int i = 1; i < 2 * n; i++) { freq[i] += freq[i - 1]; }
 
		// coveredNum[i] := cantidad de puntos cubiertos por exactamente i segmentos
		long[] coveredNum = new long[n + 1];
		for (int i = 1; i < coords.size(); i++) {
			/*
			 * Descomprimimos los extremos de una frecuencia dada y sumamos los
			 * puntos de este rango a la respuesta.
			 */
			coveredNum[freq[i - 1]] += coords.get(i) - coords.get(i - 1);
		}
 
		for (int i = 1; i <= n; i++) {
			System.out.print(coveredNum[i]);
			System.out.print(" ");
		}
	}
 
	// BeginCodeSnip{Long Pair Class}
	private static class Pair {
		public long first, second;
 
		public Pair(long f, long s) {
			first = f;
			second = s;
		}
	}
	// EndCodeSnip
}


n = int(input())
# Guarda los extremos originales para usarlos después en el arreglo de frecuencias
segments = []
 
# Guarda solo los extremos únicos en orden
points = set()
 
for _ in range(n):
	l, r = map(int, input().split())
	segments.append((l, r))
	points.add(l)
	points.add(r + 1)
 
# Este mapa guarda las coordenadas comprimidas.
compressed = {}
coords = []
 
for cur, c in enumerate(sorted(points)):
	compressed[c] = cur
	coords.append(c)
 
# Guarda la frecuencia de un extremo dado
freq = [0] * (2 * n)
 
for l, r in segments:
	# Un segmento va de [l*, r*], así que debemos terminar el segmento
	# en r* + 1 para asegurar que r* quede incluido en el segmento.
	freq[compressed[l]] += 1
	freq[compressed[r + 1]] -= 1
 
# Sumas de prefijos de la cantidad de puntos en un extremo comprimido dado
for i in range(1, len(freq)):
	freq[i] += freq[i - 1]
 
# covered_num[i] := cantidad de puntos cubiertos por exactamente i segmentos
covered_num = [0] * (n + 1)
 
for i in range(1, len(coords)):
	# Descomprimimos los extremos de una frecuencia dada
	# y sumamos los puntos de este rango a la respuesta.
	covered_num[freq[i - 1]] += coords[i] - coords[i - 1]
 
print(" ".join(map(str, covered_num[1:])))

Solución 2: Mapa

Como alternativa, también podemos usar un mapa para guardar frecuencias en cada punto de interés e iterarlos en orden. Así, no hace falta hacer de forma explícita la compresión de coordenadas.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++Python


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	int n;
	cin >> n;
 
	// coordenadas distintas de inicio y fin de los segmentos
	set<ll> points;
	// frecuencia de una coordenada dada
	map<ll, int> freq;
	for (int i = 0; i < n; i++) {
		ll l, r;
		cin >> l >> r;
 
		/*
		 * Un segmento va de [l*, r*], así que debemos terminar el segmento
		 * en r* + 1 para asegurar que r* quede incluido en el segmento.
		 */
		freq[l]++;
		freq[r + 1]--;
		points.insert(l);
		points.insert(r + 1);
	}
 
	// cantidad de segmentos superpuestos en la posición actual
	int layers = freq[*points.begin()];
	auto it = next(points.begin());
	// covered_num[i] := cantidad de puntos cubiertos por exactamente i segmentos
	vector<ll> covered_num(n + 1);
 
	/*
	 * recorremos todas las coordenadas de interés y sumamos la cantidad de puntos
	 * de cada rango a la respuesta correspondiente
	 */
	while (it != points.end()) {
		covered_num[layers] += (*it - *prev(it));
		layers += freq[*it];
		it++;
	}
 
	for (int i = 1; i <= n; i++) { cout << covered_num[i] << " \n"[i == n]; }
}


from collections import defaultdict
 
n = int(input())
 
points = set()  # coordenadas distintas de inicio y fin de los segmentos
freq = defaultdict(int)  # frecuencia de una coordenada dada
 
for _ in range(n):
	l, r = map(int, input().split())
 
	# Un segmento va de [l*, r*], así que debemos terminar el segmento
	# en r* + 1 para asegurar que r* quede incluido en el segmento.
	freq[l] += 1
	freq[r + 1] -= 1
	points.add(l)
	points.add(r + 1)
 
sorted_points = sorted(points)
 
# cantidad de segmentos superpuestos en la posición actual
layers = freq[sorted_points[0]]
 
# covered_num[i] := cantidad de puntos cubiertos por exactamente i segmentos
covered_num = [0] * (n + 1)
 
# recorremos todas las coordenadas de interés y sumamos la
# cantidad de puntos de cada rango a la respuesta correspondiente
for i in range(1, len(sorted_points)):
	covered_num[layers] += sorted_points[i] - sorted_points[i - 1]
	layers += freq[sorted_points[i]]
 
print(" ".join(map(str, covered_num[1:])))