백준 7469 K번째 수

https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net i,j,k가 주어지면 배열 a[i...j]에서 k번째로 작은 수를 찾아내는 쿼리를 처리해야 한다. 구간 쿼리를 처리해야되니까 segment tree를 만들고 싶은데, 해당 쿼리를 처리하려면 merge sort tree를 만들면 된다. 머지 소트 트리를 만들면, 쿼리가 주어졌을 때 a[i...j]에서 임의의 수 x보다 작거나 같은 수의 개수를 알 수 있다. 각각의 구간에서 이분 탐색을 하면 된다. 그러면..

원문링크 : 백준 7469 K번째 수