취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1615번 문제인 교차개수세기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/1615 

주어진 선분들의 교차점의 개수가 몇 개인지 세는 문제이다.

선분들을 1) 왼쪽 노드번호가 작은 것부터, 2) 왼쪽 노드번호가 같은 두 선분이 있다면 오른쪽 노드번호가 작은 것부터 살펴보자.

지금 보고있는 선분과 앞서 나온 선분들 사이의 교차점의 개수는 지금 긋는 선분의 오른쪽 노드번호보다 큰 오른쪽 노드번호를 갖는 선분들의 수와 같다는 점을 관찰하자. 앞서나온 선분들의 왼쪽끝은 지금의 선분보다 번호가 작기 때문이다. 같은 경우 교차점은 없기 때문에 고려하지 않는다. 2) 규칙을 잘 생각해보면 알 수 있다.

따라서 구간합을 관리하는 세그먼트트리(segment tree)를 이용하면 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int seg[4097];

void update(int L, int R, int qI) {
	int sI = 1;
	while (L < R) {
		seg[sI]++;
		int mid = (L + R) / 2;
		if (qI <= mid) {
			R = mid;
			sI = sI * 2;
		}
		else {
			L = mid + 1;
			sI = sI * 2 + 1;
		}
	}
	seg[sI]++;
}

int rangesum(int L, int R, int qL, int qR, int sI) {
	if (R < qL || qR < L) return 0;
	if (qL <= L && R <= qR)return seg[sI];
	return rangesum(L, (L + R) / 2, qL, qR, sI * 2) + rangesum((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1);
}

vector<pair<int, int>> pairs;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M; cin >> N >> M;
	while (M--) {
		int x, y; cin >> x >> y;
		pairs.push_back({ x,y });
	}

	sort(pairs.begin(), pairs.end());

	ll ans = 0;
	for (auto p : pairs) {
		int x = p.second;
		ans += rangesum(1, N, x + 1, N, 1);
		update(1, N, x);
	}

	cout << ans;
}