Skip to Content
CTRL K

Nuske vs Phantom Thnook

Explicación

Nuestro enfoque es hacer sumas de prefijos 2D, donde el arreglo de sumas de prefijos calcula cuántas componentes conexas hay de (0, 0) a (x, y). Sin embargo, no es claro cuál es la función de transición. Por ejemplo, si nuestra grilla se ve así,

01
11

prefix0,1=1\texttt{prefix}_{0, 1} = 1 porque hay una componente conexa en la primera fila, y prefix1,0=1\texttt{prefix}_{1, 0} = 1 porque hay una componente conexa en la primera columna. Sin embargo, prefix1,1=1\texttt{prefix}_{1, 1} = 1 también porque estas dos componentes conexas se fusionan.

La clave para hallar la función de transición es la frase “for every pair of two blue square aa and bb, there is at most one path that starts from aa, repeatedly proceeds to an adjacent (side by side) blue square and finally reaches bb, without traversing the same square more than once.”

Esto significa que si dos regiones conexas separadas se unen en un punto, no pueden unirse en ningún otro lugar. Por ejemplo, abajo, dos componentes conexas separadas (A y B) se unen en la esquina inferior derecha (*), así que no pueden tocarse en ningún otro lado.

01101     0AA0A
00101     00A0A
00111     00AAA
10001     B000A
11111     BBBB*

Con esto en mente, podemos hacer análisis por casos. Digamos que buscamos prefix[i][j]\texttt{prefix[i][j]}.

Caso 1: gridi,j=gridi−1,j=gridi,j−1=1\texttt{grid}_{i, j} = \texttt{grid}_{i - 1, j} = \texttt{grid}_{i, j - 1} = 1

? 1
1 1

Llamamos AA a gridi−1,j\texttt{grid}_{i - 1, j} y BB a gridi,j−1\texttt{grid}_{i, j - 1}.

? A
B 1

Antes de agregar gridi,j\texttt{grid}_{i, j}, AA y BB debían pertenecer a componentes conexas separadas, porque si no, tendrían que estar conectadas en otro lugar, lo que viola el enunciado. Por lo tanto, fusionamos dos componentes conexas en una. En este caso, tenemos prefi,j=prefi−1,j+prefi,j−1−prefi−1,j−1−1\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1} - 1.

Caso 2: gridi,j=1\texttt{grid}_{i, j} = 1, gridi−1,j=gridi,j−1=0\texttt{grid}_{i - 1, j} = \texttt{grid}_{i, j - 1} = 0

? 0
0 1

¡Agregamos una nueva componente conexa! En este caso, tenemos prefi,j=prefi−1,j+prefi,j−1−prefi−1,j−1+1\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1} + 1.

Caso 3: Todos los demás casos en los que gridi,j=1\texttt{grid}_{i, j} = 1

? 1
0 1

O,

? 0
1 1

Agregamos a una componente conexa previa, así que tenemos prefi,j=prefi−1,j+prefi,j−1−prefi−1,j−1\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1}.

Caso 4: gridi,j=0\texttt{grid}_{i, j} = 0 Al introducir gridi,j\texttt{grid}_{i, j} no se puede crear una componente conexa nueva, y no se pueden fusionar dos componentes. Por lo tanto, en este caso, simplemente tenemos

prefi,j=prefi−1,j+prefi,j−1−prefi−1,j−1\texttt{pref}_{i, j} = \texttt{pref}_{i - 1, j} + \texttt{pref}_{i, j - 1} - \texttt{pref}_{i - 1, j - 1}

¡En este punto ya estamos más que a mitad de camino! Sin embargo, con esto solo podemos calcular el cambio en la cantidad de componentes conexas en un cierto rango. ¡Todavía hay que hallar con cuántas componentes conexas empezamos!

Para esto, calculamos cuántas componentes conexas hay en la fila superior y en la columna más a la izquierda del rango que estamos buscando. Podemos usar la misma idea, otra vez con sumas de prefijos.

Ver la implementación para más detalles.

Implementación

Complejidad temporal: O(NM+q)\mathcal{O}(NM + q)

Como hacemos sumas de prefijos 2D, por conveniencia, la grilla se traslada 1 unidad a la derecha y hacia abajo. La fila extra de arriba y la columna de la izquierda se llenan con 0.

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_SIZE = 2e3;
 
