Help Yourself

Contemos cuánto contribuye cada segmento a la complejidad total si recorremos todos los inicios y finales en orden.

Análisis oficial (C++) 

Explicación

El enfoque de fuerza bruta de este problema sería recorrer todos los subconjuntos y contar el número de componentes conexas de cada subconjunto.

Sin embargo, este enfoque tiene complejidad temporal $\mathcal{O}(2^N * N)$ y es demasiado grande para las restricciones de tiempo del problema, excepto en los primeros tres casos de prueba. Para optimizarlo, podemos calcular cuánto contribuye cada segmento a la respuesta total.

Consideremos el caso de prueba de ejemplo

Para cada segmento podemos listar los subconjuntos en los que el segmento se cuenta. Solo debemos listar los subconjuntos en los que el segmento es el comienzo de una componente conexa, porque de lo contrario sobrecontaríamos.

Usando el caso de prueba de ejemplo, los segmentos serán los siguientes:

• 1.er segmento: $[1,2,3]$, $[1,2]$, $[1,3]$ y $[1]$
• 2.º segmento: $[2,3]$ y $[2]$
• 3.er segmento: $[2,3]$ y $[3]$

Podemos recorrer toda la longitud del segmento (de $1$ a $2N$). Decimos que un segmento está abierto en cierto punto si lo contiene y cerrado si no. En cada paso, mantenemos el número de segmentos abiertos. Si se abre un segmento nuevo, podemos calcular cuánto contribuye a la respuesta asegurándonos de no sobrecontar. Necesitamos hallar el número de subconjuntos en los que este segmento es el comienzo de una componente conexa.

No incluimos subconjuntos que tengan los segmentos ya abiertos porque, en ese caso, el segmento no será el comienzo de la componente conexa. Además, debemos incluir el segmento actual en el subconjunto. Así, habrá $2^{N - open}$ subconjuntos en los que el segmento actual contribuye $1$ a la respuesta, donde ‘open’ es el número de segmentos abiertos incluyendo el recién abierto. Podemos sumar este valor a la respuesta final.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
 
const ll MOD = 1e9 + 7;
 
int main() {
	freopen("help.in", "r", stdin);
	int n;
	cin >> n;
	// Marcamos los puntos donde un segmento se abrió o se cerró
	vi a(2 * n + 1, 0);
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[x]++;
		a[y]--;
	}
 
	// Precalculamos potencias de 2
	vl pow(n);
	pow[0] = 1;
	for (int i = 1; i <= n - 1; i++) { pow[i] = pow[i - 1] * 2 % MOD; }
 
	int open_segs_num = 0;
	ll ans = 0;
	for (int i = 1; i <= 2 * n; i++) {
		// Actualizamos el número de segmentos abiertos
		open_segs_num += a[i];
		/*
		 * Si se abre un segmento nuevo, contamos el número de subconjuntos
		 * en los que este segmento nuevo es el comienzo de una componente conexa
		 */
		if (a[i] == 1) { ans = (ans + pow[n - open_segs_num]) % MOD; }
	}
	freopen("help.out", "w", stdout);
	cout << ans << endl;
}

MOD = 1000000007
 
n = int(open("help.in".readline()))
 
# Si el segmento está abierto el valor será positivo; si no, negativo
a = [0] * (2 * n + 1)
for i in range(n):
	x, y = map(int, filein.readline().split())
	a[x] += 1  # abrir
	a[y] -= 1  # cerrar
 
# precalculamos las potencias de 2
power = [1] * n
for i in range(1, n):
	power[i] = power[i - 1] * 2 % MOD
 
open_segs = 0
ans = 0
for i in range(1, 2 * n + 1):
	open_segs += a[i]
	if a[i] == 1:
		ans = (ans + power[n - open_segs]) % MOD
 
print(ans, file=open("help.out", "w"))

Explicación

Sea $c_k$ la suma de complejidades de los primeros $k$ segmentos. Usamos $c_k$ para calcular $c_{k+1}$ en un proceso similar a la programación dinámica, y nuestra respuesta final es $c_N$.

De $c_k$ a $c_{k+1}$, nuestro nuevo conjunto de subconjuntos es

La suma de las complejidades del conjunto anterior de subconjuntos sigue siendo $c_k$. Sin embargo, agregar $\texttt{seg}_{k+1}$ a cada uno de ellos puede fusionar muchos segmentos que antes eran disjuntos (si $\texttt{seg}_{k+1}$ resultaba intersectar a todos ellos).

Para controlar esto, ordenamos los segmentos por sus extremos izquierdos. Esto significa que cada segmento nuevo solo puede o bien fusionarse a sí mismo en un segmento anterior (sin fusionar segmentos que antes eran disjuntos) o bien formar un nuevo segmento disjunto.

También sabemos que nuestro segmento nuevo forma un nuevo segmento disjunto si y solo si se fusiona con segmentos anteriores que no lo intersectan. Por lo tanto, la fórmula de transición es:

Si $x$ es el número de segmentos anteriores que no intersectan $segment_k$,

Para contar $x$, usamos un indexed set que guarda los extremos derechos de los segmentos anteriores. Podemos usar su función order_of_key para determinar el número de segmentos anteriores que terminan antes de nuestro extremo izquierdo.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Importing indexed sets}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// EndCodeSnip
 
const int MOD = 1e9 + 7;
 
// BeginCodeSnip{Binary Exponentiation (from module)}
long long exp(long long x, long long n) {
	assert(n >= 0);
	x %= MOD;  // nota: MOD * MOD debe ser menor que 2^63 para evitar desbordamiento de ll
	long long res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % MOD; }
		x = x * x % MOD;
		n /= 2;
	}
	return res;
}
// EndCodeSnip
 
int main() {
	ifstream fin("help.in");
	int n;
	vector<pair<int, int>> ranges;
 
	fin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		fin >> a >> b;
		ranges.push_back({a, b});
	}
 
	// Ordenamos los rangos por sus valores izquierdos
	sort(ranges.begin(), ranges.end());
 
	Tree<pair<int, int>> pastend;
	int tot = 0;
	for (int i = 0; i < n; i++) {
		int left = ranges[i].first, right = ranges[i].second;
 
		// Contamos # de rangos anteriores que no intersectan
		int unaffiliated = pastend.order_of_key({left, -1});
 
		tot = (2 * tot) % MOD + exp(2, unaffiliated);
		tot %= MOD;
		pastend.insert({right, i});
	}
 
	ofstream("help.out") << tot << endl;
}