https://www.acmicpc.net/problem/2357

문제예시

1. 입력

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

2. 출력

5 100
38 100
20 81
5 81

---

풀이과정

• 세그먼트 트리를 이용해서 구간에 대한 최댓값과 최솟값을 구하고 출력하기로 함

---

코드

• 최댓값과 최솟값을 구하기 위한 세그먼트 트리를 각각 구현
• 각 섹션별로 구간에 대한 최댓값과 최솟값을 저장하도록 한다
• 입력된 값에 따라 해당 구간 사이에서 존재하는 최대값과 최솟값을 각각 구하여 출력한다

class MINSegmentTree {
    var value: Int
    var leftBound: Int
    var rightBound: Int
    var leftChild: MINSegmentTree?
    var rightChild: MINSegmentTree?
    
    init(array: [Int], leftBound: Int, rightBound: Int) {
        self.leftBound = leftBound
        self.rightBound = rightBound
        
        if leftBound == rightBound {
            value = array[leftBound]
        } else {
            let middle = (leftBound + rightBound) / 2
            leftChild = MINSegmentTree(array: array, leftBound: leftBound, rightBound: middle)
            rightChild = MINSegmentTree(array: array, leftBound: middle+1, rightBound: rightBound)
            value = min(leftChild!.value, rightChild!.value)
        }
    }
    
    func query(leftBound: Int, rightBound: Int) -> Int {
        if self.leftBound == leftBound && self.rightBound == rightBound {
            return self.value
        }
        
        guard let leftChild = leftChild else { return Int.max }
        guard let rightChild = rightChild else { return Int.max }
        
        if leftChild.rightBound < leftBound {
            return rightChild.query(leftBound: leftBound, rightBound: rightBound)
        } else if rightChild.leftBound > rightBound {
            return leftChild.query(leftBound: leftBound, rightBound: rightBound)
        } else {
            let leftQuery = leftChild.query(leftBound: leftBound, rightBound: leftChild.rightBound)
            let rightQuery = rightChild.query(leftBound: rightChild.leftBound, rightBound: rightBound)
            return min(leftQuery, rightQuery)
        }
    }
}

class MAXSegmentTree {
    var value: Int
    var leftBound: Int
    var rightBound: Int
    var leftChild: MAXSegmentTree?
    var rightChild: MAXSegmentTree?
    
    init(array: [Int], leftBound: Int, rightBound: Int) {
        self.leftBound = leftBound
        self.rightBound = rightBound
        
        if leftBound == rightBound {
            value = array[leftBound]
        } else {
            let middle = (leftBound + rightBound) / 2
            leftChild = MAXSegmentTree(array: array, leftBound: leftBound, rightBound: middle)
            rightChild = MAXSegmentTree(array: array, leftBound: middle+1, rightBound: rightBound)
            value = max(leftChild!.value, rightChild!.value)
        }
    }
    
    func query(leftBound: Int, rightBound: Int) -> Int {
        if self.leftBound == leftBound && self.rightBound == rightBound {
            return self.value
        }
        
        guard let leftChild = leftChild else { return Int.max }
        guard let rightChild = rightChild else { return Int.max }
        
        if leftChild.rightBound < leftBound {
            return rightChild.query(leftBound: leftBound, rightBound: rightBound)
        } else if rightChild.leftBound > rightBound {
            return leftChild.query(leftBound: leftBound, rightBound: rightBound)
        } else {
            let leftQuery = leftChild.query(leftBound: leftBound, rightBound: leftChild.rightBound)
            let rightQuery = rightChild.query(leftBound: rightChild.leftBound, rightBound: rightBound)
            return max(leftQuery, rightQuery)
        }
    }
}

let input = readLine()!.split(separator: " ").map{Int($0)!}
var arr = [Int]()


for _ in 0..<input[0] {
    arr.append(Int(readLine()!)!)
}

let minSegmentTree = MINSegmentTree(array: arr, leftBound: 0, rightBound: arr.count-1)
let maxSegmentTree = MAXSegmentTree(array: arr, leftBound: 0, rightBound: arr.count-1)

for _ in 0..<input[1] {
    let order = readLine()!.split(separator: " ").map{Int($0)!}
    
    print(minSegmentTree.query(leftBound: order[0] - 1, rightBound: order[1] - 1),maxSegmentTree.query(leftBound: order[0] - 1, rightBound: order[1] - 1))
}

---

트리 매우 어렵다...