문제

출처 : https://www.algospot.com/judge/problem/read/NERD2

대 성황이었던 지난 알고스팟 연간 모의고사 이후 프로그래밍 대회의 열기는 날로 뜨거워져 올해는 10만명이 넘는 사람들이 참가 신청을 할 것으로 예상되고 있습니다. 그러나 채점관을 할 자원 봉사자는 예년과 똑같이 5명뿐이라, 이 사람들을 대회에 다 참가시킬 수는 없습니다. 따라서 올해에도 참가 신청을 한 사람 중 진정한 프로그래밍 너드들만을 대회에 참가할 수 있도록 받아 주기로 했습니다.

종만의 새로운 이론에 따르면, 어떤 사람의 너드 지수는 다음 두 가지 값에 의해 결정됩니다.

• 알고스팟 온라인 채점 시스템에서 푼 문제의 수 p
• 밤 새면서 지금까지 끓여먹은 라면 그릇 수 q

이 이론에 따르면 어떤 참가 신청자 a 의 문제 수 pa 와 그릇 수 qa 를 다른 참가 신청자 b 의 문제 수 pb 와 그릇 수 qb 에 각각 비교했을 때, pa < pb, qa < qb 라면 참가 신청자 a 는 너드일 가능성이 없습니다. 조직위는 너드일 가능성이 있는 사람들만을 대회에 받아주기로 했습니다.

한 사람의 참가 가능 여부는 다른 사람들에 의해 결정되기 때문에, 대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀝니다. 예를 들어 다음과 같은 4명의 사람들이 순서대로 참가 신청을 했다고 합시다.

종만과 재훈이 순서대로 대회 참가 신청을 하면 대회에 참가할 수 있는 사람의 수는 각각 1, 2 로 늘어나지만, 효승이는 문제 수도 라면 그릇 수도 종만보다 많으므로 효승이 참가 신청을 한 시점에서 종만은 더 이상 대회에 참가할 수 없습니다. 따라서 이 네 명이 참가 신청을 할 때마다 참가 가능자의 수는 1, 2, 2, 3으로 변합니다.

이렇게 각 사람이 참가 신청을 할 때마다 대회에 참가할 수 있는 사람들의 수가 어떻게 변하는지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 참가 신청한 사람들의 수 N (1 <= N <= 50000) 이 주어집니다. 그 후 N 줄에 각 2개의 정수로 각 사람의 문제 수 pi 와 라면 그릇 수 qi 가 참가 신청한 순서대로 주어집니다 (0 <= pi,qi <= 100000) . 두 사람의 문제 수나 라면 그릇 수가 같은 경우는 없다고 가정해도 좋습니다. 입력의 양이 많으므로 가능한 빠른 입력 함수를 사용하는 것이 좋습니다.

출력

각 사람이 참가 신청을 할 때마다 대회 참가 자격이 되는 사람의 수를 계산한 뒤, 각 테스트 케이스마다 그 합을 출력합니다.

풀이

주어진 입력값이 중복값이 존재하지 않은 두 숫자 쌍이므로, 이진 검색트리를 통해 효율적인 범위 검색이 가능하다. 새로운 참가자가 주어졌을 때, 기존 참가자 중 문제수와 라면그릇수가 더 큰 참가자가 존재하여 참가할 수 없는경우와, 참가할 때 자신보다 문제수와 라면 그릇수가 더 작은 참가자들이 존재하는 경우 두 가지를 고려하는 것이 핵심이다. 특히, 중요한 것은 참가자들을 문제수를 기준으로 오름차순으로 정렬된 형태를 생각할 때, 각 참가자들의 그릇수는 내림차순의 형태를 나타나게 된다. 만약 p1<p2일 때, q1<q2이면 1번이 2번보다 모두 작은 경우이므로 모순되기 때문에, 문제수에 따라 정렬된 이진 트리를 생각할 때 그릇수는 반대로 정렬된다는 것이다.

// 새로 입력된 문제 수 p, 그릇 수 q, 이진 검색 트리 map
if (map.higherKey(p) != null) {
	int dish = map.get(map.higherKey(p));
	if (dish > q) {
		sum += map.size();
		continue;
	}
}
map.put(p, q);
while (map.lowerKey(p) != null) {
	int dish = map.get(map.lowerKey(p));
	if (dish > q)
		break;
	else
		map.remove(map.lowerKey(p));
}
sum += map.size();

이진 검색트리 map을 구현하고, 먼저 참가자가 대회에 참가할 수 있는 여부를 검사해야 한다. 이는 트리에 참가자보다 문제수와 그릇수가 더 많은 참가자의 존재여부로 파악할 수 있다. map은 문제수를 키값으로 하여 정렬된 이진 검색트리인데, 입력된 문제 수 p보다 더 큰값이 존재하는지를 higherKey 메소드를 통해 알아내며 존재할 경우, p보다 큰 값중 가장 작은값은 그릇수가 가장 큰 경우에 해당하므로 해당 참가자의 그릇수가 q보다 클 때 참가할 수 없는 경우가 되기 때문에 현재 트리의 크기를 합산하고 종료한다.

이에 해당되지 않는 경우는 map에 (p,q)를 추가하며 (p,q)보다 작은 값들을 찾아내어 트리에서 제거하여야 한다. 이는 일일이 순회하며 파악할 필요 없이, 문제수 p보다 작은 값 중 최댓값은 그릇수가 나머지중 최소이므로 해당 그릇수가 q보다 작은지 여부를 검사하여, 작은 경우 해당 참가자를 제거하고 다시 p보다 작은 최댓값을 다음값으로 갱신하는 과정을 반복함으로써 (p,q)쌍보다 작은 값들을 차례로 제거할 수 있다.