https://www.acmicpc.net/problem/11012
레벨: P2

[1] 문제 요약

테스트케이스의 수 $T$ 가 주어지고, 매 테스트케이스마다 첫 줄에는 $n, m$이 주어진다. $n$은 국민의 집 좌표의 개수, $m$은 퍼레이드가 열리는 횟수다.

이후 $n$개의 줄에는 국민들의 집의 좌표가 주어진다. 국민들은 자신의 집에 퍼레이드가 도착할 때마다 계란을 던진다. 그 아래 $m$개의 줄에는 퍼레이드가 일어나는 영역 $[l, r] \times [b, t]$에 해당하는 $l, r, b, t$가 주어진다.

$m$일 동안 맞게 될 계란 수의 총합은 어떻게 될까?

[2] 아이디어

인터넷에서 찾을 수 있는 대부분의 풀이에서는 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 좌표에 대한 쿼리를 날려봄으로써 카운트할 수 있다.

• x축 방향으로, 0에서 100000으로 간다.
• 각 x좌표에 대해
  + 왼쪽 변이 있으면 해당 변의 [b, t] 구간에 +1을 해준다.
  + 해당 x좌표 위의 집들에 대해, 해당 집의 y좌표에 대한 쿼리값을 답에 더한다
  + 오른쪽 변이 있으면 해당 변의 [b, t] 구간에 -1을 해준다.

구간 갱신이 잦은 문제이므로, 세그먼트 트리의 지연 전파를 이용하면 된다.

3. 전체 코드

#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);
	}
}

여담

문제를 많이 틀렸는데, 로직 상 틀린 점을 계속 못 찾았다.

틀린 이유는 마지막 줄에 줄바꿈을 안 해줘서였다. 출력할 때도 조심해서 문제를 풀자.