Funcia
Lv.4coordinate-compressionpersistent-segment-treesegment-tree

구간에서 K번째로 작은 수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 a와 질의 목록 queries가 주어집니다. 각 질의 queries[q] = [l, r, k]는 구간 a[l..r](양 끝 포함)의 값을 오름차순으로 정렬했을 때 k번째로 작은 값을 묻습니다. k는 1부터 셉니다.

배열 a는 질의 도중 바뀌지 않습니다. 모든 질의의 답을 순서대로 배열에 담아 반환하세요.

입출력 예

aqueriesresult
[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[]

제한 사항

  • 1≤N=1 \le N = a.length ≤100,000\le 100{,}000
  • −109≤-10^9 \le a[i] ≤109\le 10^9
  • 1≤1 \le queries.length ≤100,000\le 100{,}000
  • queries[q] = [l, r, k], 0≤l≤r<N0 \le l \le r < N, 1≤k≤r−l+11 \le k \le r - l + 1

기대 복잡도

시간
O((N + Q) log N)
공간
O(N log N)

입출력 예

aqueries기대 출력
[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]

힌트

힌트

질의마다 구간을 정렬하거나 선택 알고리즘을 돌리면 O(NQ)O(NQ) 이상입니다.

1. 값 압축 후 "개수 세그먼트 트리"

값을 정렬해 0..M-1 순위로 바꾸고, 순위별 개수를 담는 세그먼트 트리를 생각합니다. 이 트리가 있으면 루트에서 시작해 "왼쪽 자식의 개수 ≥ k이면 왼쪽, 아니면 k에서 빼고 오른쪽"으로 내려가 O(log⁡M)O(\log M)에 k번째 값을 찾을 수 있습니다.

2. 접두사마다 한 그루씩 — 퍼시스턴트 세그먼트 트리

T_i = a[0..i-1]의 개수 트리라 하면 구간 [l, r]의 개수는 T_{r+1} - T_l(노드별 뺄셈)입니다. 두 트리를 동시에 내려가며 위 탐색을 하면 됩니다.

트리를 N번 통째로 복사하면 메모리가 부족합니다. T_{i+1}은 T_i에서 경로 하나(루트에서 리프까지 O(log⁡M)O(\log M)개 노드)만 다르므로, 바뀐 노드만 새로 만들고 나머지 자식은 이전 버전과 공유합니다. 전체 노드 수는 O(Nlog⁡M)O(N \log M)입니다.

머지 소트 트리 + 이분 탐색(O(log⁡3N)O(\log^3 N))이나 웨이블릿 트리로도 풀 수 있습니다.

복잡도 목표

O((N+Q)log⁡N)O((N + Q) \log N)이 목표입니다. 질의마다 구간을 처리하는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)318 ms추정
C++ (GCC, gnu++23)318 ms도출됨
Python 3.132576 ms도출됨
Java 252126 ms도출됨
Kotlin 2.4 (JVM)1636 ms추정
C# 14 (.NET 10)1636 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.