<p>A city&#39;s <strong>skyline</strong> is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return <em>the <strong>skyline</strong> formed by these buildings collectively</em>.</p>

<p>The geometric information of each building is given in the array <code>buildings</code> where <code>buildings[i] = [left<sub>i</sub>, right<sub>i</sub>, height<sub>i</sub>]</code>:</p>

<ul>
	<li><code>left<sub>i</sub></code> is the x coordinate of the left edge of the <code>i<sup>th</sup></code> building.</li>
	<li><code>right<sub>i</sub></code> is the x coordinate of the right edge of the <code>i<sup>th</sup></code> building.</li>
	<li><code>height<sub>i</sub></code> is the height of the <code>i<sup>th</sup></code> building.</li>
</ul>

<p>You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height <code>0</code>.</p>

<p>The <strong>skyline</strong> should be represented as a list of &quot;key points&quot; <strong>sorted by their x-coordinate</strong> in the form <code>[[x<sub>1</sub>,y<sub>1</sub>],[x<sub>2</sub>,y<sub>2</sub>],...]</code>. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate <code>0</code> and is used to mark the skyline&#39;s termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline&#39;s contour.</p>

<p><b>Note:</b> There must be no consecutive horizontal lines of equal height in the output skyline. For instance, <code>[...,[2 3],[4 5],[7 5],[11 5],[12 7],...]</code> is not acceptable; the three lines of height 5 should be merged into one in the final output as such: <code>[...,[2 3],[4 5],[12 7],...]</code></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/merged.jpg" style="width: 800px; height: 331px;" />
<pre>
<strong>Input:</strong> buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
<strong>Output:</strong> [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
<strong>Explanation:</strong>
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> buildings = [[0,2,3],[2,5,3]]
<strong>Output:</strong> [[0,3],[5,0]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= buildings.length &lt;= 10<sup>4</sup></code></li>
	<li><code>0 &lt;= left<sub>i</sub> &lt; right<sub>i</sub> &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>1 &lt;= height<sub>i</sub> &lt;= 2<sup>31</sup> - 1</code></li>
	<li><code>buildings</code> is sorted by <code>left<sub>i</sub></code> in&nbsp;non-decreasing order.</li>
</ul>

/* Scanline: 
### Detailed Walkthrough of the Implementation
- **Data Structures**:
  - A `map<int, vector<pair<int,bool>>>` named `mp` is used to store building events, where each key represents a position (either the start or end of a building) and the value is a vector of pairs. Each pair contains the building height and a boolean flag indicating if it's the start (`true`) or end (`false`) of a building.
  - A `multiset<int>` named `st` is used to keep track of the current active building heights. This structure helps in efficiently finding the current maximum height.
  - A `vector<vector<int>>` named `res` stores the resulting skyline points.
- **Building Event Mapping**:
  - Iterate through each building in the input `buildings`. For each building:
    - The left edge (start position) and right edge (end position) are recorded in the map `mp` with corresponding heights and flags. The height at the start position is marked with `true` (indicating a rising edge), and at the end position with `false` (indicating a falling edge).
- **Processing Events**:
  - Iterate through the sorted keys of the map `mp` (positions):
    - For each position, iterate through the list of pairs (height and flag):
      - If the flag is `true`, add the height to the multiset `st`.
      - If the flag is `false`, remove one occurrence of the height from `st`.
    - Determine the current maximum height (`H`) by checking the last element in the multiset `st`. If `st` is empty, `H` is set to 0.
    - If the current height `H` differs from the last recorded height in `res`, add the current position and height to `res`.
- **Return**:
  - The vector `res` containing the skyline points is returned.

### Key Ideas
- Use of a `map` to handle both rising and falling edges of buildings efficiently, sorted by position.
- A `multiset` is used to maintain the current set of active building heights, allowing efficient insertion, deletion, and retrieval of the maximum height.
- The skyline changes only when the maximum height changes, which is detected by comparing the current maximum height with the last recorded height.

### Time Complexity
- **Insertion and Deletion in `map` and `multiset`**: Each building edge is inserted and removed from the `multiset`, and accessing the maximum height takes O(log n) time for each event. Since there are at most `2n` events (two for each building), the overall time complexity is O(n log n), where `n` is the number of buildings.

### Space Complexity
- **Map and Multiset Storage**: The space complexity is O(n) due to storing events in the map and active building heights in the multiset.

### Potential Optimizations
- **Coordinate Compression**: If the range of positions is very large, we could use coordinate compression to reduce the range of the position keys in the map, potentially speeding up access times.
- **Sweep Line Algorithm**: The current implementation is already efficient using a sweep line approach. Further optimization could be achieved by using a balanced binary search tree instead of a multiset, though the difference in practical performance might be minimal.
*/
// class Solution {
// public:
//     vector<vector<int>> getSkyline(vector<vector<int>>& buildings) 
//     {
//         map<int, vector<pair<int,bool>>> mp; // pos->{height, flag}
//         for (auto building: buildings)
//         {
//             // Add the position, left edge rising edge, right edge falling edge
//             mp[building[0]].push_back({building[2], true});
//             mp[building[1]].push_back({building[2], false});
//         }
        
//         multiset<int>st;
//         vector<vector<int>>res;
//         for (auto& [pos, pairs]: mp)
//         {
//             // Iterate through all the rising and falling edges at this position
//             for (auto& [height, flag]: pairs)
//             {
//                 if (flag == true)
//                     st.insert(height);
//                 else
//                     st.erase(st.find(height));                
//             }

//             // At current position, what is the largest height?
//             int H = st.empty() ? 0: *st.rbegin();

//             // res should only contain non-duplicated coordinates
//             if (res.empty() || res.back()[1]!=H)
//                 res.push_back({pos, H});
//         }

//         return res;
//     }
// };

/* Segment tree:
此题的线段树解法，是以370.Range-Addition的懒标记版本为基础，稍加改动。

首先，不同于307或者370中已经给出了nums数组。此题中给出的是建筑物高度拐点的pos。这些pos的绝对值对我们而言其实是没有意义的，我们只关心这些pos的相对顺序，也就是idx。所以我们其实需要构造两个映射，pos2idx和idx2pos，方便我们做转换。转换之后，每个builiding相当于一个区间更新。特别注意，如果一个building对应的索引区间是[i:j]，那么我们只更新区间[i:j-1]。也就是说，线段树中的每个叶子节点的单点info，代表的其实是[i:i+1)这段左闭右开的小区间。

然后我们设计一下SegTreeNode的数据结构。除了常规的left,right,start,end之外，此时节点的info表示的是该区间内出现的高度最大值。注意，不一定整个区间都是该恒定的高度。此外，该节点的tag是一个bool量，表示该区间的高度是否都是相同的（也就是等于info）。tag为true时说明我们能断言整个区间的信息是一致的，我们不需要下沉去更新每一块更细的区间。下文会详细说明。

初始化函数init(root, 0, n-1)不需要特别的改动。其中n就是离散化之后有多少个数据点。初始化时，每个节点的info设置为0，tag设置为false。

区间更新函数updateRange(node, a, b, val)是本题的重点，意思是将区间[a,b]里的所有数据点的最大值更新为val（如果原最大值小于val的话）。我们分几种情况讨论：

边界条件：[a,b]与该节点区间互斥，直接return。
边界条件：该节点的区间是单点，那么node->info = max(node->info, val)然后return
边界条件：如果该节点的区间包含在[a,b]内，并且node->info <= val，说明该节点区间的数据点可以统一更新为val。并且我们就设置tag标记true，根据之前的分析，我们可以直接返回而不用下沉去更新更细节的区间。
其他情况下，我们就递归处理updateRange(node->left, a, b, val) && updateRange(node->right, a, b, val)。但是递归之前，我们别忘了查看当前的tag是否为true。如果是的话，说明当前节点的区间不再有统一的高度，我们需要去掉tag的标记，并且将其影响传递给两个子区间，即
        if (node->tag == 1) // if current node tagged lazy, push information down
        {
            node->tag = 0;            
            node->left->info = node->info;
            node->right->info = node->info;
            node->left->tag = 1;
            node->right->tag = 1;            
        }   
对于此题，我们其实不需要写区间查询的函数。因为我们最终输出的结果，会要求遍历线段树的每一个节点，写个DFS即可。当然，如果遍历到某个区间的tag依然为true时，其实可以不用继续深入下去，直接输出该区间的信息。最终输出的结果需要整理一下，如果相邻的叶子节点的高度相同，我们再做一下归并。

另外补充一点，我们将所有的building按照高度从小到大排序一遍，会使带有懒标签的线段树代码跑得更快。这是因为在updateRange时有更大的概率触发下面这个条件，使得我们只需要标记lazy tag并立即返回：

if (a <= node->start && node->end <=b && val >= node->info) 
{... return; }
*/
// 支持动态开点
class SegTree
{
    public:
    int start,end,status;
    SegTree* left;
    SegTree* right;
    SegTree(int a, int b, int s):start(a),end(b),status(s),left(nullptr),right(nullptr){}

    void remove(SegTree* &node)
    {
        if (node == nullptr) return;
        remove(node->left);
        remove(node->right);
        delete node;
        node = nullptr;
        return;            
    }

    void setStatus(int a, int b, int s)
    {
        if (a>=end || b<=start)
            return;
        if (a<=start && b>=end && s>=status)
        {
            remove(left);
            remove(right);
            status = s;
            return;
        }
        if (a<=start && b>=end && s<status && left==nullptr)
            return;
        if (left==nullptr)
        {
            int mid = start+(end-start)/2;
            left = new SegTree(start,mid,status);
            right = new SegTree(mid,end,status);
        }
        left->setStatus(a,b,s);
        right->setStatus(a,b,s);
        status = max(left->status,right->status);            
    }
};

class Solution {
public:
    vector<vector<int>>results;
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) 
    {
        if (buildings.size()==0) return {};
        
        SegTree* root = new SegTree(0,INT_MAX,0);
        for (auto q:buildings)
            root->setStatus(q[0],q[1],q[2]);
        
        DFS(root);
        if (results.back()[1]!=0) results.push_back({INT_MAX,0});
        
        vector<vector<int>>filteredResults;
        for (auto p: results)
        {
            if (filteredResults.size()!=0 && p[1]==filteredResults.back()[1])
                continue;
            filteredResults.push_back({p[0],p[1]});
        }
        if (filteredResults.size()!=0 && filteredResults[0][1]==0) filteredResults.erase(filteredResults.begin());
        return filteredResults;
    }
    
    void DFS(SegTree* node)
    {        
        if (node->left==NULL)
            results.push_back({node->start,node->status});
        else
        {
            DFS(node->left);
            DFS(node->right);
        }
    }
};


/* Sorted container: 
My implementation does not pass all test cases
*/
// class Solution {
// public:
//     vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
//         mp<int, int> mp;  // mp to store the x-coordinate and height
//         vector<vector<int>> result;

//         // Process the buildings one by one
//         for(const auto & b : buildings){
//             int start = b[0], end = b[1], height = b[2];

//             // Update the skyline with the new building's start point
//             auto left = mp.upper_bound(start);
//             auto right = mp.upper_bound(end);
//             int prevHeight = INT_MAX;
//             bool startUsed = false;

//             // Does the building extablish a new left coordinate?
//             if(left == mp.begin()) {
//                 // Current building is the leftmost then need to add
//                 mp[start] = height;
//                 left = mp.begin();
//             }else{
//                 // Current building's left coordinate is lower, need to add
//                 if(prev(left)->second < height){
//                     prevHeight = prev(left)->second;
//                     mp[start] = height;
//                     startUsed = true;
//                     left = prev(left);
//                 }
//             }

//             // Range of the building index: shall we update or remove previous coordinates?
//             while (left != right) {
//                 if(left->second < height){
//                     // Shall we remove this coordinate or update it?
//                     if(startUsed){
//                         left = mp.erase(left);
//                     }else{
//                         prevHeight = left->second;
//                         mp[left->first] = height;
//                         startUsed = true;
//                         left++;
//                     }
//                 } else {
//                     ++left;
//                 }
//             }

//             if(right == mp.end()){
//                 mp[end] = 0;
//             }else{
//                 if(prevHeight < height){
//                     mp[end] = prevHeight;
//                 }
//             }
//         }

//         // Convert mp to result vector, ensuring unique heights
//         int prev_height = 0;
//         for (const auto& [key, value] : mp) {
//             if (value != prev_height) {
//                 result.push_back({key, value});
//                 prev_height = value;
//             }
//         }

//         return result;
//     }
// };
38503