[伯俊10868-Kotlin]最高価格


質問リンク
  • セグメントツリーキャビティの画像
  • import java.io.BufferedReader
    import java.io.BufferedWriter
    import kotlin.math.min
    import kotlin.math.pow
    
    private lateinit var bufferedReader: BufferedReader
    private lateinit var bufferedWriter: BufferedWriter
    private lateinit var input: MutableList<Int>
    private lateinit var segTree: Array<Int>
    
    fun main() {
        bufferedReader = System.`in`.bufferedReader()
        bufferedWriter = System.out.bufferedWriter()
    
        // 1. get n, m
        val (n, m) = bufferedReader
            .readLine()
            .split(" ")
            .map { it.toInt() }
    
        // 2. get input
        input = mutableListOf()
        for (i in 0 until n) {
            input.add(bufferedReader.readLine().toInt())
        }
    
        // 3. construct segTree
        val segTreeSize = getSegTreeSize(n)
        segTree = Array(2 * segTreeSize - 1) { Int.MAX_VALUE }
        constructSegTree(0, n - 1, 0)
    
        // 4. get (a, b)
        for (i in 0 until m) {
            val (a, b) = bufferedReader
                .readLine()
                .split(" ")
                .map { it.toInt() }
            val answer = rangeMinQuery(a - 1, b - 1, 0, n - 1, 0)
            bufferedWriter.write("$answer\n")
        }
        bufferedReader.close()
        bufferedWriter.close()
    }
    
    fun getSegTreeSize(n: Int): Int {
        var exponent = 1.0
        while (n > 2.0.pow(exponent)) {
            exponent++
        }
        return 2.0.pow(exponent).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] = min(segTree[2 * pos + 1], segTree[2 * pos + 2])
    }
    
    fun rangeMinQuery(qLow: Int, qHigh: Int, low: Int, high: Int, pos: Int): Int {
        if (qLow <= low && qHigh >= high) return segTree[pos]
        if (qLow > high || qHigh < low) return Int.MAX_VALUE
    
        val mid = (low + high) / 2
        return min(
            rangeMinQuery(qLow, qHigh, low, mid, 2 * pos + 1),
            rangeMinQuery(qLow, qHigh, mid + 1, high, 2 * pos + 2)
        )
    }