Funcia
Lv.3segment-treesparse-table

구간 최솟값 질의

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

어느 산길의 지점별 고도가 정수 배열 values로 주어집니다. 등산객들이 "l번 지점부터 r번 지점까지 걸으면 가장 낮은 곳의 고도는 얼마인가요?"라고 묻습니다.

queries[j] = [l, r]마다 values[l], values[l+1], …, values[r] 중 최솟값을 구해 질문 순서대로 배열에 담아 반환하세요. values는 바뀌지 않습니다.

입출력 예

valuesqueriesresult
[5, 2, 8, 6, 3, 7][[0, 5], [2, 3], [3, 5], [4, 4]][2, 6, 3, 3]
[-1, -1, 0][[1, 2], [0, 0]][-1, -1]

입출력 예 설명

예 1 — 전체 구간의 최솟값은 2, [2, 3] 구간 {8, 6}의 최솟값은 6, [3, 5] 구간 {6, 3, 7}의 최솟값은 3입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(values: int[], queries: int[][]) → int[]

제한 사항

  • 1≤N=1 \le N = values.length ≤200,000\le 200{,}000, −109≤-10^9 \le values[i] ≤109\le 10^9
  • 1≤Q=1 \le Q = queries.length ≤200,000\le 200{,}000
  • 0≤0 \le l ≤\le r <N< N

기대 복잡도

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

입출력 예

valuesqueries기대 출력
[5,2,8,6,3,7][[0,5],[2,3],[3,5],[4,4]][2,6,3,3]
[-1,-1,0][[1,2],[0,0]][-1,-1]

힌트

힌트

배열이 바뀌지 않으므로 미리 표를 만들어 두고 질문마다 빠르게 답할 수 있습니다.

희소 테이블(sparse table): t[k][i] = values[i .. i + 2^k - 1]의 최솟값으로 정의하면

t[0][i]=values[i],t[k][i]=min⁡(t[k−1][i], t[k−1][i+2k−1])t[0][i] = \text{values}[i], \qquad t[k][i] = \min(t[k-1][i],\ t[k-1][i + 2^{k-1}])

로 O(Nlog⁡N)O(N \log N)에 만들 수 있습니다. 질문 [l, r]은 길이 L=r−l+1L = r - l + 1에 대해 2k≤L2^k \le L인 가장 큰 kk를 골라

min⁡(t[k][l], t[k][r−2k+1])\min(t[k][l],\ t[k][r - 2^k + 1])

로 답합니다. 두 구간이 겹쳐도 최솟값에는 영향이 없기 때문에 O(1)O(1)입니다. (세그먼트 트리로 O(log⁡N)O(\log N)에 답해도 됩니다.)

복잡도 목표

질문마다 구간을 직접 훑는 O(NQ)O(NQ) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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