구간 트리. [2517]

[1. 문제 설명]

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

---

[2. 풀이 접근]

첫번째 좌표 압축

• 실력이라는 값은 10억 이하의 값이다.
• 그러나 주어지는 데이터 개수는 최대 50만개 이다.
• 또, 고유한 값으로 주어지므로, 좌표 압축을 통해 현실적인 메모리에서 
• 각 실력의 순위를 확인 할 수 있다.

iterate 순서

• 꼴지부터 iterate 해서, 자신 보다 앞에 있으면서 낮은 실력을 갖는 사람의 수를 구하기
  => 이 방식으로 하면, 구간 트리를 먼저 만들고,
  => 구간 트리에서 낮은 순위에 있는 사람의 실력을 점차적으로 제거해나가야 한다.
• 1등부터 iterate 해서, 자신 보다 앞에 있으면서 낮은 실력을 갖는 사람의 수를 구하기
  => 이 방식으로 하면, empty 한 구간 트리에서 시작해서
  => 높은 순위에 있는 사람의 실력을 점차 추가해 나간다.
• 1등 부터 iterate 하는 방식이 좀 더 좋아 보인다.
• 한쪽 방향으로 만 iterate 하는 사고 방식을 취하지 않도록 하는 것이 좋겠다.

---

[3. 코드]