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

 

11505번: 구간 곱 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

세그먼트 트리 문제다.

 

풀이

구간 합 구하기 문제와 다른 점은 세그먼트 트리의 갱신 부분에 주의할 부분이 있다는 점이다. 처음에는 단순히 기존값으로 나누고, 새로운 값으로 다시 곱해주면서 리프노드까지 도달하는 방법으로 접근했지만, 예제에서 알 수 있듯이 트리의 값이 0으로 바뀌게 되면 다음 갱신에 문제가 발생한다. 따라서 리프노드부터 먼저 갱신이 이루어지고, 루트노드까지 새로운 값으로 계산을 해주어야 한다. 

 

정답 코드

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()
let K = fio.readInt()
let MOD = 1000000007
var arr = [Int]()
var tree = Array(repeating: 1, count: N*4)
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] = arr[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)
tree[idx] = (left*right)%MOD
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 1
}
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)
return (left*right)%MOD
}
func update_tree(from n:Int, to m:Int, idx:Int, target_idx:Int, value:Int) -> Int{
if target_idx < n || m < target_idx{
return tree[idx]
}
if n == m{
tree[idx] = value
return tree[idx]
}
let mid = (n+m)/2
let left = update_tree(from: n, to: mid, idx: idx*2, target_idx: target_idx, value: value)
let right = update_tree(from: mid+1, to: m, idx: idx*2+1, target_idx: target_idx, value: value)
tree[idx] = (left*right)%MOD
return tree[idx]
}
make_tree(from: 0, to: N-1, idx: 1)
for _ in 0..<M+K{
if fio.readInt() == 1{
let B = fio.readInt()-1
let C = fio.readInt()
arr[B] = C
update_tree(from: 0, to: N-1, idx: 1, target_idx: B, value: C)
}else{
let B = fio.readInt()-1
let C = fio.readInt()-1
print(read_tree(from: 0, to: N-1, idx: 1, min: B, max: C))
}
}
view raw 11505.swift hosted with ❤ by GitHub

재귀호출 시에 범위를 반대로 적어 "틀렸습니다"를 연발했다.. 아는 유형의 문제라 방심했던 탓이다. 항상 집중해서 문제를 풀 것.

'Problem Solving > BOJ' 카테고리의 다른 글

[1306] 달려라 홍준  (0) 2023.02.18
[14428] 수열과 쿼리 16  (0) 2023.02.17
[2357] 최솟값과 최댓값  (0) 2023.02.15
[2042] 구간 합 구하기  (0) 2023.02.15
[2533] 사회망 서비스(SNS)  (0) 2023.02.13

+ Recent posts

티스토리툴바