Skip to Content
CTRL K

Land of the Rainbow Gold

Explicación

Resumen

Fórmula de Euler + una estructura de datos adecuada para consultas de rango 2D.

Intuición

En este problema nos piden contar la cantidad de regiones contiguas de celdas en varios rectángulos planos. Esas regiones están separadas por segmentos de río y por los bordes del rectángulo.

¿En qué otro lugar contamos la cantidad de regiones en una superficie plana?

Exacto: usamos la fórmula de Euler para contar la cantidad de caras de un grafo planar . Esto sugiere que debemos convertir nuestros rectángulos en grafos planares.

Construir el grafo planar

Podemos convertir un rectángulo en un grafo planar así:

  • Colocar segmentos de río temporales fuera del borde del rectángulo.
  • Por cada segmento de río, insertamos sus 4 esquinas en un conjunto de nodos y sus 4 lados en un conjunto de aristas.

Observemos que el grafo resultante es planar, así que podemos aplicar la fórmula de Euler.

Aplicar la fórmula de Euler

Para un grafo planar, la fórmula de Euler es F=E−V+1+CF = E - V + 1 + C, donde FF es el número de caras (incluida la cara de fondo), EE es el número de aristas, VV es el número de vértices y CC es el número de componentes conexas.

Observemos que FF en nuestro grafo planar es igual a 1+R+A1 + R + A, donde RR es el número de segmentos de río y AA es la respuesta de la consulta. Esto significa que debemos restar R+1R + 1 de FF para obtener AA.

Como todo el río es una gran componente conexa, podemos simplemente revisar si el río toca el rectángulo envolvente para determinar CC.

Hallar EE, VV y RR es bastante más complicado.

Hallar EE, VV y RR

Para hallar EE, VV y RR, podemos usar una estructura de datos que maneje consultas de rango 2D de forma eficiente.

Sin embargo, las coordenadas de la grilla pueden ser muy grandes, así que un BIT 2D simple o un Árbol de Segmentos no sirven aquí.

Para sortear esto, podemos usar un BIT 2D con compresión de coordenadas o un Árbol de Segmentos persistente. Ver las secciones sobre consultas de suma 2D offline o árboles de segmentos persistentes para más detalles.

Implementación

Con un Árbol de Segmentos persistente.

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

Complejidad de memoria: O(Nlog⁡N)\mathcal{O}(N \log N)

#include "rainbow.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
 
const int MAXN = 2e5, MAXSEG = (6e5 + 9) * 19 + 1;
 
int cnt = 1, segtree[MAXSEG], left_c[MAXSEG], right_c[MAXSEG];
 
struct Segtree {
	set<int> data[MAXN + 1];
	int roots[MAXN + 2];
 
	void add(int x, int y) { data[x].insert(y); }
 
	void build() {
		FOR(i, 1, MAXN + 1) {
			roots[i + 1] = roots[i];
			for (int j : data[i]) update(j, roots[i + 1]);
		}
	}
 
	void update(int pos, int &node, int l = 1, int r = MAXN) {
		segtree[cnt] = segtree[node] + 1;
		left_c[cnt] = left_c[node];
		right_c[cnt] = right_c[node];
		node = cnt++;
 
		if (l == r) return;
		int mid = (l + r) / 2;
		if (pos > mid) update(pos, right_c[node], mid + 1, r);
		else update(pos, left_c[node], l, mid);
	}
 
	int query(int l1, int r1, int l2, int r2) {
		if (l2 > r2) return 0;
		return query(l2, r2, roots[r1 + 1], 1, MAXN) -
		       query(l2, r2, roots[l1], 1, MAXN);
	}
	int query(int a, int b, int node, int l, int r) {
		if (a > r || b < l) return 0;
		if (a <= l && b >= r) return segtree[node];
		int mid = (l + r) / 2;
		return query(a, b, left_c[node], l, mid) +
		       query(a, b, right_c[node], mid + 1, r);
	}
} vertices, edges_horiz, edges_vert, rivers;
 
int mx_r, mn_r, mx_c, mn_c;
 
void add_river(int x, int y) {
	vertices.add(x, y);
	vertices.add(x + 1, y);
	vertices.add(x, y + 1);
	vertices.add(x + 1, y + 1);
	edges_horiz.add(x, y);
	edges_horiz.add(x + 1, y);
	edges_vert.add(x, y);
	edges_vert.add(x, y + 1);
	rivers.add(x, y);
}
 
void init(int R, int C, int sr, int sc, int M, char *S) {
	add_river(sr, sc);
	mx_r = mn_r = sr;
	mx_c = mn_c = sc;
	FOR(i, 0, M) {
		if (S[i] == 'N') sr--;
		if (S[i] == 'E') sc++;
		if (S[i] == 'S') sr++;
		if (S[i] == 'W') sc--;
		add_river(sr, sc);
		mx_r = max(mx_r, sr);
		mn_r = min(mn_r, sr);
		mx_c = max(mx_c, sc);
		mn_c = min(mn_c, sc);
	}
	vertices.build();
	edges_horiz.build();
	edges_vert.build();
	rivers.build();
}
 
int colour(int ar, int ac, int br, int bc) {
	int E =
	    edges_horiz.query(ar + 1, br, ac, bc) + edges_vert.query(ar, br, ac + 1, bc);
	int V = vertices.query(ar + 1, br, ac + 1, bc);
	int R = rivers.query(ar, br, ac, bc);
	int C = (ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c ? 1 : 2);
	return E - V + C - R;
}
Fundamentos