O(nlogn) C++ Segment Tree
\nclass Solution {\npublic:\n  int n;\n  vector<int> height, lazy;\n\n  void push_up(int i) {\n    height[i] = max(height[i*2], height[i*2+1]);\n  }\n\n  void p
```\nclass Solution {\npublic:\n  int n;\n  vector<int> height, lazy;\n\n  void push_up(int i) {\n    height[i] = max(height[i*2], height[i*2+1]);\n  }\n\n  void push_down(int i) {\n    if (lazy[i]) {\n        lazy[i*2] = lazy[i*2+1] = lazy[i];\n        height[i*2] = height[i*2+1] = lazy[i];\n        lazy[i] = 0;\n    }\n  }\n\n  void update(int i, int l, int r, int L, int R, int val) {\n    if (L <= l && r <= R) {\n      height[i] = val;\n      lazy[i] = val;\n      return;\n    }\n    push_down(i);\n    int mid = l + (r-l)/2;\n    if (L < mid) update(i*2, l, mid, L, R, val);\n    if (R > mid) update(i*2+1, mid, r, L, R, val);\n    push_up(i);\n  }\n\n  int query(int i, int l, int r, int L, int R) {\n    if (L <= l && r <= R) return height[i];\n    push_down(i);\n    int res = 0;;\n    int mid = l + (r-l)/2;\n    if (L < mid) res = max(res, query(i*2, l, mid, L, R));\n    if (R > mid) res = max(res, query(i*2+1, mid, r, L, R));\n    return res;\n  }\n\n  vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n    vector<int> a;\n    for (auto& p : positions) {\n      a.push_back(p.first);\n      a.push_back(p.first+p.second);\n    }\n    sort(a.begin(), a.end());\n    n = unique(a.begin(), a.end()) - a.begin();\n    a.resize(n);\n    \n    height.resize(n<<2, 0);\n    lazy.resize(n<<2, 0);\n    vector<int> res;\n    for (auto& p : positions) {\n      int l = lower_bound(a.begin(), a.end(), p.first) - a.begin();\n      int r = lower_bound(a.begin(), a.end(), p.first+p.second) - a.begin();\n      int maxh = query(1, 0, n, l, r);\n      update(1, 0, n, l, r, maxh+p.second);\n      res.push_back(query(1, 0, n, 0, n));\n    }\n    return res;\n  }\n};\n```
[]