[2357] 최솟값과 최댓값

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

2357번: 최솟값과 최댓값

세그먼트 트리 문제다.

 

풀이

각 노드에 (Int, Int) 자료형을 통해 최솟값과 최댓값을 담는 세그먼트 트리를 생성하여, 각 구간별 최솟값과 최댓값이 담기는 세그먼트 트리를 생성하여 조건에 맞게 출력하면 된다.

 

[1,2,3,4,5] 배열을 기준으로 만든 세그먼트 트리다. 리프노드에는 동일한 값을 넣었다. 

 

트리를 읽어야 할 때는 구간에 해당하는 노드를 탐색, 각각의 최댓값과 최솟값을 비교하여 반환하면 된다.

해당 그림은 1 ~ 4번 인덱스 구간의 최솟값, 최댓값을 읽어올 때 참고하게 될 노드다.

범위 밖의 노드라면 입력 범위의 최댓값과 최솟값을 바꾸어 출력하게 하였다. ((1,000,000,000, 1) 리턴)

 

정답 코드

	import Foundation
	//by rhyno
	final class FileIO {
	private let buffer:[UInt8]
	private var index: Int = 0
	init(fileHandle: FileHandle = FileHandle.standardInput) {
	buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
	}
	@inline(__always) private func read() -> UInt8 {
	defer { index += 1 }
	return buffer[index]
	}
	@inline(__always) func readInt() -> Int {
	var sum = 0
	var now = read()
	var isPositive = true
	while now == 10
	|| now == 32 { now = read() } // 공백과 줄바꿈 무시
	if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
	while now >= 48, now <= 57 {
	sum = sum * 10 + Int(now-48)
	now = read()
	}
	return sum * (isPositive ? 1:-1)
	}
	@inline(__always) func readString() -> String {
	var now = read()
	while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
	let beginIndex = index-1
	while now != 10,
	now != 32,
	now != 0 { now = read() }
	return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
	}
	@inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
	var now = read()
	while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
	let beginIndex = index-1
	while now != 10,
	now != 32,
	now != 0 { now = read() }
	return Array(buffer[beginIndex..<(index-1)])
	}
	}
	let fio = FileIO()
	let N = fio.readInt()
	let M = fio.readInt()
	var arr = [Int]()
	var tree = Array(repeating: (1000000001,0), count: N*4)
	for _ in 0..<N{
	arr.append(fio.readInt())
	}
	func make_tree(from:Int, to:Int, idx:Int) -> (Int,Int){
	if from == to{
	tree[idx] = (arr[from],arr[from])
	return tree[idx]
	}
	let mid = (from+to)/2
	let l = make_tree(from: from, to: mid, idx: idx*2)
	let r = make_tree(from: mid+1, to: to, idx: idx*2+1)
	tree[idx].0 = min(l.0, r.0)
	tree[idx].1 = max(l.1, r.1)
	return tree[idx]
	}
	func read_tree(from:Int, to:Int, idx:Int, head:Int, tail:Int) -> (Int,Int){
	if to < head || tail < from{
	return (1000000001,0)
	}
	if head <= from && to <= tail{
	return tree[idx]
	}
	let mid = (from+to)/2
	let l = read_tree(from: from, to: mid, idx: idx*2, head: head, tail: tail)
	let r = read_tree(from: mid+1, to: to, idx: idx*2+1, head: head, tail: tail)
	return (min(l.0, r.0),max(l.1, r.1))
	}
	make_tree(from: 0, to: N-1, idx: 1)
	for _ in 0..<M{
	let start = fio.readInt()-1
	let end = fio.readInt()-1
	let res = read_tree(from: 0, to: N-1, idx: 1, head: start, tail: end)
	print(res.0,res.1)
	}

view raw 2357.swift hosted with ❤ by GitHub