[Kotlin] Segment Tree + Cumulative Count Map 60L
\n// Based on https://www.youtube.com/watch?v=Oq2E2yGadnU\nclass MajorityChecker(arr: IntArray) {\n\n    private val n = arr.size\n    private val data = Array<
```\n// Based on https://www.youtube.com/watch?v=Oq2E2yGadnU\nclass MajorityChecker(arr: IntArray) {\n\n    private val n = arr.size\n    private val data = Array<Counts?>(2 * n) { null }\n\n    init {\n        for (i in arr.indices) {\n            data[n + i] = Counts(mapOf(arr[i] to 1))\n        }\n\n        for (idx in (n - 1) downTo 1) {\n            data[idx] = data[2 * idx]!! + data[2 * idx + 1]!!\n        }\n    }\n\n    fun query(left: Int, right: Int, threshold: Int): Int {\n        val querySTree = queryTree(left, right)\n\n        return querySTree.countMap\n            .takeIf { it.isNotEmpty() }\n            ?.let { it.entries.maxBy { it.value } }\n            ?.takeIf { (_, count) -> count >= threshold }\n            ?.key\n            ?: -1\n    }\n\n    private fun queryTree(left: Int, right: Int): Counts {\n        var left = left + n\n        var right = right + n + 1\n        var result = Counts()\n        while (left < right) {\n            if (left % 2 == 1) {\n                result += data[left++]!!\n            }\n            if (right % 2 == 1) {\n                result += data[--right]!!\n            }\n            left /= 2\n            right /= 2\n        }\n        return result\n    }\n\n    private data class Counts(val countMap: Map<Int, Int> = emptyMap()) {\n        operator fun plus(right: Counts): Counts {\n            return when {\n                right.countMap.isEmpty() -> this\n                countMap.isEmpty() -> right\n                else -> {\n                    val combinedMap = (right.countMap.keys + countMap.keys)\n                        .associateWith { right.countMap.getOrDefault(it, 0) + countMap.getOrDefault(it, 0) }\n                    Counts(combinedMap)\n                }\n            }\n        }\n    }\n}\n```
[]