int main() {
	int n, m, q;
	cin >> n >> m >> q;
 
	/*
	 * Los siguientes 4 bucles se pueden combinar en un solo for, pero para
	 * facilitar la comprensión los separamos.
	 * Lectura de la grilla:
	 */
	vector<bitset<MAX_SIZE + 1>> grid(MAX_SIZE + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char a;
			cin >> a;
			grid[i][j] = (a == '1');
		}
	}
 
	// Arreglo general de sumas de prefijos. pref[x][y] es cuántas componentes
	// hay en el arreglo 2D de (1, 1) a (x, y), inclusive.
	vector<vector<int>> pref(MAX_SIZE + 1, vector<int>(MAX_SIZE + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
			if (grid[i][j]) {
				if ((!grid[i - 1][j]) && (!grid[i][j - 1])) {
					/*
					 *   0
					 * 0 1
					 * ¡Se forma una nueva componente conexa!
					 */
					pref[i][j]++;
				}
				if ((grid[i - 1][j]) && (grid[i][j - 1])) {
					/*
					 *   1
					 * 1 1
					 * ¡Se fusionan dos componentes conexas!
					 */
					pref[i][j]--;
				}
			}
		}
	}
 
	// horpref[x][y] es cuántas componentes conexas hay en la fila
	// de (x, 1) a (x, y), inclusive.
	vector<vector<int>> horpref(MAX_SIZE + 1, vector<int>(MAX_SIZE + 1));
 
	// verpref[x][y] es cuántas componentes conexas hay en la columna
	// de (1, y) a (x, y), inclusive.
	vector<vector<int>> verpref(MAX_SIZE + 1, vector<int>(MAX_SIZE + 1));
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			horpref[i][j] = horpref[i][j - 1];
			verpref[i][j] = verpref[i - 1][j];
			if (grid[i][j]) {
				horpref[i][j] += !grid[i][j - 1];
				verpref[i][j] += !grid[i - 1][j];
			}
		}
	}
 
	for (int i = 0; i < q; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
 
		int ans = grid[a][b];  // Si empezamos con una componente conexa
 
		// Cuántas componentes nuevas aparecen en la fila superior y la columna izquierda
		ans += horpref[a][d] - horpref[a][b];
		ans += verpref[c][b] - verpref[a][b];
 
		// Cambio en la # de componentes conexas en el resto de la grilla
		ans += pref[c][d] - pref[a][d] - pref[c][b] + pref[a][b];
		cout << ans << endl;
	}
}
import java.io.*;
import java.util.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int rowNum = Integer.parseInt(initial.nextToken());
		int colNum = Integer.parseInt(initial.nextToken());
		int queryNum = Integer.parseInt(initial.nextToken());
 
		/*
		 * Los siguientes 4 bucles se pueden combinar en un solo for, pero para
		 * facilitar la comprensión los separamos.
		 * Lectura de la grilla:
		 */
		String[] grid = new String[rowNum + 1];
		grid[0] = "0".repeat(colNum + 1);
		for (int r = 0; r < rowNum; r++) {
			grid[r + 1] = "0" + read.readLine();
			assert grid[r].length() == colNum;
		}
 
		// Arreglo general de sumas de prefijos. pref[x][y] es cuántas componentes
		// hay en el arreglo 2D de (1, 1) a (x, y), inclusive.
		int[][] pref = new int[rowNum + 1][colNum + 1];
		for (int r = 1; r <= rowNum; r++) {
			for (int c = 1; c <= colNum; c++) {
				pref[r][c] = pref[r - 1][c] + pref[r][c - 1] - pref[r - 1][c - 1];
				if (grid[r].charAt(c) == '1') {
					boolean up = grid[r - 1].charAt(c) == '1';
					boolean left = grid[r].charAt(c - 1) == '1';
					if (!(up || left)) {
						/*
						 *   0
						 * 0 1
						 * ¡Se forma una nueva componente conexa!
						 */
						pref[r][c]++;
					}
					if (up && left) {
						/*
						 *   1
						 * 1 1
						 * ¡Se fusionan dos componentes conexas!
						 */
						pref[r][c]--;
					}
				}
			}
		}
 
		// horpref[x][y] es cuántas componentes conexas hay en la fila
		// de (x, 1) a (x, y), inclusive.
		int[][] horpref = new int[rowNum + 1][colNum + 1];
 
		// verpref[x][y] es cuántas componentes conexas hay en la columna
		// de (1, y) a (x, y), inclusive.
		int[][] verpref = new int[rowNum + 1][colNum + 1];
 
		for (int r = 1; r <= rowNum; r++) {
			for (int c = 1; c <= colNum; c++) {
				horpref[r][c] = horpref[r][c - 1];
				verpref[r][c] = verpref[r - 1][c];
				if (grid[r].charAt(c) == '1') {
					if (grid[r].charAt(c - 1) == '0') { horpref[r][c]++; }
					if (grid[r - 1].charAt(c) == '0') { verpref[r][c]++; }
				}
			}
		}
 
		StringBuilder queryAns = new StringBuilder();
		for (int q = 0; q < queryNum; q++) {
			StringTokenizer query = new StringTokenizer(read.readLine());
			int sr = Integer.parseInt(query.nextToken());
			int sc = Integer.parseInt(query.nextToken());
			int er = Integer.parseInt(query.nextToken());
			int ec = Integer.parseInt(query.nextToken());
 
			// Si empezamos con una componente conexa
			int corner = grid[sr].charAt(sc) == '1' ? 1 : 0;
 
			// Cuántas componentes nuevas aparecen en la fila superior y la columna izquierda
			int topRow = horpref[sr][ec] - horpref[sr][sc];
			int topCol = verpref[er][sc] - verpref[sr][sc];
 
			// Cambio en la # de componentes conexas en el resto de la grilla
			int change = pref[er][ec] - pref[sr][ec] - pref[er][sc] + pref[sr][sc];
 
			queryAns.append(corner + topRow + topCol + change).append('\n');
		}
 
		System.out.print(queryAns);
	}
}
MAX_SIZE = 2000
 
