:: Kotlin :: Segment Tree Solution
\n\n# Code\n\nclass Solution {\n    fun fallingSquares(positions: Array<IntArray>): List<Int> {\n        val posToIdx = HashMap<Double, Int>()\n        val pos 
\n\n# Code\n```\nclass Solution {\n    fun fallingSquares(positions: Array<IntArray>): List<Int> {\n        val posToIdx = HashMap<Double, Int>()\n        val pos = mutableListOf<Double>()\n\n        for (position in positions) {\n            pos.add(position[0].toDouble() + 0.1)\n            pos.add((position[0] + position[1]).toDouble() - 0.1)\n        }\n\n        pos.sort()\n\n        for (index in pos.indices) {\n            val crd = pos[index]\n            if (posToIdx.containsKey(crd)) continue\n            posToIdx.put(crd, index)\n        }\n\n        val st = SegmentTree(pos.size * 2)\n        val result = mutableListOf<Int>()\n        var m = 0\n        for (position in positions) {\n            val u = posToIdx.getOrDefault(position[0].toDouble() + 0.1, -1)\n            val v = posToIdx.getOrDefault((position[0] + position[1]).toDouble() - 0.1, -1)\n            val l = position[1]\n\n            val max = st.query(u, v)\n            st.update(u, v, max + l)\n            m = maxOf(m, max + l)\n            result.add(m)\n        }\n\n        return result\n    }\n}\n\nclass SegmentTree(val n: Int) {\n    val tree = IntArray(n * 4)\n    val lazy = IntArray(n * 4)\n\n    fun update(l: Int, r: Int, value: Int) {\n        update(0, 0, n - 1, l, r, value)\n    }\n\n    fun update(node: Int, start: Int, end: Int, l: Int, r: Int, value: Int) {\n        if (start > end || start > r || end < l) return\n        if (lazy[node] != 0) {\n            tree[node] = maxOf(tree[node], lazy[node])\n            if (start != end) {\n                lazy[node * 2 + 1] = maxOf(lazy[node * 2 + 1], lazy[node])\n                lazy[node * 2 + 2] = maxOf(lazy[node * 2 + 1], lazy[node])\n            }\n            lazy[node] = 0\n        }\n\n        if (l <= start && end <= r) {\n            tree[node] = maxOf(tree[node], value)\n            if (start != end) {\n                lazy[2 * node + 1] = maxOf(lazy[node * 2 + 1], value)\n                lazy[2 * node + 2] = maxOf(lazy[node * 2 + 1], value)\n            }\n            return\n        }\n        val mid = (start + end) / 2\n\n        update(node * 2 + 1, start, mid, l, r, value)\n        update(node * 2 + 2, mid + 1, end, l, r, value)\n\n        tree[node] = maxOf(tree[node * 2 + 1], tree[node * 2 + 2])\n    }\n\n    fun query(l: Int, r: Int): Int {\n        return query(0, 0, n - 1, l, r)\n    }\n\n    fun query(node: Int, start: Int, end: Int, l: Int, r: Int): Int {\n        if (start > end || start > r || end < l) return Int.MIN_VALUE\n        if (lazy[node] != 0) {\n            tree[node] = maxOf(tree[node], lazy[node])\n            if (start != end) {\n                lazy[node * 2 + 1] = maxOf(lazy[node * 2 + 1], lazy[node])\n                lazy[node * 2 + 2] = maxOf(lazy[node * 2 + 1], lazy[node])\n            }\n            lazy[node] = 0\n        }\n\n        if (l <= start && end <= r) {\n            return tree[node]\n        }\n        val mid = (start + end) / 2\n        val left = query(node * 2 + 1, start, mid, l, r)\n        val right = query(node * 2 + 2, mid + 1, end, l, r)\n        return maxOf(left, right)\n    }\n}\n```
['Kotlin']