C++ discretization + Segment Tree O(nlog(n)) time 29ms
\nclass Solution {\n    vector<int> vec;\n    int getId(int x) {\n        return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;\n    }\n    int m;\n 
```\nclass Solution {\n    vector<int> vec;\n    int getId(int x) {\n        return lower_bound(vec.begin(), vec.end(), x) - vec.begin() + 1;\n    }\n    int m;\n    int seg[2005 * 4], lazy[2005 * 4];\n    \n    void build(int rt, int left, int right) {\n        seg[rt] = 0, lazy[rt] = -1;\n        if (left == right) return;\n        int mid = (left + right) / 2;\n        build(rt * 2, left, mid);\n        build(rt * 2 + 1, mid + 1, right);\n    }\n    \n    void add(int rt, int left, int right, int L, int R, int val) {\n        if (L <= left && right <= R) {\n            seg[rt] = lazy[rt] = val;\n            return;\n        }\n        pushDown(rt, left, right);\n        \n        int mid = (left + right) / 2;\n        \n        if (L <= mid) add(rt * 2, left, mid, L, R, val);\n        if (R > mid) add(rt * 2 + 1, mid + 1, right, L, R, val);\n        \n        seg[rt] = max(seg[rt * 2], seg[rt * 2 + 1]);\n    }\n    \n    \n    void pushDown(int rt, int left, int right) {\n        // use lazy symbol to reduce the segment tree traverse, only update the son when needed\n        if (lazy[rt] != -1) {\n            seg[rt * 2] = lazy[rt * 2] = lazy[rt * 2 + 1] = seg[rt * 2 + 1] = lazy[rt];\n            lazy[rt] = -1;\n        }\n    }\n    \n    int query(int rt, int left, int right, int L, int R) {\n         if (L <= left && right <= R) {\n            return seg[rt];\n        }\n        pushDown(rt, left, right);\n        \n        int mid = (left + right) / 2;\n        \n        int res = -1;\n        if (L <= mid) res = max(res, query(rt * 2, left, mid, L, R));\n        if (R > mid) res = max(res, query(rt * 2 + 1, mid + 1, right, L, R));\n        \n        return res;\n    }\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        int n = positions.size();\n        \n        for (int i = 0; i < n; i++) {\n            vec.push_back(positions[i].first);\n            vec.push_back(positions[i].first + positions[i].second - 1);\n        }\n        \n        \n        //discretization\n        sort(vec.begin(), vec.end());\n        vec.erase(unique(vec.begin(), vec.end()), vec.end());\n        \n        m = vec.size();\n        \n        //build tree\n        build(1, 1, m);\n        \n        vector<int> res;\n        int curMax = 0;\n        \n        //insert segment to tree and query\n        for (int i = 0; i < n; i++) {\n            \n            //use discretization to reduce the size of segment tree\n            int l = getId(positions[i].first);\n            int r = getId(positions[i].first + positions[i].second - 1);\n            \n            \n            // query the maxHeight from l to r\n            int segMax = query(1, 1, m, l, r);\n            \n            int newHeight = segMax + positions[i].second;\n            \n            // add new height to segment tree from l to r\n            add(1, 1, m, l, r, newHeight);\n                \n            curMax = max(curMax, newHeight);\n            \n            res.push_back(curMax);\n        }\n        \n        return res;\n    }\n};\n```
[]