n, m, q = map(int, input().split())
 
grid = [[False] * (MAX_SIZE + 1) for _ in range(MAX_SIZE + 1)]
 
# Leemos la grilla
for i in range(1, n + 1):
	row = input()
	for j in range(1, m + 1):
		grid[i][j] = row[j - 1] == "1"
 
# Arreglo general de sumas de prefijos. pref[x][y] es cuántas componentes
# hay en el arreglo 2D de (1, 1) a (x, y), inclusive.
pref = [[0] * (MAX_SIZE + 1) for _ in range(MAX_SIZE + 1)]
 
for i in range(1, n + 1):
	for j in range(1, m + 1):
		pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1]
		if grid[i][j]:
			"""
			  0
			0 1
			¡Se forma una nueva componente conexa!
			"""
			if not grid[i - 1][j] and not grid[i][j - 1]:
				pref[i][j] += 1
 
			"""
              		  1
            		1 1
            		¡Se fusionan dos componentes conexas!
            		"""
			if grid[i - 1][j] and grid[i][j - 1]:
				pref[i][j] -= 1
 
# horpref[x][y]: cantidad de componentes conexas en la fila de (x, 1) a (x, y)
horpref = [[0] * (MAX_SIZE + 1) for _ in range(MAX_SIZE + 1)]
 
# verpref[x][y]: cantidad de componentes conexas en la columna de (1, y) a (x, y)
verpref = [[0] * (MAX_SIZE + 1) for _ in range(MAX_SIZE + 1)]
 
for i in range(1, n + 1):
	for j in range(1, m + 1):
		horpref[i][j] = horpref[i][j - 1]
		verpref[i][j] = verpref[i - 1][j]
		if grid[i][j]:
			horpref[i][j] += not grid[i][j - 1]
			verpref[i][j] += not grid[i - 1][j]
 
for _ in range(q):
	a, b, c, d = map(int, input().split())
 
	# Si empezamos con una componente conexa
	ans = grid[a][b]
 
	# Cuántas componentes nuevas aparecen en la fila superior y la columna izquierda
	ans += horpref[a][d] - horpref[a][b]
	ans += verpref[c][b] - verpref[a][b]
 
	# Cambio en la cantidad de componentes conexas en el resto de la grilla
	ans += pref[c][d] - pref[a][d] - pref[c][b] + pref[a][b]
 
	print(ans)
Fundamentos