8050 : 구간 최솟값 쿼리
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
길이 $N$인 정수 배열 $A$가 주어지고, $Q$개의 쿼리가 각각 두 인덱스 $l$, $r$을 제시합니다. 각 쿼리에 대해 $A[l], A[l+1], \ldots, A[r]$ 중 최솟값을 출력하십시오.
배열은 변경되지 않으며 (정적 배열), 쿼리만 최대 $2 \times 10^5$개까지 주어집니다.
[제약 조건]
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le l \le r \le N$
배열은 변경되지 않으며 (정적 배열), 쿼리만 최대 $2 \times 10^5$개까지 주어집니다.
[제약 조건]
• $1 \le N, Q \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le l \le r \le N$
입력 설명
첫 번째 줄에 두 정수 $N$과 $Q$ ($1 \le N, Q \le 2 \times 10^5$)가 주어집니다.
두 번째 줄에 $N$개의 정수 $A_i$ ($1 \le A_i \le 10^9$)가 주어집니다.
다음 $Q$줄에 각각 두 정수 $l$과 $r$ ($1 \le l \le r \le N$)이 주어집니다.
두 번째 줄에 $N$개의 정수 $A_i$ ($1 \le A_i \le 10^9$)가 주어집니다.
다음 $Q$줄에 각각 두 정수 $l$과 $r$ ($1 \le l \le r \le N$)이 주어집니다.
출력 설명
$Q$개의 쿼리 결과를 각 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3\n3 1 4 1 5\n1 3\n2 4\n3 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1\n1\n1도움
스파스 테이블(Sparse Table)을 사용하면 $O(N \log N)$ 전처리 후 각 쿼리를 $O(1)$에 처리할 수 있습니다.