어렵지 않게, (4, 4)부터 (4, 4)까지의 합을 구하면 1이다.
입력
표준입력으로 입력이 주어진다. 첫 줄에는 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. N은 1 이상 1024 이하, M은 1 이상 100,000 이하이다. 그 다음 N 줄에는 표에 대한 정보가 주어진다. 한 줄에는 N개의 숫자가 사이에 공백을 두고 주어진다. 이 수들은 모두 1 이상 1,000 이하인 정수이다. 그 다음 M개의 줄에는 각각의 줄마다 a b c d 4개의 정수가 주어지는데, 이들은 모두 1 이상 N 이하이며, a는 c 이하, b는 d 이하이다. 이는 (a, b)부터 (c, d)까지의 직사각형 부분에 대한 합을 구하라는 것이다.
출력
입력에서 각 줄에 주어진 a b c d마다 해당하는 합을 한 줄에 출력한다. 따라서 답은 총 M줄이다.
제출
하나의 .c/.cpp/.java 파일을 제출한다.
예제 입력
4 2
0 1 0 1
1 1 0 1
1 0 1 0
1 1 2 1
2 2 3 4
4 4 4 4
예제 출력
3
1
2차원 부분합 문제이다. 세그먼트트리로 풀었다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class SegmentTree {
private:
vector<long long> Nodes;
vector<long long> input;
long long init(int index, int start, int end) {
if (start == end) {
Nodes[index] = input[start];
}
else {
Nodes[index] = init(index * 2 + 1, start, (start + end) / 2) + init(index * 2 + 2, (start + end) / 2 + 1, end);
}
return Nodes[index];
}
public:
SegmentTree(int N, vector<long long> input) {
int height = (int)ceil(log2(N));
int tree_size = (1 << (height + 1));
Nodes.resize(tree_size+1,0);
this->input = input;
init(0, 0, N - 1);
}
long long sum(int index, int start, int end, int left, int right) {
if (start > right || end < left)
return 0;
else if (start >= left && end <= right)
return Nodes[index];
else {
int middle = (start + end) / 2;
return sum(2 * index + 1, start, middle, left, right) + sum(2 * index + 2, middle + 1, end, left, right);
}
}
void update(int changed_index, long long diff, int index, int start, int end)
{
if (changed_index < start || changed_index > end)
return;
Nodes[index] += diff;
if (start != end) {
int mid = (start + end) / 2;
update(changed_index, diff, index * 2 + 1, start, mid);
update(changed_index, diff, index * 2 + 2, mid + 1, end);
}
}
};
int main() {
ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
int N, M;
cin >> N >> M;
vector<vector<long long>> input(N+1);
vector<SegmentTree> arr;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
input[i].push_back(0);
}
}
for (int i = N-1; i >= 0; i--) {
for (int j = 0; j < N; j++) {
int tmp;
cin >> tmp;
input[i][j] = tmp;
}
}
for (int i = 0; i < N; i++) {
SegmentTree tmp = SegmentTree(N, input[i]);
arr.push_back(tmp);
}
for (int i = 0; i < M; i++) {
int a, b, c, d;
long long ans = 0;
cin >> a >> b >> c >> d;
int ymax = max(b, d)-1;
int ymin = min(b, d)-1;
int xmax = max(a, c)-1;
int xmin = min(a, c)-1;
for (int j = ymin; j <= ymax; j++) {
ans += arr[j].sum(0, 0, N - 1, xmin, xmax);
}
cout << ans << endl;
}
return 0;
}
'vidigummy KAU > 2021 문제해결기법' 카테고리의 다른 글
문해기 과제 4 (0) | 2021.06.29 |
---|---|
문해기 과제 3 (0) | 2021.06.29 |
문해기 2번 과제 (0) | 2021.06.29 |