백준 2357 최솟값과 최댓값
23 Jun 2021https://www.acmicpc.net/problem/2357
n개의 정수가 주어지면 순서대로 배열에 집어넣는다. 그 후 구간 쿼리가 주어질 때마다 해당 구간에서의 최댓값과 최솟값을 각각 구해주는 문제이다. 최댓값, 최솟값을 구하는 문제이기 때문에 fenwick tree는 사용할 수 없고 세그먼트 트리를 활용해서 구현해주어야 한다.
업데이트가 없기 때문에 구현이 조금 간편해졌지만 업데이트 구현도 크게 어렵지 않으니 한번 고민해보면 좋다. 세그먼트 트리 2개를 만들어서 하나는 구간의 최댓값, 하나는 구간의 최솟값을 저장하도록 만들자. 세그먼트 트리를 처음 만들 때 좌측 child와 우측 child에 대해서 반환받은 결과를 가지고 둘 중 최댓값 혹은 최솟값으로 구간의 최대 최소를 정해주면 된다. 이 후 구간 쿼리가 주어질 때마다 두 세그먼트 트리에서 각각 결과를 얻어내서 출력하면 된다.
- 전체 코드
struct Segment {
var arr:[Int]
var tree:[Int]
var isMax:Bool
init(arr: [Int], isMax: Bool) {
self.arr = arr
self.isMax = isMax
tree = Array(repeating: 0, count: 4*arr.count)
makeTree(start: 0, end: arr.count-1, node: 1)
}
mutating func makeTree(start: Int, end: Int, node: Int) -> Int {
if start == end {
tree[node] = arr[start]
}
else {
let mid = (start+end)/2
if isMax {
tree[node] = max(makeTree(start: start, end: mid, node: 2*node), makeTree(start: mid+1, end: end, node: 2*node+1))
}
else {
tree[node] = min(makeTree(start: start, end: mid, node: 2*node), makeTree(start: mid+1, end: end, node: 2*node+1))
}
}
return tree[node]
}
func find(start: Int, end: Int, node: Int, left: Int, right: Int) -> Int {
if end < left || right < start {
return isMax ? 0 : 1_000_000_001
}
if left <= start && end <= right {
return tree[node]
}
let mid = (start+end)/2
if isMax {
return max(find(start: start, end: mid, node: 2*node, left: left, right: right), find(start: mid+1, end: end, node: 2*node+1, left: left, right: right))
}
else {
return min(find(start: start, end: mid, node: 2*node, left: left, right: right), find(start: mid+1, end: end, node: 2*node+1, left: left, right: right))
}
}
}
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
var arr = Array(repeating: 0, count: n)
for i in 0..<n {
arr[i] = Int(String(readLine()!))!
}
var maxTree = Segment(arr: arr, isMax: true)
var minTree = Segment(arr: arr, isMax: false)
var str = ""
for _ in 0..<m {
let line = readLine()!.split(separator: " ").map{Int(String($0))!}
str += "\(minTree.find(start: 0, end: n-1, node: 1, left: line[0]-1, right: line[1]-1)) \(maxTree.find(start: 0, end: n-1, node: 1, left: line[0]-1, right: line[1]-1))\n"
}
print(str)