Maximum Building II

Explicación

Sea $r_{i,j}$ el número máximo de celdas libres continuas en la fila $i$ empezando desde $(i, j)$ hacia la derecha. Esto se puede precomputar. De forma similar a Maximum Building I , también podemos aplicar pilas monótonas para hallar

$u_{i, j}$ , la última fila por encima de $i$ con celda $(x, j)$ tal que $r_{x, j} > r_{i, j}$
$d_{i, j}$ , la última fila por debajo de $i$ con celda $(y, j)$ tal que $r_{y, j} \ge r_{i, j}$

Podemos actualizar de forma eficiente la matriz de respuesta con sumas de prefijos y arreglos de diferencias . Teniendo $r_{i,j}$ , $u_{i,j}$ y $d_{i,j}$ precomputados, conocemos la cota superior y la cota inferior del rectángulo de ancho $r_{i,j}$ , es decir, cuánto puede expandirse por encima y por debajo de la fila $i$ manteniendo el ancho $r_{i, j}$ .

Haremos arreglos de diferencias en cada columna de forma independiente. En consecuencia, las actualizaciones de la matriz de respuesta se ven así:

incrementar $\texttt{ans}[1][r_{i,j}]$ en $1$
decrementar $\texttt{ans}[i - u_{i, j} + 2][r_{i,j}]$ en $1$
decrementar $\texttt{ans}[d_{i,j} - i + 2][r_{i, j}]$ en $1$
incrementar $\texttt{ans}[d_{i,j} - u_{i,j} + 3][r_{i,j}]$ en $1$

Finalmente, sumamos $ans[i][j]$ a $ans[i][j-1]$ , es decir, una submatriz de tamaño $i \times j$ contiene una submatriz de tamaño $i \times (j-1)$ .

Implementación

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

C++Python


#include <iostream>
#include <stack>
#include <vector>
 
using namespace std;
 
int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> r(n + 2, vector<int>(m + 2));
	vector<vector<int>> u(n + 1, vector<int>(m + 1));
	vector<vector<int>> d(n + 1, vector<int>(m + 1));
	vector<vector<int>> ans(n + 3, vector<int>(m + 3));
	vector<vector<char>> mat(n + 1, vector<char>(m + 1));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) { cin >> mat[i][j]; }
		for (int j = m; j >= 1; j--) {
			if (mat[i][j] == '*') {
				r[i][j] = 0;
			} else {
				r[i][j] = r[i][j + 1] + 1;
			}
		}
	}
 
	stack<int> st;
	// Precomputar u[i][j] y d[i][j]
	for (int j = 1; j <= m; j++) {
		while (!st.empty()) { st.pop(); }
		for (int i = 1; i <= n; i++) {
			while (!st.empty() && r[i][j] < r[st.top()][j]) { st.pop(); }
			u[i][j] = st.empty() ? 1 : (st.top() + 1);
			st.push(i);
		}
		while (!st.empty()) { st.pop(); }
		for (int i = n; i >= 1; i--) {
			while (!st.empty() && r[i][j] <= r[st.top()][j]) { st.pop(); }
			d[i][j] = st.empty() ? n : (st.top() - 1);
			st.push(i);
		}
	}
 
	// Hacer arreglo de diferencias en cada columna de forma independiente
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans[1][r[i][j]]++;
			ans[i - u[i][j] + 2][r[i][j]]--;
			ans[d[i][j] - i + 2][r[i][j]]--;
			ans[d[i][j] - u[i][j] + 3][r[i][j]]++;
		}
	}
	for (int j = 1; j <= m; j++) {
		for (int i = 1; i <= n; ++i) { ans[i][j] += ans[i - 1][j]; }
		for (int i = 1; i <= n; ++i) { ans[i][j] += ans[i - 1][j]; }
	}
	for (int i = n; i >= 1; i--) {
		for (int j = m; j >= 2; --j) { ans[i][j - 1] += ans[i][j]; }
	}
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; ++j) { cout << ans[i][j] << " "; }
		cout << '\n';
	}
}


n, m = map(int, input().split())
 
r = [[0] * (m + 2) for _ in range(n + 2)]
u = [[0] * (m + 1) for _ in range(n + 1)]
d = [[0] * (m + 1) for _ in range(n + 1)]
ans = [[0] * (m + 3) for _ in range(n + 3)]
mat = [[""] * (m + 1) for _ in range(n + 1)]
 
for i in range(1, n + 1):
	row = input().strip()
	for j in range(1, m + 1):
		mat[i][j] = row[j - 1]
 
for i in range(1, n + 1):
	for j in range(m, 0, -1):
		if mat[i][j] == "*":
			r[i][j] = 0
		else:
			r[i][j] = r[i][j + 1] + 1
 
# Precomputar u[i][j] y d[i][j]
for j in range(1, m + 1):
	st = []
	for i in range(1, n + 1):
		while st and r[i][j] < r[st[-1]][j]:
			st.pop()
		u[i][j] = 1 if not st else st[-1] + 1
		st.append(i)
 
	st.clear()
	for i in range(n, 0, -1):
		while st and r[i][j] <= r[st[-1]][j]:
			st.pop()
		d[i][j] = n if not st else st[-1] - 1
		st.append(i)
 
# Hacer arreglo de diferencias en cada columna de forma independiente
for i in range(1, n + 1):
	for j in range(1, m + 1):
		ans[1][r[i][j]] += 1
		ans[i - u[i][j] + 2][r[i][j]] -= 1
		ans[d[i][j] - i + 2][r[i][j]] -= 1
		ans[d[i][j] - u[i][j] + 3][r[i][j]] += 1
 
for j in range(1, m + 1):
	for i in range(1, n + 1):
		ans[i][j] += ans[i - 1][j]
	for i in range(1, n + 1):
		ans[i][j] += ans[i - 1][j]
 
for i in range(n, 0, -1):
	for j in range(m, 1, -1):
		ans[i][j - 1] += ans[i][j]
 
for i in range(1, n + 1):
	print(" ".join(map(str, ans[i][1 : m + 1])))