Skip to Content
CTRL K

Rectangles

Explicación

Primero simplifiquemos este problema, y luego generalicemos la solución de ese problema a este.

Digamos que teníamos una matriz de solo 0 y 1. ¿Cuántas submatrices de solo 1 hay?

Definamos primero un arreglo 2D, \texttt{longest\\_consec}, que contiene el número de 1 consecutivos que están directamente a la derecha para cada celda (incluyendo la celda misma). Por ejemplo, esta matriz…

1011
0111
0001

tendría el siguiente \texttt{longest\\_consec}:

1021
0321
0001

Ahora, recorremos cada columna y luego cada fila en reversa, y hallamos para cada celda el número de submatrices de solo 1 donde la celda es la esquina superior izquierda.

¿Cómo haríamos esto?

Primero, inicialicemos una pila \texttt{rel\\_streaks} que tendrá elementos con dos propiedades: el valor de \texttt{longest\\_consec} para ese elemento y la diferencia en número de fila (o sea, la distancia) entre ese elemento y el siguiente elemento de la pila.

También inicializamos un número \texttt{curr\\_sum}, que, después de procesar, contendrá el número de submatrices de solo 1 que empiezan en cada celda.

Ahora, digamos que acabamos de empezar en una celda particular. ¿Cómo deberíamos cambiar nuestro valor de \texttt{curr\\_sum}? No consideremos primero las nuevas matrices de una fila que recién se agregaron, y consideremos solo los arreglos anteriores. Para poder extenderse a la celda actual, necesitan tener un ancho en columnas menor que el valor actual de \texttt{longest\\_consec}. Para restar estas submatrices recién inválidas, seguimos sacando de la pila mientras la primera parte del primer elemento es mayor que el ancho actual y ajustando el valor de \texttt{curr\\_sum} según corresponda.

Finalmente, para cada paso, solo hay que agregar el elemento actual a la pila y sumar a \texttt{curr\\_sum} el valor de \texttt{longest\\_consec} de esa celda.

Dado que resolvimos ese problema más simple, podemos aplicar esto al problema real. Hagamos una versión modificada de \texttt{longest\\_consec}, donde cada celda contiene el número de elementos consecutivos a la derecha con el mismo valor que la celda actual.

Después de eso, ejecutamos casi el mismo algoritmo, solo que ahora reseteamos todas las variables necesarias cuando encontramos un número distinto a los anteriores que estábamos procesando.

Implementación

Complejidad temporal: O(RC)\mathcal{O}(RC) para cada uno de TT casos de prueba

 
#include <algorithm>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::pair;
using std::vector;
 
int main() {
	// see /general/fast-io
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
 
	int test_num;
	std::cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int row_num;
		int col_num;
		std::cin >> row_num >> col_num;
		vector<vector<int>> grid(row_num, vector<int>(col_num));
		for (int r = 0; r < row_num; r++) {
			for (int c = 0; c < col_num; c++) { std::cin >> grid[r][c]; }
		}
 
		vector<vector<int>> longest_consec(row_num, vector<int>(col_num));
		for (int r = 0; r < row_num; r++) {
			int curr = -1;
			int streak = 0;
			for (int c = 0; c < col_num; c++) {
				if (grid[r][c] == curr) {
					streak++;
				} else {
					curr = grid[r][c];
					streak = 1;
				}
				longest_consec[r][c] = streak;
			}
		}
 
		long long total = 0;
		for (int c = 0; c < col_num; c++) {
			vector<pair<int, int>> rel_streaks;
			int curr_sum = 0;  // the current amt of valid submatrices
			int curr = grid[row_num - 1][c];
			// for each row in reverse, count # of valid submatrices that start
			// at that cell
			for (int r = row_num - 1; r >= 0; r--) {
				// if we encounter a diff number, just up & reset everything
				if (grid[r][c] != curr) {
					curr = grid[r][c];
					curr_sum = 0;
					rel_streaks = vector<pair<int, int>>();
				}
 
				/*
				 * the total # of elements that were killed
				 * between this element & the last one
				 */
				int popped = 0;
				// while this current row can possibly be a chokehold
				while (!rel_streaks.empty() &&
				       longest_consec[r][c] < rel_streaks.back().first) {
					// subtract the # of rectangles this chokehold made invalid
					curr_sum -= (rel_streaks.back().second + 1) *
					            (rel_streaks.back().first - longest_consec[r][c]);
					// add the number of kills this one got & kill this one
					// itself
					popped += rel_streaks.back().second + 1;
					rel_streaks.pop_back();
				}
				rel_streaks.push_back({longest_consec[r][c], popped});
				// add the submatrices of height 1
				curr_sum += longest_consec[r][c];
				total += curr_sum;
			}
		}
		cout << total << '\n';
	}
}
import java.io.*;
import java.util.*;
 
public class Rectangles {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer initial = new StringTokenizer(read.readLine());
			int rowNum = Integer.parseInt(initial.nextToken());
			int colNum = Integer.parseInt(initial.nextToken());
			int[][] grid = new int[rowNum][];
			for (int r = 0; r < rowNum; r++) {
				grid[r] = Arrays.stream(read.readLine().split(" "))
				              .mapToInt(Integer::parseInt)
				              .toArray();
			}
 
			int[][] longestConsec = new int[rowNum][colNum];
			for (int r = 0; r < rowNum; r++) {
				int curr = -1;
				int streak = 0;
				for (int c = colNum - 1; c >= 0; c--) {
					if (grid[r][c] == curr) {
						streak++;
					} else {
						curr = grid[r][c];
						streak = 1;
					}
					longestConsec[r][c] = streak;
				}
			}
 
			long total = 0;
			for (int c = 0; c < colNum; c++) {
				Stack<int[]> relStreaks = new Stack<>();
				int currSum = 0;  // the current amt of valid submatrices
				int curr = grid[rowNum - 1][c];
				/*
				 * for each row in reverse, count the # of valid submatrices
				 * that start at that cell
				 */
				for (int r = rowNum - 1; r >= 0; r--) {
					// if we encounter a diff number, just up & reset everything
					if (grid[r][c] != curr) {
						curr = grid[r][c];
						currSum = 0;
						relStreaks = new Stack<>();
					}
 
					/*
					 * the total # of elements that were killed
					 * between this element & the last one
					 */
					int popped = 0;
					// while this current row can possibly be a chokehold
					while (!relStreaks.isEmpty() &&
					       longestConsec[r][c] < relStreaks.peek()[0]) {
						// subtract the number of rectangles this chokehold made
						// invalid
						currSum -= (relStreaks.peek()[1] + 1) *
						           (relStreaks.peek()[0] - longestConsec[r][c]);
						// add the number of kills this one got & kill this one
						// itself
						popped += relStreaks.peek()[1] + 1;
						relStreaks.pop();
					}
					relStreaks.add(new int[] {longestConsec[r][c], popped});
					currSum += longestConsec[r][c];  // add the submatrices of height 1
					total += currSum;
				}
			}
			System.out.println(total);
		}
	}
}
Fundamentos