C++ | Two Methods | Segment Tree + Discretization | Map
Map: O(n^2)\nc++\nclass Solution {\n public:\n  vector<int> fallingSquares(vector<vector<int>>& positions) {\n    vector<int> ans;\n    map<int, pair<int, int>>
* Map: O(n^2)\n```c++\nclass Solution {\n public:\n  vector<int> fallingSquares(vector<vector<int>>& positions) {\n    vector<int> ans;\n    map<int, pair<int, int>> h;\n    int max_height = 0;\n    for (int i = 0; i < positions.size(); ++i) {\n      int left = positions[i][0];\n      int right = left + positions[i][1];\n      int height = 0;\n      for (auto& it : h) {\n        if (it.first >= right) break;\n        if (it.second.first > left) {\n          height = max(height, it.second.second);\n        }\n      }\n      height += positions[i][1];\n      h[left] = {right, height};\n      max_height = max(max_height, height);\n      ans.push_back(max_height);\n    }\n    return ans;\n  }\n};\n```\n\n* SegmentTree: O(nlogn)\n```c++\nclass Solution {\n public:\n  // SegmentTree + Discretization\n  vector<int> fallingSquares(vector<vector<int>>& positions) {\n    set<int> coords;\n    for (int i = 0; i < positions.size(); ++i) {\n      coords.insert(positions[i][0]);\n      coords.insert(positions[i][0] + positions[i][1]);\n    }\n\n    int range = 0;\n    unordered_map<int, int> h;\n    for (auto& it : coords) {\n      h[it] = ++range;\n    }\n\n    int max_height = 0;\n    vector<int> ans;\n    SegmentTree<STMax> st(range);\n    ans.reserve(positions.size());\n    for (int i = 0; i < positions.size(); ++i) {\n      int left = positions[i][0];\n      int right = positions[i][0] + positions[i][1];\n      int height = st.query(h[left] + 1, h[right]) + positions[i][1];\n      st.update(h[left] + 1, h[right], height);\n      max_height = max(max_height, height);\n      ans.push_back(max_height);\n    }\n    return ans;\n  }\n};\n```
['Tree', 'C', 'C++']