[백준 11505 - Kotlin] 구간 곱 구하기

문제링크

• 이 문제 를 이해했다면 쉽게 풀 수 있는 문제 입니다.

import java.io.BufferedReader
import java.io.BufferedWriter
import kotlin.math.pow

private lateinit var bufferedReader: BufferedReader
private lateinit var bufferedWriter: BufferedWriter
private lateinit var input: Array<Long>
private lateinit var segTree: Array<Long>

fun main() {
    bufferedReader = System.`in`.bufferedReader()
    bufferedWriter = System.out.bufferedWriter()

    // 1. get (n, m, k)
    val (n, m, k) = bufferedReader
        .readLine()
        .split(" ")
        .map { it.toInt() }

    // 2. get input
    input = Array(n) { 0 }
    for (i in 0 until n) {
        input[i] = bufferedReader.readLine().toLong()
    }

    // 3. construct segment tree
    val segTreeSize = getSegTreeSize(n)
    segTree = Array(2 * segTreeSize + 1) { 1 }
    constructSegTree(0, n - 1, 0)

    // 4. get (a, b, c)
    for (i in 0 until (m + k)) {
        val (a, b, c) = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }

        if (a == 1) {
            updateSegTree(b - 1, c.toLong(), 0, n - 1, 0)
        } else {
            val answer = rangeMultiplyQuery(b - 1, c - 1, 0, n - 1, 0)
            bufferedWriter.write("$answer\n")
        }
    }

    bufferedReader.close()
    bufferedWriter.close()
}

fun getSegTreeSize(n: Int): Int {
    var exponential = 0
    while (n > 2.0.pow(exponential)) {
        exponential++
    }
    return 2.0.pow(exponential).toInt()
}

fun constructSegTree(low: Int, high: Int, pos: Int) {
    if (low == high) {
        segTree[pos] = input[low]
        return
    }

    val mid = (low + high) / 2
    constructSegTree(low, mid, 2 * pos + 1)
    constructSegTree(mid + 1, high, 2 * pos + 2)
    segTree[pos] = segTree[2 * pos + 1] * segTree[2 * pos + 2] % 1_000_000_007
}

fun updateSegTree(index: Int, value: Long, low: Int, high: Int, pos: Int) {
    if (index < low || index > high) return
    if (low == high) {
        segTree[pos] = value
        return
    }

    val mid = (low + high) / 2
    updateSegTree(index, value, low, mid, 2 * pos + 1)
    updateSegTree(index, value, mid + 1, high, 2 * pos + 2)
    segTree[pos] = segTree[2 * pos + 1] * segTree[2 * pos + 2] % 1_000_000_007
}

fun rangeMultiplyQuery(qLow: Int, qHigh: Int, low: Int, high: Int, pos: Int): Long {
    if (qLow <= low && qHigh >= high) return segTree[pos]
    if (qLow > high || qHigh < low) return 1

    val mid = (low + high) / 2
    return rangeMultiplyQuery(qLow, qHigh, low, mid, 2 * pos + 1) * rangeMultiplyQuery(qLow, qHigh, mid + 1, high, 2 * pos + 2) % 1_000_000_007
}