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보다 작거나 같은 수의 개수를 알 수 있다. 각각의 구간에서 이분 탐색을 하면 된다.
그러면 파라메트릭을 하면서 k번째 수를 찾을 수 있음을 알 수 있다.
대충 시간복잡도는 O(QlogNlogNlogX)(X는 가능한 수의 개수(10^18)이하)이므로 시간 내에 문제를 풀 수 있다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 3653 영화 수집 (0) | 2023.01.23 |
|---|---|
| 백준 3090 차이를 최소로 (0) | 2023.01.05 |
| 백준 15972 물탱크 (0) | 2023.01.05 |
| 백준 22348 헬기 착륙장 (0) | 2023.01.05 |
| 백준 1315 RPG (0) | 2023.01.05 |
