98% beat using Segment Tree
IntuitionStore in a segment tree heights of left edges of each cube.
when adding a cube to the board, update all cubes in the x-range of the cube.ApproachComple
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Store in a segment tree heights of left edges of each cube.
when adding a cube to the board, update all cubes in the x-range of the cube.
# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
$$O(nlog(n))$$

- Space complexity:
$$O(n)$$

# Code
```cpp []
class SegmentTree {
    vector<int> tree, lazy;
    int size;

public:
    SegmentTree(int n) {
        size = n;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }

    void rangeUpdate(int node, int start, int end, int l, int r, int val) {
        if (lazy[node] != 0) {
            tree[node] = max(tree[node], lazy[node]); 
            if (start != end) { 
                lazy[2 * node + 1] = max(lazy[node],lazy[2 * node + 1]);
                lazy[2 * node + 2] = max(lazy[node],lazy[2 * node + 2]);
            }
            lazy[node] = 0; 
        }

        if (start > r || end < l) return;

        if (start >= l && end <= r) { 
            tree[node] = max(tree[node],val);
            if (start != end) {
                lazy[2 * node + 1] = max(val,lazy[2 * node + 1]);
                lazy[2 * node + 2] = max(val,lazy[2 * node + 2]);
            }
            return;
        }

        int mid = (start + end) / 2;
        rangeUpdate(2 * node + 1, start, mid, l, r, val);
        rangeUpdate(2 * node + 2, mid + 1, end, l, r, val);
        tree[node] = max(tree[2 * node + 1],tree[2 * node + 2]); 
    }

    int rangeQuery(int node, int start, int end, int l, int r) {
        if (lazy[node] != 0) {
            tree[node] = max(tree[node], lazy[node]);
            if (start != end) { 
                lazy[2 * node + 1] = max(lazy[node],lazy[2 * node + 1]);
                lazy[2 * node + 2] = max(lazy[node],lazy[2 * node + 2]);
            }
            lazy[node] = 0; 
        }

        if (start > r || end < l) return 0;

        if (start >= l && end <= r) return tree[node];

        int mid = (start + end) / 2;
        return max(rangeQuery(2 * node + 1, start, mid, l, r),
               rangeQuery(2 * node + 2, mid + 1, end, l, r));
    }


    void update(int l, int r, int val) {
        rangeUpdate(0, 0, size - 1, l, r, val);
    }

    int query(int l, int r) {
        return rangeQuery(0, 0, size - 1, l, r);
    }
};

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> x_values;
        for(auto& p:positions)
            x_values.push_back(p[0]);
        sort(x_values.begin(),x_values.end());
        SegmentTree t(size(x_values));

        vector<int> result;
        for(auto& p:positions){
            int x = p[0], cube_size = p[1];
            int left_indx =  lower_bound(x_values.begin(),x_values.end(),x)-x_values.begin();
            int right_indx = lower_bound(x_values.begin(),x_values.end(),x+cube_size)-x_values.begin()-1;
            int height = t.query(left_indx,right_indx) + cube_size;

            t.update(left_indx,right_indx,height);
            if (result.empty())
                result.push_back(height);
            else 
                result.push_back(max(height,result.back()));
        }
        return result;

    }
};
```
['C++']