직사각형 영역 합
실버 III의견: 0
\(N \times M\) 크기의 격자가 주어진다. \(i\)행 \(j\)열 칸에는 정수 \(a_{i,j}\)가 적혀 있다. 이어서 \(Q\)개의 질문이 주어진다. 각 질문은 네 정수 \(r_1, c_1, r_2, c_2\)로 이루어지며, 왼쪽 위가 \((r_1, c_1)\)이고 오른쪽 아래가 \((r_2, c_2)\)인 직사각형 영역 안의 모든 수의 합을 묻는다 (\(r_1 \le r_2\), \(c_1 \le c_2\)).
질문이 많으므로 매번 직사각형을 직접 더하는 방법으로는 시간 안에 답할 수 없다.
\(1 \le N, M \le 1\,000\), \(N \times M \le 1\,000\,000\), \(1 \le Q \le 100\,000\), \(0 \le a_{i,j} \le 1\,000\)
첫째 줄에 격자의 행 수 \(N\)과 열 수 \(M\)이 주어진다. 다음 \(N\)개의 줄에 각각 \(M\)개의 정수가 주어진다. 그 다음 줄에 질문의 수 \(Q\)가 주어지고, 다음 \(Q\)개의 줄에 각각 네 정수 \(r_1, c_1, r_2, c_2\)가 주어진다.
각 질문에 대해 해당 직사각형 영역 안의 수들의 합을 한 줄에 하나씩 출력한다.
2 3
1 2 3
4 5 6
2
1 1 2 3
2 2 2 3
21
11전체 합은 \(1+2+3+4+5+6=21\)이고, \((2,2)\)~\((2,3)\) 영역은 \(5+6=11\)이다.
1 1
7
1
1 1 1 1
7한 칸짜리 영역의 합은 그 칸의 값 \(7\)이다.
실버 I막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
직사각형 영역 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
직사각형 영역 합