Time Limit: 2000 msMemory Limit: 256 MBSilver III4Author: 관리자
r1,c1,r2,c2
0≤r1≤r2≤R−1 0≤c1≤c2≤C−1 (r1,c1)부터 (r2,c2)까지의 직사각형 영역 2차원 누적합
Pi,j를 "왼쪽 위 (0,0)부터 (i−1,j−1)까지의 직사각형 합"이라 정의한다. 이를 점화식으로 계산하면:
Pi,j=Pi−1,j+Pi,j−1−Pi−1,j−1+Ai−1,j−1
겹치는 부분 Pi−1,j−1을 한 번 빼 줘야 한다 (포함-배제).
그러면 (r1,c1)부터 (r2,c2)까지 직사각형 합은:
rect_sum=Pr2+1,c2+1−Pr1,c2+1−Pr2+1,c1+Pr1,c1
제한
- 1≤R,C≤1000
- 1≤Q≤105
- −104≤Ai,j≤104
- 0≤r1≤r2≤R−1,
입출력 예시
입력 1
3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
0 0 0 0
0 0 2 3
1 1 2 2
출력 1
설명:
- 첫 질의: 한 칸 (0,0)만 → 1
- 두 번째: 전체 격자 → 1+2+⋯+12=78
- 세 번째: 부터 까지 →
입력 2
2 2 4
-1 2
3 -4
0 0 1 1
0 0 0 1
1 0 1 1
0 1 1 1
출력 2
2
0≤c1≤c2≤C−1
(1,1)
6+7+10+11=34