BOJ 20418 역전의 제왕 (Hard)

역전의 제왕 (Hard)

 

아마 가장 간단한 방법은 PBDS(Policy-Based Data Structure)라는 라이브러리에 있는 Order Statistics Tree라는 걸 쓰는 것 같다.
이 자료구조는 정렬된 순서를 유지하면서 원소 삽입, 삭제, \(k\)번째 원소, lower bound와 그 위치를 다 \(O(\log{n})\)만에 할 수 있는 기능이 있다. 그러면 스코어보드를 구현만 하면 변하기 전 순위와 변한 후 순위를 모두 쉽게 알 수 있다.

이 것과 별개로 내가 푼 방법은 조금 다른 식이다.
우선 마지막 순위를 구하는 것은 우선순위 큐로 할 수 있다. 그런데 문제 하나를 스코어보드에 반영한 뒤에 얼마나 순위가 올랐는지는 쉽게 알 수 없다.

이 것을 구하기 위해 우선순위 큐에서 나온 참가자의 순서를 기록해둔다. 이 때, 더 이상 공개할 문제가 없는 참가자도 한 번은 나오도록 한다.
예제 1을 예로들면 이 순서는 \(3\ 2\ 1\ 2\ 1\ 2\)가 된다.
그리고 이렇게 볼때 각각 오른 순위는 다음에 자신이 나올 때까지의 사이에 있는 서로 다른 수의 개수가 된다.
즉, \(k\)번 참가자의 역전 포인트는 이 기록에서 어떤 \(k\)와 그 다음 \(k\)사이의 서로 다른 수의 개수를 각각 구해서 모두 더한 값과 같다.

그러면 결국 문제는 구간 내의 서로 다른 수의 개수 쿼리를 처리하는 것과 같다.
이 문제는 쿼리 구간이 특이하게 정해지는 경우라서 다른 방법이 있지 않을까 싶기도 한데, 아무튼 서로 다른 수와 쿼리 1를 푸는 방법을 그대로 적용할 수 있다. Mo's algorithm, 세그먼트 트리 등이 있다.