백준 11012 - Egg
이번에 리뷰해볼 문제는 Egg입니다. 단계별로 풀어보기를 도장깨기처럼 정복해나가고 있는데, 어느덧 40단계를 넘어섰습니다. 이젠 하루에 한 문제 풀기도 벅차군요. 아무튼 시작해봅시다.
이 문제도 영어라서, 번역을 좀 해보죠.
상근이는 국민들의 열렬한 지지를 받는 대통령이다. 상근이가 행사에 참석할 때마다(대통령이 행사에 나가는 것 말고 무슨 일이 있겠는가) 그를 사랑해 마지않는 국민들은 그에게 달걀을 던지고(?), 상근이는 그 달걀들을 항상 잡아낸다. 사실 상근이는 이 순간을 무척이나 좋아하는데, 달걀을 너무나 사랑하기 때문이다(…?). 사람들은 상근이가 행사에 참석하여 그들의 집 앞에 올 때마다 달걀을 던져준다.
입력으로는 \(N\)개의 이차원 좌표들이 주어진다. 이들은 각 행사 때마다 달걀을 던지는 사람들이 살고있는 지점을 나타낸다. 여러 사람들이 한 곳에서 살고 있을 수 있고, 좌표는 중복될 수 있다. 또한 남은 \(M\)일의 임기동안 행사가 벌어지는 범위가 정해진다. 행사는 좌표축에 평행한 직사각형 영역에서 진행되며, 상근이는 헌법을 수호하는 일국의 대통령이므로 행사 일정을 모두 따라야만 한다. 행사의 범위는 이차원 좌표 상에서 \([l, r] \times [b, t]\)를 나타낸다.
스토리는 꽤 코믹하지만, 막상 풀기 위해서는 세그먼트 트리를 써야하는 어려운 문제입니다.
처음에는 어떻게 접근해야할지 좀 막막해서 구글에 문제를 검색해봤는데, 상단에 노출되는 결과들은 모두 Persistent Segment Tree를 쓰는 풀이밖에 없더군요. 단계별로 풀어보기에선 분명 이 자료구조는 필요 없다고 했는데 말이죠. 그렇게 한참을 고민하다가 세그먼트 트리를 3개 써보면 되지 않을까 하는 생각에까지 미치게 되었습니다.
위에서부터 순서대로 문제를 풀기 때문에 이미 직사각형 문제를 풀고 난 후였는데요. 스위핑으로 선분의 총 길이를 계산하는 과정에서 길이를 저장하는 별도의 세그먼트 트리를 만들고 활용해야 했습니다. 이 세그먼트 트리는 직접 업데이트 되는 일은 없고, 선분이 추가되면 별도의 알고리즘을 통해 간접적으로 업데이트되며, 실제로 접근할 수 있는 건 루트 노드일 뿐이죠.
이걸 좀 응용해봅시다. 이번 문제에서는 업데이트되는 대상이 2개입니다. 선분과 점이죠. 이 두 세그먼트 트리 간의 계산을 통해 원하는 값을 얻어낼 수 있지 않을까요?
위 그림은 선분 범위를 세그먼트 트리에 저장한 모습입니다. 이진트리를 활용하므로 선분이 전체 좌표를 반으로 잘라 들어갔을 때의 영역을 완전히 포함했을 때에만 노드의 값을 갱신합니다. 세 선분이 모두 전체 좌표 상의 (0.25 ~ 0.5)를 덮고 있다면 이 영역을 나타내는 노드의 값은 3이 됩니다.
이번엔 각 영역 내에 점이 몇 개 있는지를 나타내는 세그먼트 트리입니다. 리프 노드는 특정 좌표에 중복되는 점이 몇 개 있는지를 나타내며, 그 위의 노드는 양 자식 노드의 값을 합한 값을 갖습니다. 그렇게 주욱 타고 올라가면 전체 범위 상 점이 몇 개 있는지 나타내게 됩니다.
이제 두 세그먼트 트리로부터 문제가 요구하는 값을 구해봅시다. 의외로 상당히 단순한데, 선분의 중첩은 행사가 진행되는 횟수를 나타내며, 점의 중첩은 각 지점에 사는 사람의 수를 나타냅니다. 사람들은 행사 때마다 달걀을 던지므로 어떤 지점에서 던지는 달걀의 개수는 중첩된 선분 개수와 점의 개수를 곱한 값과 같습니다.
비약이 심한 그림이긴 하지만, 뜻이 전달되면 좋겠군요. 아무튼, 선분과 점을 따로 갱신하면서도 달걀의 총 개수는 \(O(1)\)만에 구할 수 있게 되었습니다.
공간복잡도는 생각할 것도 없습니다. 세그먼트 트리 3개를 쓸 뿐이므로 유의미하게 많은 공간을 쓰진 않으니까요. 시간복잡도는 어떻게 될까요. 직사각형의 중첩된 넓이를 구할 때의 쿼리의 수는 윗선분, 아랫선분 2개씩 모든 직사각형의 넓이에 대해 진행합니다. 점의 개수 업데이트는 특정 y좌표 상에서 추가해준 다음 바로 다음 좌표에서 제거해야 하므로 또한 2번씩 진행합니다. 선분과 점의 업데이트는 따로 진행되며 서로 독립이므로 쿼리의 수는 \(N + M\)이 되겠군요. 또한 각 쿼리마다 세그먼트 트리의 업데이트가 필요하므로 \(O(\log MAX)\)의 시간이 소요됩니다. 총 시간복잡도는 \(O((N + M)\log MAX)\)입니다. 이 정도면 통과는 무리 없어보입니다.
남은 것은 구현 뿐입니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
typedef long long int ll;
const int MAX = 100'000;
struct Vertex { int x1, x2, y, diff; };
bool CompY(Vertex& a, Vertex& b) { return a.y < b.y; }
struct Pos { int x, y; };
bool CompPosY(Pos& a, Pos& b) { return a.y < b.y; }
int N, M;
std::vector<Vertex> v;
std::vector<Pos> p;
ll seg_range[MAX * 4]; // 퍼레이드 선분의 누적 범위 조회
ll seg_pos[MAX * 4]; // 달걀을 던지는 사람들의 수 조회
ll seg_count[MAX * 4]; // (선분 누적 범위) * (범위 내 사람들의 수)
void update_range(int left, int right, ll diff, int index = 1, int start = 0, int end = MAX) {
if (left > end || right < start) return;
if (left <= start && end <= right) {
seg_range[index] += diff;
}
else {
int mid = (start + end) >> 1;
update_range(left, right, diff, index << 1, start, mid);
update_range(left, right, diff, (index << 1) + 1, mid + 1, end);
}
// 선분이 추가되거나 제거될 때마다 개수를 업데이트합니다.
seg_count[index] = seg_count[index << 1] + seg_count[(index << 1) + 1] + seg_pos[index] * seg_range[index];
}
void update_pos(int pos, ll diff, int index = 1, int start = 0, int end = MAX) {
if (pos > end || pos < start) return;
seg_pos[index] += diff;
if (start == end) { // 이 부분은 개선의 여지가 있어 보입니다만, 어떻게 고칠지는 잘 모르겠군요.
seg_count[index] = seg_pos[index] * seg_range[index];
return;
}
int mid = (start + end) >> 1;
update_pos(pos, diff, index << 1, start, mid);
update_pos(pos, diff, (index << 1) + 1, mid + 1, end);
// 점이 추가되거나 제거될 때마다 개수를 업데이트합니다.
seg_count[index] = seg_count[index << 1] + seg_count[(index << 1) + 1] + seg_pos[index] * seg_range[index];
}
ll get_count() { return seg_count[1]; } // O(1)
int main() {
int T;
std::cin >> T;
while (T--) {
memset(seg_range, 0, sizeof seg_range);
memset(seg_count, 0, sizeof seg_count);
memset(seg_pos, 0, sizeof seg_pos);
v.clear();
p.clear();
ll total = 0;
std::cin >> N >> M;
for (int i = 0; i < N; ++i) {
int x, y;
std::cin >> x >> y;
p.push_back({ x, y }); // 전체 범위가 좁은 편이므로 따로 좌표 압축은 하지 않습니다.
}
for (int i = 0; i < M; ++i) {
int x1, x2, y1, y2;
std::cin >> x1 >> x2 >> y1 >> y2; // l, r, b, t
v.push_back({ x1, x2, y1, 1 });
v.push_back({ x1, x2, y2 + 1, -1 }); // 직사각형 범위가 제거되는 시점은 (t + 1)이 되어야 합니다.
}
std::sort(p.begin(), p.end(), CompPosY);
std::sort(v.begin(), v.end(), CompY);
std::vector<int> stack;
for (int y = 0, i = 0, j = 0; y <= MAX; ++y) { // x축과 평행한 모든 선에 대해 검사합니다.
while (!stack.empty()) update_pos(stack.back(), -1), stack.pop_back(); // 점 제거
while (i < v.size() && v[i].y == y) { // 선분 추가 및 제거
update_range(v[i].x1, v[i].x2, v[i].diff);
i++;
}
while (j < p.size() && p[j].y == y) { // 점 추가
update_pos(p[j].x, 1);
stack.push_back(p[j].x); // 점은 추가된 직후 제거되어야 합니다.
j++;
}
total += get_count(); // 실제 값을 추가하는 부분
if (i == v.size() && j == p.size()) break; // 모든 쿼리를 수행했다면 빠져나갑니다.
}
std::cout << total << '\n';
}
}