6079 : 단조 스택·큐 비교
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
단조 스택·큐 비교
두 종류의 쿼리를 처리하시오.
쿼리 유형:
-
오큰수 = i번째 원소 이후 처음 등장하는 자신보다 큰 수. 없으면 -1.
→ 단조 스택(Monotonic Stack) 전처리 $O(N)$
-
→ 단조 덱(Monotonic Deque) 또는 Sparse Table $O(1)$
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 윈도우 크기 $K$: $1 \le K \le N$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
두 종류의 쿼리를 처리하시오.
쿼리 유형:
-
NGE i: i번째 원소의 오큰수(Next Greater Element)를 출력합니다.오큰수 = i번째 원소 이후 처음 등장하는 자신보다 큰 수. 없으면 -1.
→ 단조 스택(Monotonic Stack) 전처리 $O(N)$
-
WMIN l r: 구간 [l, r]의 최솟값을 출력합니다.→ 단조 덱(Monotonic Deque) 또는 Sparse Table $O(1)$
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 윈도우 크기 $K$: $1 \le K \le N$ (정수)
• 각 원소: $-10^9 \le a_i \le 10^9$ (정수)
입력 설명
첫째 줄에 배열 크기 N (1 ≤ N ≤ 100,000)과 쿼리 수 Q (1 ≤ Q ≤ 50,000)가 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
셋째 줄부터 Q개의 쿼리가 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
셋째 줄부터 Q개의 쿼리가 주어집니다.
출력 설명
각 쿼리의 결과를 한 줄에 하나씩 출력합니다. NGE가 없으면 -1을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 3
3 5 2 7 1 6
NGE 1
WMIN 1 4
NGE 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
5
2
7