6082 : 구간 최솟값 쿼리 (덱)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
구간 최솟값 쿼리
N개의 정수 배열에 대해 Q개의 구간 최솟값 쿼리 [l, r]를 처리하시오.
효율적인 구현: Sparse Table $O(N \log N)$ 전처리, $O(1)$ 쿼리
Sparse Table 원리:
- $sp[j][i]$ = 배열 i번째부터 $2^j$개 원소 중 최솟값
- 쿼리 [l, r]: $k = \lfloor \log_2(r-l+1) \rfloor$로 두 구간의 min을 취함
단조 덱(Monotonic Deque)을 활용한 슬라이딩 윈도우 방식도 응용 가능합니다.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 쿼리 수 $Q$: $1 \le Q \le 100{,}000$ (정수)
• 쿼리 범위 $[L, R]$: $1 \le L \le R \le N$
N개의 정수 배열에 대해 Q개의 구간 최솟값 쿼리 [l, r]를 처리하시오.
효율적인 구현: Sparse Table $O(N \log N)$ 전처리, $O(1)$ 쿼리
Sparse Table 원리:
- $sp[j][i]$ = 배열 i번째부터 $2^j$개 원소 중 최솟값
- 쿼리 [l, r]: $k = \lfloor \log_2(r-l+1) \rfloor$로 두 구간의 min을 취함
단조 덱(Monotonic Deque)을 활용한 슬라이딩 윈도우 방식도 응용 가능합니다.
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 쿼리 수 $Q$: $1 \le Q \le 100{,}000$ (정수)
• 쿼리 범위 $[L, R]$: $1 \le L \le R \le N$
입력 설명
첫째 줄에 배열 크기 N (1 ≤ N ≤ 100,000)과 쿼리 수 Q (1 ≤ Q ≤ 100,000)가 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
셋째 줄부터 Q개의 줄에 쿼리 구간 l r (1-indexed)이 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
셋째 줄부터 Q개의 줄에 쿼리 구간 l r (1-indexed)이 주어집니다.
출력 설명
각 쿼리의 구간 최솟값을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 3
3 1 4 1 5 9
1 3
2 5
4 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
1
1