https://www.acmicpc.net/problem/14428
14428번: 수열과 쿼리 16
길이가 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
세그먼트 트리 문제다.
풀이
기본적인 세그먼트 트리 문제다. 단, 이번에는 인덱스를 반환하는 것이 목적이므로, 각 노드에는 인덱스가 담기고, 노드의 값은 수열의 값을 비교하여 담아주면 된다.
트리의 값을 읽어올 때, 인덱스가 1부터 시작하므로 수열의 맨 앞에 입력 가능한 범위 밖의 값인 1,000,000,001을 담는다. 이후 범위 밖의 값을 조회하게 될 때 0번 인덱스를 반환하여 대소비교에 영향을 주지 않게 한다.
트리의 갱신은 지난번 구간 곱 구하기 문제와 동일하게 수열의 값을 먼저 갱신한 뒤 정해진 구간 내의 리프노드부터 루트노드까지 트리의 갱신을 시도하면 된다.
정답 코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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() | |
| var tree = Array(repeating: 0, count: (N+1)*4) | |
| var arr = [1000000001] | |
| for _ in 0..<N{ | |
| arr.append(fio.readInt()) | |
| } | |
| func make_tree(from n:Int, to m:Int, idx:Int) -> Int{ | |
| if n == m{ | |
| tree[idx] = n | |
| return tree[idx] | |
| } | |
| let mid = (n+m)/2 | |
| let left = make_tree(from: n, to: mid, idx: idx*2) | |
| let right = make_tree(from: mid+1, to: m, idx: idx*2+1) | |
| if arr[left] == arr[right]{ | |
| tree[idx] = left<right ? left:right | |
| }else { | |
| tree[idx] = arr[left]<arr[right] ? left:right | |
| } | |
| return tree[idx] | |
| } | |
| func read_tree(from n:Int, to m:Int, idx:Int, min:Int, max:Int) -> Int{ | |
| if m < min || max < n{ | |
| return 0 | |
| } | |
| if min <= n && m <= max{ | |
| return tree[idx] | |
| } | |
| let mid = (n+m)/2 | |
| let left = read_tree(from: n, to: mid, idx: idx*2, min: min, max: max) | |
| let right = read_tree(from: mid+1, to: m, idx: idx*2+1, min: min, max: max) | |
| if arr[left] == arr[right]{ | |
| return left<right ? left:right | |
| }else { | |
| return arr[left]<arr[right] ? left:right | |
| } | |
| } | |
| func update_tree(from n:Int, to m:Int, idx:Int, target_idx:Int) -> Int{ | |
| if target_idx < n || m < target_idx{ | |
| return tree[idx] | |
| } | |
| if n==m{ | |
| return tree[idx] | |
| } | |
| let mid = (n+m)/2 | |
| let left = update_tree(from: n, to: mid, idx: idx*2, target_idx: target_idx) | |
| let right = update_tree(from: mid+1, to: m, idx: idx*2+1, target_idx: target_idx) | |
| if arr[left] == arr[right]{ | |
| tree[idx] = left<right ? left:right | |
| }else { | |
| tree[idx] = arr[left]<arr[right] ? left:right | |
| } | |
| return tree[idx] | |
| } | |
| make_tree(from: 1, to: N, idx: 1) | |
| let M = fio.readInt() | |
| for _ in 0..<M{ | |
| if fio.readInt() == 1{ | |
| let idx = fio.readInt() | |
| let value = fio.readInt() | |
| arr[idx] = value | |
| update_tree(from: 1, to: N, idx: 1, target_idx: idx) | |
| }else{ | |
| let min = fio.readInt() | |
| let max = fio.readInt() | |
| print(read_tree(from: 1, to: N, idx: 1, min: min, max: max)) | |
| } | |
| } |
'Problem Solving > BOJ' 카테고리의 다른 글
| [14438] 수열과 쿼리 17 (0) | 2023.02.20 |
|---|---|
| [1306] 달려라 홍준 (0) | 2023.02.18 |
| [11505] 구간 곱 구하기 (0) | 2023.02.16 |
| [2357] 최솟값과 최댓값 (0) | 2023.02.15 |
| [2042] 구간 합 구하기 (0) | 2023.02.15 |
