ssdj

Análisis oficial (en rumano) 

Explicación

Empecemos por un caso más simple, cuando la grilla solo contiene las letras a y b. Asociemos a cada letra un valor correspondiente a su posición en el alfabeto (por ahora, a vale $0$ y b vale $1$). Ahora tendremos que hallar la cantidad de submatrices tales que en las esquinas superior izquierda e inferior derecha tenemos $1$ y tenemos $0$ en todos los demás lugares.

Construyamos otra grilla de tamaño $n \times n$ donde $b(i, j)$ guarda la cantidad de $0$ consecutivos en la columna $j$ por encima de la posición $(i, j)$.

Ahora, para cada fila de $2$ a $n$, para una posición dada $(i, j)$ que es igual a $1$ (consideraremos esta la esquina inferior derecha), nos moveremos de derecha a izquierda en esa fila para hallar los valores iguales a $1$ ubicados en coordenadas $(i, k)$ donde $k < j$ tales que $b(i, k) > 0$ y $b(i, k)$ es estrictamente menor que todos los valores $b(i, p)$ con $p$ entre $k+1$ y $j$.

La complejidad de este enfoque es $\mathcal{O}(n^2)$.

Ahora necesitamos generalizar para toda la grilla, que tiene todas las letras minúsculas del alfabeto. En cada paso, fijamos una letra, llamémosla $ch$.

Para esa letra, crearemos ahora una grilla donde las posiciones correspondientes a todas las letras que son menores que $ch$ serán iguales a $0$, todas las letras iguales a $ch$ serán iguales a $1$ y todas las letras mayores que $ch$ serán iguales a $2$.

Al igual que hicimos para la grilla binaria, contaremos cuántas submatrices tienen valores iguales a $0$ excepto por las dos esquinas mencionadas. Para evitar el sobreconteo, solo contaremos las submatrices tales que contienen $1$ en al menos una esquina. Ahora, cuando procesamos una posición $(i, j)$ haremos lo siguiente: si en esa posición tenemos $1$, contaremos la cantidad de posiciones previas que corresponden tanto a $1$ como a $2$, y si en la misma posición tenemos $2$, solo contaremos las posiciones previas que son iguales a $1$.

La complejidad de este enfoque sigue siendo $\mathcal{O}(n^2)$ por cada letra, lo que nos da una complejidad total de $\mathcal{O}(sigma \times n^2)$, donde $sigma = 26$ es la longitud del alfabeto.

Para otros enfoques, también se pueden consultar las soluciones de usuarios en Infoarena ; solo hay que pulsar el popup que aparece después de hacer clic por primera vez en una solución.

Implementación

Complejidad temporal: $\mathcal{O}(26 \cdot N^2)$

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	ifstream f("ssdj.in");
 
	int n;
	f >> n;
 
	long long ans = 0;
	vector<vector<char>> mat(n + 1, vector<char>(n + 1));
	vector<vector<int>> lst(n + 2, vector<int>(n + 2));
	vector<vector<int>> lst2(n + 2, vector<int>(n + 2));
	vector<int> d(n + 2);
 
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) { f >> mat[i][j]; }
	}
	for (int i = 1; i <= n; i++) { lst2[n + 1][i] = n + 2; }
	for (char i = 'z'; i >= 'a'; i--) {
		for (int row = 1; row <= n; row++) {
			int stackSize = 0;
			for (int col = 1; col <= n; col++) {
				if (mat[row][col] >= i) {
					lst[row][col] = row;
				} else {
					lst[row][col] = lst[row - 1][col];
				}
				while (stackSize && lst[row - 1][col] >= lst[row][d[stackSize]]) {
					--stackSize;
				}
				if (mat[row][col] == i) {
					ans += stackSize;
					if (stackSize && d[1] == col) { --stackSize; }
				}
				while (stackSize && lst[row][col] >= lst[row][d[stackSize]]) {
					--stackSize;
				}
				if (lst[row][col] <= (row - 1) && lst[row][col] != 0) {
					d[++stackSize] = col;
				}
			}
		}
 
		for (int row = n; row >= 1; row--) {
			int stackSize = 0;
			int hm = 0;
			for (int col = n; col >= 1; col--) {
				if (mat[row][col] >= i) {
					lst2[row][col] = row;
				} else {
					lst2[row][col] = lst2[row + 1][col];
				}
				while (stackSize && lst2[row + 1][col] <= lst2[row][d[stackSize]]) {
					if (mat[lst2[row][d[stackSize]]][d[stackSize]] == i) { hm--; }
					stackSize--;
				}
				if (mat[row][col] == i) {
					ans += stackSize;
					ans -= hm;
					if (stackSize && d[stackSize] == col) { ans--; }
				}
				while (stackSize && lst2[row][col] <= lst2[row][d[stackSize]]) {
					if (mat[lst2[row][d[stackSize]]][d[stackSize]] == i) { hm--; }
					stackSize--;
				}
				if (lst2[row][col] >= (row + 1) && lst2[row][col] != (n + 2)) {
					if (mat[lst2[row][col]][col] == i) { hm++; }
					d[++stackSize] = col;
				}
			}
		}
	}
 
	ofstream("ssdj.out") << ans << endl;
}