BOJ 10548 BOB

각 칸에 대해서, 그 칸이 직사각형의 맨 오른쪽 아래 칸인 직사각형 중에서 모든 칸의 값이 같은 것의 개수를 세어 문제를 풀 수 있습니다. 이를 위해서는 다음의 정보가 필요합니다.

• left[r][c]: $r$행 $c$열에서부터 같은 값이 왼쪽으로 연속해서 몇 개 등장하는지 (자기자신 포함)
• up[r][c]: $r$행 $c$열에서부터 같은 값이 위쪽으로 연속해서 몇 개 등장하는지 (자기자신 포함)

이들을 계산해 놓고, 가로 방향으로 이동하면서 계산한다고 하면 다음의 관찰을 할 수 있습니다.

• left[r][c] = 1이면, 그 칸이 맨 오른쪽 아래인 직사각형의 개수는 up[r][c]와 같습니다.
• left[r][c] > 1이면, 그 칸이 맨 오른쪽 아래인 직사각형 중에서 가로로 $k$칸짜리인 것의 개수는 가능한 최대 높이와 같고, 이는 up[r][c-k+1..=c]의 구간 최솟값과 같습니다.

후자의 경우, left[r][c]개의 구간 최솟값을 나열하면 왼쪽에서 오른쪽 방향으로 단조 증가하므로, (서로 다른 최솟값, 그 최솟값의 개수)를 유지하는 모노톤 스택을 이용하여 모든 구간 최솟값의 합을 amortized $\mathcal{O}($ 같은 수가 나타나는 구간의 전체 길이 $)$에 구할 수 있습니다. 따라서 최종 알고리즘은 $\mathcal{O}(NM)$의 시간 복잡도를 갖습니다.