Solution
C++ []\n#include <vector>\n#include <algorithm>\n#include <iterator>\n\nstruct SegmentTree {\n\n    SegmentTree(int n) : n(n) {\n        size = 1;\n        whil
```C++ []\n#include <vector>\n#include <algorithm>\n#include <iterator>\n\nstruct SegmentTree {\n\n    SegmentTree(int n) : n(n) {\n        size = 1;\n        while (size < n) {\n            size <<= 1;\n        }\n        tree.resize(2*size);\n        lazy.resize(2*size);\n    }\n\n    void add_range(int l, int r, int h) {\n        l += size;\n        r += size;\n\n        tree[l] = max(tree[l], h);\n        tree[r] = max(tree[r], h);\n        if (l != r) {\n            if (!(l & 1)) {\n                lazy[l+1] = max(lazy[l-1], h);\n            }\n            if (r & 1) {\n                lazy[r-1] = max(lazy[r-1], h);\n            }\n        }\n        l >>= 1;\n        r >>= 1;\n        while (l != r) {\n            tree[l] = max(tree[2*l], tree[2*l + 1]);\n            tree[r] = max(tree[2*r], tree[2*r + 1]);\n            if (l / 2 != r / 2) {\n                if (!(l & 1)) {\n                    lazy[l+1] = max(lazy[l+1], h);\n                }\n                if (r & 1) {\n                    lazy[r-1] = max(lazy[r-1], h);\n                }\n            }\n            l >>= 1;\n            r >>= 1;\n        }\n        while (l > 0) {\n            tree[l] = max(tree[2*l], tree[2*l + 1]);\n            l >>= 1;\n        }\n    }\n    int max_range(int l, int r) {\n        l += size;\n        r += size;\n\n        int max_val = max(tree[l], tree[r]);\n        while (l / 2 != r / 2) {\n            if (!(l & 1)) {\n                max_val = max(tree[l + 1], max_val);\n                max_val = max(lazy[l + 1], max_val);\n            }\n            if (r & 1) {\n                max_val = max(tree[r - 1], max_val);\n                max_val = max(lazy[r - 1], max_val);\n            }\n            max_val = max(max_val, lazy[l]);\n            max_val = max(max_val, lazy[r]);\n\n            l >>= 1;\n            r >>= 1;\n        }\n        max_val = max(max_val, lazy[r]);\n\n        while (l / 2 > 0) {\n            max_val = max(lazy[l], max_val);\n            l >>= 1;\n        }\n        return max_val;\n    }\n    int global_max() {\n        return max_range(0, n-1);\n    }\n    int size;\n    int n;\n    vector<int> tree;\n    vector<int> lazy;\n};\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<vector<int>>& positions) {\n        \n        vector<int> points;\n        for (const auto& rect: positions) {\n            points.push_back(rect[0]);\n            points.push_back(rect[0] + rect[1] - 1);\n        }\n        sort(begin(points), end(points));\n        auto new_end = unique(begin(points), end(points));\n        points.resize(distance(begin(points), new_end));\n\n        SegmentTree st(points.size());\n\n        vector<int> results;\n\n        int max_height = 0;\n        for (const auto& rect: positions) {\n            int x_1 = rect[0];\n            int x_2 = rect[0] + rect[1] - 1;\n\n            int l = distance(begin(points), lower_bound(begin(points), end(points), x_1));\n            int r = distance(begin(points), lower_bound(begin(points), end(points), x_2));\n\n            int cur_height = st.max_range(l, r);\n            int new_height = rect[1] + cur_height;\n            max_height = max(new_height, max_height);\n            st.add_range(l, r, new_height);\n            results.push_back(max_height);\n        }\n        return results;\n    }\n};\n```\n\n```Python3 []\nclass Solution:\n    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n        height = [0]\n        pos = [0]\n        res = []\n        max_h = 0\n        for left, side in positions:\n            i = bisect.bisect_right(pos, left)\n            j = bisect.bisect_left(pos, left + side)\n            high = max(height[i - 1:j] or [0]) + side\n            pos[i:j] = [left, left + side]\n            height[i:j] = [high, height[j - 1]]\n            max_h = max(max_h, high)\n            res.append(max_h)\n        return res\n```\n\n```Java []\nclass Solution {\n    public List<Integer> fallingSquares(int[][] positions)\n    {\n        int[] ends = new int[positions.length*2];\n        for(int i=0; i<positions.length; i++)\n        {\n            ends[i*2+0] = positions[i][0];\n            ends[i*2+1] = positions[i][0]+positions[i][1];\n        }\n        Arrays.sort(ends);\n\n        int[] ceilings = new int[ends.length-1];\n        int maxAll = 0;\n        ArrayList<Integer> results = new ArrayList<>();\n        for(int i=0; i<positions.length; i++)\n        {\n            int X = positions[i][0];\n            int x = Arrays.binarySearch(ends, X);\n            assert x>=0;\n            int maxCeiling = 0;\n            int Y = X + positions[i][1];\n            for(int y=x; ends[y]<Y; y++)\n                maxCeiling = Math.max(maxCeiling, ceilings[y]);\n            maxCeiling += (Y-X);\n            for(int y=x; ends[y]<Y; y++)\n                ceilings[y] = maxCeiling;\n            maxAll = Math.max(maxAll, maxCeiling);\n            results.add(maxAll);\n        }\n        return results;\n    }\n}\n```\n
['C++', 'Java', 'Python3']