BOJ 5419 북서풍

문제

• 링크 - https://www.acmicpc.net/problem/5419

문제 분류

• 난이도 - 중
• 태그 - 구간 트리

문제 풀이

각 점에 대해서 자신의 위치보다 \(x\) 값이 크거나 같으면서, \(y\)값은 작거나 같은 지점들을 모두 세면 되는 문제다. 그런데 \(n\)의 값을 보면 알겠지만, 단순하게 모두 다 해보는 \(O(N^2)\) 방식으로는 안된다. 구간 트리를 사용하면 이 정보를 빠르게 셀 수 있다.

먼저 좌표들을 (1) \(x\)값이 감소하는 방향으로, (2) \(y\) 값이 증가하는 방향으로 정렬한다.

그런 다음에 유일한 \(y\) 좌표들을 가지고 구간 트리를 구성한다. 이제 앞서 점들을 정렬한 순서대로 하나씩 자신보다 \(x\) 값이 크거나 같은 점들 중에서 \(y\) 값이 작거나 같은 좌표들을 구간 합 트리에 질의를 하여 찾아낸다. 그런 다음에 자신의 \(y\) 좌표에 해당하는 트리의 구간(위치)에 +1을 하면 된다. 

소스 코드

#include <iostream> #include <string> #include <algorithm> #include <cstring> #include <cmath> #include <vector> #include <cstdlib> #include <stack> #include <queue> #include <set> #include <map> using namespace std; struct RangeSum { int n; vector<int> tree; RangeSum(const vector<int>& a) { n = a.size(); if (n == 0) return; tree.assign(n * 4, 0); } int query(int p, int left, int right, int qLeft, int qRight) { if (qLeft > right || qRight < left) return 0; if (qLeft <= left && right <= qRight) return tree[p]; int mid = (left + right) / 2; return query(p * 2, left, mid, qLeft, qRight) + query(p * 2 + 1, mid + 1, right, qLeft, qRight); } int update(int p, int left, int right, int you, int plus) { if (you < left || you > right) return tree[p]; if (left == right) return tree[p] += plus; int mid = (left + right) / 2; return tree[p] = update(p * 2, left, mid, you, plus) + update(p * 2 + 1, mid + 1, right, you, plus); } int query(int qLeft, int qRight) { return query(1, 0, n - 1, qLeft, qRight); } void update(int you, int plus) { update(1, 0, n - 1, you, plus); } }; bool predicate(const pair<int, int>& lhs, const pair<int, int>& rhs) { if (lhs.first != rhs.first) return lhs.first > rhs.first; return lhs.second < rhs.second; } int main() { int T; scanf("%d", &T); while (T--) { int n; scanf("%d", &n); vector<pair<int, int>> locations; vector<int> a; for (int i = 0; i < n; i++) { int x, y; scanf("%d%d", &x, &y); locations.emplace_back(x, y); a.push_back(y); } sort(locations.begin(), locations.end(), predicate); sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); RangeSum rSum(a); long long ans = 0; for (int i = 0; i < n; i++) { int qLeft = 0; int qRight = lower_bound(a.begin(), a.end(), locations[i].second) - a.begin(); ans += rSum.query(qLeft, qRight); rSum.update(qRight, 1); } printf("%lld\n", ans); } return 0; }