테스트케이스의 수 가 주어지고, 매 테스트케이스마다 첫 줄에는 이 주어진다. 은 국민의 집 좌표의 개수, 은 퍼레이드가 열리는 횟수다.
이후 개의 줄에는 국민들의 집의 좌표가 주어진다. 국민들은 자신의 집에 퍼레이드가 도착할 때마다 계란을 던진다. 그 아래 개의 줄에는 퍼레이드가 일어나는 영역 에 해당하는 가 주어진다.
일 동안 맞게 될 계란 수의 총합은 어떻게 될까?
인터넷에서 찾을 수 있는 대부분의 풀이에서는 PST(Persistent Segment Tree)라는 자료구조를 사용해 이 문제를 풀고 있지만, 사실 지연 전파와 스위핑만으로도 풀 수 있다. 다음과 같은 예를 생각해보자. 푸르게 색칠된 부분이 퍼레이드가 일어나는 영역이고, 빨간 점들은 국민의 집들이라 하자.
1, 4, 5번은 한 번씩 카운트가 되고 2, 3번은 두 번씩 카운트가 되어, 정답은 7이 되어야 한다. 각 점이 몇 번 카운트되어야 하는지만 알 수 있으면 문제를 풀 수 있다.
각 영역마다 카운트되는 횟수는 위와 같다. y좌표들을 관리하는 세그먼트 트리를 만들고, x축 방향으로 0에서 100000으로 가보자. 왼쪽 변을 만날 때마다 [b, t]
에 +1을 해주고, 오른쪽 변을 만날 때마다 [b,t]
에 -1을 해주면 각 점마다 몇 번 카운트를 해줘야 하는지 쉽게 알아낼 수 있다.
각 국민들의 집은 x축 방향으로 0에서 100000로 가면서, 해당 x좌표 위의 집들에 대해, 해당 집의 y 좌표에 대한 쿼리를 날려봄으로써 카운트할 수 있다.
[b, t]
구간에 +1을 해준다.[b, t]
구간에 -1을 해준다.구간 갱신이 잦은 문제이므로, 세그먼트 트리의 지연 전파를 이용하면 된다.
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1e5;
vector<int> tree, lazy;
void propagate(int node, int start, int end) {
if (lazy[node]) {
tree[node] += lazy[node];
if (start != end) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
}
void update(int node, int start, int end, int left, int right, int val){
propagate(node, start, end);
if (right < start || end < left) return;
if (left <= start && end <= right) {
lazy[node] += val;
propagate(node, start, end);
return;
}
int mid = (start + end) / 2;
update(node * 2, start, mid, left, right, val);
update(node * 2 + 1, mid + 1, end, left, right, val);
}
void update(int left, int right, int val){
update(1, 0, MAX, left, right, val);
}
int query(int node, int start, int end, int left, int right){
propagate(node, start, end);
if (right < start || end < left) return 0;
if (left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
return query(node * 2, start, mid, left, right)
+ query(node * 2 + 1, mid + 1, end, left, right);
}
int query(int left, int right) {
return query(1, 0, MAX, left, right);
}
int main(){
int T;
scanf("%d", &T);
while (T--) {
vector<int> eggs[MAX + 1];//egg[x]에는 해당 x좌표에 있는 집의 y좌표가 들어간다.
vector<pair<int, int>> v_open[MAX + 1], v_close[MAX + 1];//v_open[x]는 해당 x좌표에 있는 왼쪽변의 b, t, v_close[x]에는 해당 x좌표에 있는 오른쪽 변의 b, t 쌍이 들어간다.
tree.clear();
lazy.clear();
tree.resize((MAX+ 1) * 4);
lazy.resize((MAX+ 1) * 4);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
int x, y;
scanf("%d%d", &x, &y);
eggs[x].push_back(y);
}
for (int i = 0; i < m; i++) {
int l, r, b, t;
scanf("%d%d%d%d", &l, &r, &b, &t);
v_open[l].emplace_back(b, t);
v_close[r].emplace_back(b, t);
}
int ans = 0;
//x축 방향으로, 0에서 100000으로 가면서
for (int i = 0; i <= MAX; i++) {
//왼쪽 변이 있으면 해당 구간에 +1을 해준다.
for (auto open : v_open[i]) {
update(open.first, open.second, 1);
}
//집이 있으면 해당 집의 y좌표를 카운트해야 할 횟수를 더해준다.
for (int egg: eggs[i]) {
ans += query(egg, egg);
}
//왼쪽 변이 있으면 해당 구간에 -1을 해준다.
for (auto close : v_close[i]) {
update(close.first, close.second, -1);
}
}
printf("%d\n", ans);
}
}
문제를 많이 틀렸는데, 로직 상 틀린 점을 계속 못 찾았다.
틀린 이유는 마지막 줄에 줄바꿈을 안 해줘서였다. 출력할 때도 조심해서 문제를 풀자.