[BOJ] 14428,14438 수열과 쿼리 16,17

PS/BOJ 2020. 8. 23. 19:21

14428번: 수열과 쿼리 16

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인덱스를 출력한다. 그러

www.acmicpc.net

14438번: 수열과 쿼리 17

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 �

www.acmicpc.net

알고리즘: Segment tree

시간복잡도: $O((M+N)logN)$

16과 17은 사실상 같은 문제... (하나는 최솟값의 index 출력, 나머지 하나는 최솟값 출력)

수열과 쿼리 15에서 살짝 업그레이드 된 문제이다.

최솟값을 전체 구간이 아닌 주어진 구간 내에서 구해야한다.

[l, r]의 구간 쿼리가 들어왔다고 하자.

그럼 우리는 [l, r]의 모든 노드들을 살펴볼 필요 없이 위의 그림처럼 색칠된 노드들만 확인하면 된다.

이러면, 구간 쿼리를 $O(logN)$만에 처리할 수 있다.

코딩 코딩