C++ O(NlogN) TreeMap
In this question squares are only added without being removed, so a new, higher square will cover all squares under it. These squares are no longer needed to co
In this question squares are only added without being removed, so a new, higher square will cover all squares under it. These squares are no longer needed to consider, so we could just remove them from our records of heights. \nI used a ```TreeMap``` to record all useful heights. Every square adds 2 points to the record. Once a point is visited, it will be removed from the record, which gives us O(N) times for visiting. Searching the positions of new points takes O(logN), so the whole time complexity is O(NlogN).\n\n```C++\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<pair<int, int>>& positions) {\n        map<int, int> heights;\n        heights[INT_MIN] = heights[INT_MAX] = 0;\n        \n        int maxh = 0;\n        vector<int> res;\n        for (auto p : positions) {\n            int left = p.first, side = p.second, right = left + side;\n            auto lt = --heights.upper_bound(left), rt = heights.lower_bound(right);\n            int lh = 0, rh = 0;\n            for (auto it = lt; it != rt; ) {\n                rh = it->second;\n                lh = max(lh, it->second);\n                if (it == lt) it ++;\n                else it = heights.erase(it);\n            }\n            lh += side;\n            heights[left] = lh;\n            heights[right] = rh;\n            maxh = max(maxh, lh);\n            res.push_back(maxh);\n        }\n        return res; \n    }\n};\n```
[]