백준 9345 디지털 비디오 디스크(DVDs)
23 Jun 2021https://www.acmicpc.net/problem/9345
자기 자신의 index를 원소값으로 갖는 배열이 주어진다고 하자. 구간이 주어질 때 구간안에 구간의 시작부터 끝까지 숫자가 전부 들어있는지 아닌지 확인하는 문제이다. 예를들어 3-7 구간을 고르면 그 안에 3, 4, 5, 6, 7이 모두 들어있으면 true 아니면 false인 문제이다. 이 때 배열의 원소들은 swap 될 수 있다.
세그먼트를 써야할 것 같은데 구간안에 모두 존재하는지를 어떻게 판명해야할지 고민되는 문제였다. 먼저 각 원소값들은 중복이 되지 않기 때문에 3-7 구간을 구한다고 하면 총 5개의 원소값이 나타나게 될 것이다. 이를 활용하여 구간의 최솟값과 최댓값을 세그먼트 트리에 저장해놨다고 생각해보자. 3-7 구간에 3-7 원소가 모두 존재하면 최솟값이 결국 3이 나오고 최댓값이 7이 나오게 된다. 만약 다른 숫자가 들어있다고 생각하면 최솟값과 최댓값 중 하나가 다른 숫자가 나타나게 된다.
따라서 앞서 푼 최솟값 최댓값 문제와 동일하게 구현을 해주면 된다. 다만 업데이트가 이번에는 발생하므로 유의하자. 노드에서 양쪽 자식에 대해 업데이트를 호출한 후 양쪽 자식의 값 중 최솟값과 최댓값으로 노드의 값을 변경해주면 된다. 또한 3번과 7번 dvd를 바꾼다고 해도 실제로 dvd 케이스 안에 3번과 7번이 들어있는게 아닐 수 있다. 따라서 현재 dvd 케이스에 몇 번째 dvd가 들어있는지 배열로 관리해줘야 한다.
- 전체 코드
struct Segment {
var arr:[Int]
var tree:[(Int, Int)]
mutating func update(start: Int, end: Int, node: Int, index: Int, val: Int) {
if index < start || index > end {
return
}
if start == end {
tree[node] = (val, val)
return
}
let mid = (start+end)/2
update(start: start, end: mid, node: 2*node, index: index, val: val)
update(start: mid+1, end: end, node: 2*node+1, index: index, val: val)
tree[node] = (min(tree[2*node].0, tree[2*node+1].0), max(tree[2*node].1, tree[2*node+1].1))
}
mutating func change(a: Int, b: Int) {
arr.swapAt(a, b)
update(start: 0, end: arr.count-1, node: 1, index: a, val: arr[a])
update(start: 0, end: arr.count-1, node: 1, index: b, val: arr[b])
}
func find(start: Int, end: Int, node: Int, left: Int, right: Int) -> (Int, Int) {
if right < start || end < left {
return (100000, 0)
}
if left <= start && end <= right {
return tree[node]
}
let mid = (start+end)/2
let l = find(start: start, end: mid, node: 2*node, left: left, right: right)
let r = find(start: mid+1, end: end, node: 2*node+1, left: left, right: right)
return (min(l.0, r.0), max(l.1, r.1))
}
mutating func makeTree(start: Int, end: Int, node: Int) -> (Int, Int) {
if start == end {
tree[node] = (arr[start], arr[start])
return tree[node]
}
let mid = (start+end)/2
let l = makeTree(start: start, end: mid, node: 2*node)
let r = makeTree(start: mid+1, end: end, node: 2*node+1)
tree[node] = (min(l.0, r.0), max(l.1, r.1))
return tree[node]
}
init(n: Int) {
self.arr = [Int](0..<n)
self.tree = Array(repeating: (100000, 0), count: 4*n)
makeTree(start: 0, end: n-1, node: 1)
}
}
var str = ""
let t = Int(readLine()!)!
for _ in 0..<t {
let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0], m = nm[1]
var seg = Segment(n: n)
for _ in 0..<m {
let query = readLine()!.split(separator: " ").map{Int(String($0))!}
if query[0] == 0 {
seg.change(a: query[1], b: query[2])
}
else {
let result = seg.find(start: 0, end: n-1, node: 1, left: query[1], right: query[2])
if result.0 == query[1] && result.1 == query[2] {
str += "YES\n"
}
else {
str += "NO\n"
}
}
}
}
print(str)