문제 30
사각형 칠하기
$H$개의 행과 $W$개의 열로 이루어진 격자가 있다.
처음에 모든 칸의 값은 $0$이다.
격자에 $N$개의 사각형을 그린 뒤 각 칸의 값을 출력하라.
좌표 $(x, y)$는 왼쪽에서 $x$번째 열이면서 위에서 $y$번째 행인 칸을 나타낸다.
사각형 $(x_1, y_1, x_2, y_2)$를 그리면 $x_1$열 이상 $x_2$열 이하이면서 $y_1$행 이상 $y_2$행 이하인 모든 칸의 값이 $1$씩 증가한다.
입력
첫 번째 줄에 세 정수 $H$, $W$, $N$이 공백으로 구분되어 주어진다. $(1 \le H, W \le 1\,000; 0 \le N \le 100\,000)$
두 번째 줄부터 $N$개의 줄에 걸쳐 네 정수 $x_1$, $y_1$, $x_2$, $y_2$가 공백으로 구분되어 주어진다. $(1 \le x_1 \le x_2 \le W; 1 \le y_1 \le y_2 \le H)$
출력
$H$개의 줄에 걸쳐 각 줄에 $W$개의 정수를 공백으로 구분하여 출력한다.
예제 입력 1
4 5 3 1 1 2 3 2 2 4 4 4 3 5 4
예제 출력 1
1 1 0 0 0 1 2 1 1 0 1 2 1 2 1 0 1 1 2 1
공식 해설
사각형 내부를 매번 칠하면 같은 칸을 지나치게 많이 방문한다. 이차원 차분 배열에 사각형의 시작과 끝만 기록한 뒤 한꺼번에 복원하자. 배열은 행, 열 순서로 접근한다.
사각형 $(x_1,y_1,x_2,y_2)$마다 다음 네 곳을 갱신한다.
\[
D_{y_1,x_1}\mathrel{+}=1,\qquad D_{y_1,x_2+1}\mathrel{-}=1,
\]
\[
D_{y_2+1,x_1}\mathrel{-}=1,\qquad D_{y_2+1,x_2+1}\mathrel{+}=1.
\]
이후 각 행을 왼쪽에서 오른쪽으로, 각 열을 위에서 아래로 누적한다. 가로 누적에서 $x_1$열부터 시작한 증가가 $x_2+1$열에서 멈추고, 세로 누적에서 $y_1$행부터 시작한 증가가 $y_2+1$행에서 멈춘다. 따라서 해당 사각형 안에만 $1$이 남는다.
모든 연산이 덧셈이므로 사각형들의 표식을 먼저 더한 뒤 누적해도 겹친 횟수가 정확히 복원된다. 배열에는 오른쪽과 아래쪽 경계 밖의 표식을 저장할 여유를 두고, 원래 $H\times W$ 범위만 출력한다.
시간복잡도는 $O(N+HW)$, 공간복잡도는 $O(HW)$이다.
구현 · 언어별 풀이
C++ 구현
표식을 위한 여유를 두어 $(H+2)\times(W+2)$ 크기의 배열을 $0$으로 초기화한다. vector<vector<int>>처럼 동적 저장 공간을 사용하면 큰 지역 배열을 호출 스택에 두지 않아도 된다. 좌표는 행 $y$, 열 $x$의 순서로 일관되게 접근한다.
C 구현
차분 배열을 calloc으로 할당하고 네 모서리에 부호를 반영한다. (H+2)*(W+2) 크기의 평탄 배열을 쓰면 경계 바깥 한 칸도 유효하다. 좌표 (x,y)는 행 y, 열 x에 대응한다.
Python 구현
행마다 array('i')를 두거나 평탄 정수 배열을 사용하면 격자의 객체 비용을 줄일 수 있다. 같은 행 리스트를 곱해서 복제하면 행들이 같은 객체를 공유하므로 피한다. 2차원 누적합 뒤 필요한 범위만 출력한다.
Java 구현
int[][] 차분 배열을 H+2, W+2 크기로 만든다. 겹친 횟수는 N 이하라 int로 충분하다. 행과 열 방향의 누적합을 적용하고, 큰 출력은 BufferedWriter로 행별 처리한다.
Rust 구현
평탄 Vec<i32>와 stride=W+2를 사용한다. 음수 차분 표시가 있으므로 u32로 두지 않는다. 인덱스는 y*stride+x이며, 경계 바깥 차분을 위한 행·열을 남긴다.
JavaScript 구현
차분 격자는 길이 (h + 2) * (w + 2)의 Int32Array 하나로 두고 위치를 y * stride + x로 계산하면 된다. 종료 표식이 원래 격자 밖 한 칸에 놓일 수 있으므로 여유 공간을 포함한다.
사각형은 행·열 순서에 맞춰 네 부호를 기록하고, 세로·가로 누적 뒤 원래 범위만 출력한다. 겹친 횟수는 최대 $N\le100\,000$이므로 32비트 정수로 충분하다. 행마다 답을 묶어 출력하고 입력 사각형마다 격자를 직접 순회하지 않는다.