문제풀이
- 초기 상태로 N ~ 1의 번호를 순서대로 세그먼트 트리의 (0 ~ N-1)인덱스에 넣느다.
- 선택한 영화의 세그먼트 트리의 인덱스를 구하고, 그 보다 큰 인덱스의 개수를 구한다.
- 선택한 영화를 세그먼트 트리의 다음 인덱스에 넣고 이를 반복한다.
주의사항
소요시간
12분
package 백준.Platinum.P4.p3653_영화수집
class SegTree(val N: Int) {
private val tree = IntArray(4 * N)
fun update(idx: Int, diff: Int, start: Int = 0, end: Int = N - 1, treeIdx: Int = 1) {
if (end < idx || idx < start) return
tree[treeIdx] += diff
if (start == end) return
val mid = (start + end) / 2
update(idx, diff, start, mid, treeIdx * 2)
update(idx, diff, mid + 1, end, treeIdx * 2 + 1)
}
fun query(left: Int, right: Int = N - 1, start: Int = 0, end: Int = N - 1, treeIdx: Int = 1): Int {
if (end < left || right < start) return 0
if (left <= start && end <= right) return tree[treeIdx]
val mid = (start + end) / 2
return query(left, right, start, mid, treeIdx * 2) + query(left, right, mid + 1, end, treeIdx * 2 + 1)
}
}
fun main() {
val sb = StringBuilder()
repeat(readln().toInt()) {
val (N, M) = readln().trim().split(" ").map(String::toInt)
val segTree = SegTree(N + M)
val idxArr = IntArray(N + 1)
var idx = 0
for (i in N downTo 1) {
idxArr[i] = idx++
segTree.update(idxArr[i], 1)
}
for (i in readln().trim().split(" ").map(String::toInt)) {
val pIdx = idxArr[i]
val nIdx = idx++
idxArr[i] = nIdx
sb.append("${segTree.query(pIdx + 1)} ")
segTree.update(pIdx, -1)
segTree.update(nIdx, 1)
}
sb.appendLine()
}
println(sb)
}