구간에서 K번째로 작은 수
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
정수 배열 a와 질의 목록 queries가 주어집니다. 각 질의 queries[q] = [l, r, k]는 구간 a[l..r](양 끝 포함)의 값을 오름차순으로 정렬했을 때 k번째로 작은 값을 묻습니다. k는 1부터 셉니다.
배열 a는 질의 도중 바뀌지 않습니다. 모든 질의의 답을 순서대로 배열에 담아 반환하세요.
입출력 예
| a | queries | result |
|---|---|---|
[5, 1, 4, 2, 3] | [[0, 4, 2], [1, 3, 3], [2, 2, 1], [0, 2, 3]] | [2, 4, 4, 5] |
[2, 2, 1, 2] | [[0, 3, 1], [0, 3, 2], [1, 2, 2]] | [1, 2, 2] |
입출력 예 설명
예 1
[0, 4, 2]— 전체를 정렬하면[1, 2, 3, 4, 5]이고 2번째는2입니다.[1, 3, 3]—[1, 4, 2]를 정렬한[1, 2, 4]의 3번째는4입니다.[2, 2, 1]— 원소가4하나뿐입니다.[0, 2, 3]—[5, 1, 4]에서 가장 큰 값5입니다.
예 2 — 같은 값은 각각 따로 셉니다. [2, 2, 1, 2]를 정렬하면 [1, 2, 2, 2]입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(a: int[], queries: int[][]) → int[]
제한 사항
-
a.length -
a[i] -
queries.length queries[q] = [l, r, k], ,
기대 복잡도
- 시간
- O((N + Q) log N)
- 공간
- O(N log N)
입출력 예
| a | queries | 기대 출력 |
|---|---|---|
[5,1,4,2,3] | [[0,4,2],[1,3,3],[2,2,1],[0,2,3]] | [2,4,4,5] |
[2,2,1,2] | [[0,3,1],[0,3,2],[1,2,2]] | [1,2,2] |
힌트
힌트
질의마다 구간을 정렬하거나 선택 알고리즘을 돌리면 이상입니다.
1. 값 압축 후 "개수 세그먼트 트리"
값을 정렬해 0..M-1 순위로 바꾸고, 순위별 개수를 담는 세그먼트 트리를 생각합니다. 이 트리가 있으면 루트에서 시작해 "왼쪽 자식의 개수 ≥ k이면 왼쪽, 아니면 k에서 빼고 오른쪽"으로 내려가 에 k번째 값을 찾을 수 있습니다.
2. 접두사마다 한 그루씩 — 퍼시스턴트 세그먼트 트리
T_i = a[0..i-1]의 개수 트리라 하면 구간 [l, r]의 개수는 T_{r+1} - T_l(노드별 뺄셈)입니다. 두 트리를 동시에 내려가며 위 탐색을 하면 됩니다.
트리를 N번 통째로 복사하면 메모리가 부족합니다. T_{i+1}은 T_i에서 경로 하나(루트에서 리프까지 개 노드)만 다르므로, 바뀐 노드만 새로 만들고 나머지 자식은 이전 버전과 공유합니다. 전체 노드 수는 입니다.
머지 소트 트리 + 이분 탐색()이나 웨이블릿 트리로도 풀 수 있습니다.
복잡도 목표
이 목표입니다. 질의마다 구간을 처리하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 318 ms | 추정 |
| C++ (GCC, gnu++23) | 318 ms | 도출됨 |
| Python 3.13 | 2576 ms | 도출됨 |
| Java 25 | 2126 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1636 ms | 추정 |
| C# 14 (.NET 10) | 1636 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |