[Python] Segment Tree with coordinate compression
Similar to the techniques from https://codeforces.com/blog/entry/18051\n\npython\nclass Solution:\n    def fallingSquares(self, positions: List[List[int]]) -> L
Similar to the techniques from https://codeforces.com/blog/entry/18051\n\n```python\nclass Solution:\n    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n        V = set()\n        for p, w in positions:\n            V.add(p)\n            V.add(p + w)\n        rank = {x: i for i, x in enumerate(sorted(V))}\n        \n        s, n = len(rank), 1\n        while n < s:\n            n *= 2\n        seg, lazy = [0] * (2 * n - 1), [0] * (2 * n - 1)\n        \n        def push(k, l, r):\n            if lazy[k] < 0:\n                return\n            seg[k] = lazy[k]\n            if k < n - 1:\n                lazy[k * 2 + 1] = lazy[k]\n                lazy[k * 2 + 2] = lazy[k]\n            lazy[k] = -1\n        \n        def update(a, b, x, k=0, l=0, r=n):\n            if b <= l or r <= a:\n                return\n            push(k, l, r)\n            if a <= l and r <= b:\n                lazy[k] = x\n                push(k, l, r)\n            else:\n                m = (l + r) // 2\n                update(a, b, x, k * 2 + 1, l, m)\n                update(a, b, x, k * 2 + 2, m, r)\n                seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])\n                \n        def query(a, b, k=0, l=0, r=n):\n            push(k, l, r)\n            if b <= l or r <= a:\n                return 0\n            if a <= l and r <= b:\n                return seg[k]\n            m = (l + r) // 2\n            left = query(a, b, 2 * k + 1, l, m)\n            right = query(a, b, 2 * k + 2, m, r)\n            return max(left, right)\n        \n        res, mx = [], 0\n        for p, w in positions:\n            rp, rw = rank[p], rank[p + w]\n            mh = query(rp, rw) + w\n            update(rp, rw, mh)\n            mx = max(mx, mh)\n            res.append(mx)\n        return res\n```
[]