[BOJ 2107 // C++] 포함하는 구간

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

 

이번에 볼 문제는 백준 2107번 문제인 포함하는 구간이다.
문제는 아래 링크를 확인하자.

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

2107번: 포함하는 구간

각 구간 [L,R]을 R 오름차순으로 정렬하고, 각 구간을 순서대로 살펴보면서 지금까지 나온 구간 중 왼쪽 끝이 L보다 큰 구간의 개수를 세어 문제를 해결하자. [L,R]에 포함되는 모든 구간은 오른쪽 끝이 R보다 작아야하므로 지금까지 나온 구간들에 모두 들어있음을 관찰하자.

 

좌표의 범위가 넓으니 좌표압축을 하고 세그먼트트리를 이용한 구간합을 이용해 문제를 해결하자..

 

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int seg[131073];

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

int rangesum(int L, int R, int qL, int qR, int sI) {
	if (qR < L || R < qL) 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>> vec;
int leftend[25001];

int ans;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		int L, R; cin >> L >> R;
		vec.emplace_back(make_pair(L, i));
		vec.emplace_back(make_pair(R, i));
	}

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

	for (int x = 0; x < N * 2; x++) vec[x].first = x + 1;

	for (auto& p : vec) {
		int x = p.first, id = p.second;
		if (leftend[id]) {
			ans = max(ans, rangesum(1, 50000, leftend[id], x, 1));
			update(leftend[id]);
		}
		else leftend[id] = x;
	}

	cout << ans;
}