마법사의 수정 구슬
골드 V의견: 0
마법사 앙리는 \(N\)개의 수정 구슬을 일렬로 늘어놓았다. \(i\)번째 구슬의 마력은 \(a_i\)이다.
앙리는 여러 번의 실험을 위해 구간 \([l, r]\)에 있는 구슬들 중 마력이 가장 낮은 값을 알고 싶다. 실험의 수 \(Q\)가 매우 많으므로 각 질문에 빠르게 답해야 한다.
\(Q\)개의 질문에 모두 답하여라.
- \(1 \le N, Q \le 200\,000\)
- \(1 \le l \le r \le N\)
- \(-10^9 \le a_i \le 10^9\)
첫째 줄에 구슬의 수 \(N\)과 질문의 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 구슬의 마력 \(a_1, a_2, \ldots, a_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 걸쳐 질문이 주어진다. 각 줄에는 정수 \(l\), \(r\)이 공백으로 구분되어 있으며, 구간 \([l, r]\)에서의 최솟값을 묻는다.
\(Q\)개의 줄에 걸쳐 각 질문의 답을 순서대로 출력한다.
8 3
3 1 4 1 5 9 2 6
1 5
3 7
2 2
1
1
1
구간 \([1, 5]\)의 원소는 \(3, 1, 4, 1, 5\)로 최솟값은 \(1\)이다. 구간 \([3, 7]\)의 원소는 \(4, 1, 5, 9, 2\)로 최솟값은 \(1\)이다. 구간 \([2, 2]\)는 원소가 \(1\)뿐이므로 최솟값도 \(1\)이다.
5 3
10 20 30 40 50
1 5
2 4
5 5
10
20
50
단조 증가 배열. \([1,5]\) 전체의 최솟값은 \(10\), \([2,4]\)의 최솟값은 \(20\), \([5,5]\)의 최솟값은 \(50\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법사의 수정 구슬
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법사의 수정 구슬