Amassando ideas

Esta vez no haré un resumen del eununciado porque ya es muy corto y asumo que sabes inglés si pretendes resolver problemas en CSES. También es necesario conocer lo básico de análisis de complejidad de algoritmos, la STL de C++, y el Segment Tree.

Importante: Los índices de los vectores y otras estructuras de datos están en base $0$.

Solución ingenua

Para cada rango, se itera sobre cada uno de los otros y se comprueba si el otro rango contiene al primer rango o viceversa. Como hay $n$ rangos, por cada rango habrá que iterar sobre otros $n-1$ rangos, por lo que la complejidad temporal de esta solución es de $O(n^2)$.

Para comprobar que la solución no es lo suficientemente eficiente hay que considerar que $n$ puede ser hasta $2 \times 10^5$ y en ese caso nuestro programa debe hacer al menos $n^2 = 4 \times 10^10$ iteraciones, lo que es demasiado para que un procesador común y corriente no se demore más que el tiempo límite. Por tanto, habrá que buscar una solución más eficiente.

Pongamos orden

Probemos a ordenar los rangos de menor a mayor valor del límite izquierdo y luego el límite derecho de cada rango (es decir, si dos rangos tienen el mismo límite izquierdo, entonces el que tiene menor límite derecho va primero). Es una técnica muy común para resolver problemas de este tipo. Gracias a ordenar los datos de entrada, sabemos que al iterar por la lista ordenada de rangos, ninguno de los rangos por lo que ya hayamos iterado estará contenido dentro del rango de la iteración actual (llamémoslo rango $i$, porque está en el índice $i$ del vector ordenado).

Para ejemplificar lo anterior, usemos el caso de prueba de ejemplo pero ordenado:

1 6 2 4 3 6 4 8

Cuando se procese el rango (3, 6), es claro que los rangos (1, 6) y (2, 4) no estarán contenidos en éste.

Entonces, la idea de la solución es iterar por cada uno de los rangos (ahora ordenados) y para cada uno calcular tanto el número de rangos que contiene y el número de rangos que lo contienen.

Ahora sería tentador pensar que para cada rango basta con una búsqueda binaria que nos diga cuántos rangos empiezan entre el $x$ y el $y$ del rango $i$. Pero es mucho más complicado pues varios de esos rangos pueden terminar después del $y$. Por eso necesitamos una solución más ingeniosa.

Inclusión-Exclusión

El problema puede hacerse mucho más sencillo si a $n$, el número total de rangos, le restamos el número de rangos no contenidos por el rango $i$, es decir, que empiezan antes del $x$ o terminan después del $y$, que a su vez es lo mismo que:

1. el número de rangos que empiezan antes del $x$, más
2. el número de rangos que terminan después del $y$, menos
3. el número de rangos que empiezan antes del $x$ y después del $y$.

Lo anterior es una aplicación del Principio de Inclusión-Exclusión, que dados dos conjuntos $A$ y $B$, se tiene que $|A \cup B| = |A| + |B| – |A \cap B|$. En este caso $A$ es el conjunto de los rangos que empiezan antes del $x$ y $B$ es el conjunto de los rangos que terminan después del $y$.

A continuación veremos cómo calcular cada uno de los tres números.

Calculemos el 1ero

Gracias al ordenamiento hecho al principio, ya casi tenemos el número de rangos que empiezan antes del $x$. El problema es que hay rangos ya procesados que empiezan justo en $x$. Una forma de solucionar este problema es guardar un entero $j$ con el primer índice tal que el rango correspondiente a dicho índice en el vector ordenado empiece en $x$. Así el número de rangos que empiezan antes del $x$ del rango $i$ es $j+1$.

Calculemos el 2do

Después de leer la entrada, creamos otro vector que contenga los límites de los rangos pero de forma invertida, el $y$ como primer elemento y el $x$ como el segundo. También hay que ordenar este vector comparando sus elementos de la misma forma que con el vector original, de modo que cuando procesemos el rango $i$ del vector original ordenado para calcular la respuesta, hagamos una búsqueda binaria por este nuevo vector para calcular el 2do número buscado, que es igual a $n$ menos la posición retornada por lower_bound al colocar un rango que comienza con $y+1$.

Calculemos el 3ero

¿Recuerdas que todos los elementos antes del $j$-ésimo empiezan antes que el rango $i$? Podemos aprovechar esa peculiaridad para tener un conteo de los límites derechos que llevamos hasta el momento.

Una idea aparentemente útil consiste en crear un vector que sirva como histograma tal que en el índice $k$ del vector indique cuántos rangos procesados antes que el $i$-ésimo terminan con $k$. Al procesar un rango, el 3er número buscado es la suma de todos los elementos del vector desde el índice $y+1$ hasta el $10^9$, y luego de procesar el rango se actualiza el vector con el $y$ del rango.

Lamentablemente, el intento de solución anterior tiene dos problemas: por cada rango habría que iterar por aproximadamente $10^9$ elementos en el peor caso, y hay que mantener un vector de $10^9$ elementos, que consumiría más de 1GB de memoria. Un Segment Tree de sumas arreglaría el problema de las iteraciones para sumar los elementos, pero aún así el vector a crear sería gigantesco debido al rango de valores necesario. Pero aún hay esperanza, pues aunque el rango al que pertenecen los límites de los rangos es enorme, no hay más de $2 \times 2 \times 10^5 = 4 \times 10^5$ números distintos en la entrada, lo que nos permite usar una técnica llamada compresión de coordenadas.

Compresión de coordenadas

La compresión de coordenadas consiste en asignar un número distinto a cada número de la entrada para que el rango al que pertenecen los números a manejar sea más reducido. Como hay a lo más $4 \times 10^5$ números que describen los rangos, entonces ese será el límite de los números que usaremos en el Segment Tree, y no $10^9$.

La idea es que el orden relativo de los números se mantenga. Por ejemplo, no queremos asignarle un $2$ a un $100$ y al mismo tiempo asignarle un $5$ a un $40$. Para esto hay varias formas de implementar la compresión de coordenadas, pero yo presentaré una distinta a la del otro blog.

Creamos un set al que le insertamos los valores de los rangos a medida que se ingresan por la entrada, un map que contenga las asociaciones de números, y un contador con el número de elementos distintos que llevamos. Después iteramos por cada elemento del set, primero aumentamos el contador en $1$ y luego actualizamos el map asociando el elemento a procesar del set con el contador. Finalmente se modifican los vectores con los rangos (tanto el original como el que tiene los rangos invertidos) reemplazando cada número por el que tiene asociado en el map.

El proceso anterior se realiza antes de ordenar los vectores, para no gastar tiempo de más.

Ahora la cantidad de memoria consumida por la solución será muchísimo menor a lo que se tenía pensado originalmente. Un problema que parecía imposible se solucionó con un truco sencillo ;)

Aún falta algo

Nos falta calcular el número de rangos que contienen al rango $i$, para cada $i$ entre $0$ y $n-1$. La forma de hacerlo es parecida a la del 3er valor pero con algunas diferencias. Hay que considerar los rangos que empiezan con el mismo $x$ que el rango $i$ pero que tienen un $y$ superior. Además, la consulta al Segment Tree debe ser ligeramente distinta. La implementación de la solución descrita aquí queda como ejercicio para el lector o la lectora.