<p>There are several squares being dropped onto the X-axis of a 2D plane.</p>

<p>You are given a 2D integer array <code>positions</code> where <code>positions[i] = [left<sub>i</sub>, sideLength<sub>i</sub>]</code> represents the <code>i<sup>th</sup></code> square with a side length of <code>sideLength<sub>i</sub></code> that is dropped with its left edge aligned with X-coordinate <code>left<sub>i</sub></code>.</p>

<p>Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands <strong>on the top side of another square</strong> or <strong>on the X-axis</strong>. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.</p>

<p>After each square is dropped, you must record the <strong>height of the current tallest stack of squares</strong>.</p>

<p>Return <em>an integer array </em><code>ans</code><em> where </em><code>ans[i]</code><em> represents the height described above after dropping the </em><code>i<sup>th</sup></code><em> square</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/28/fallingsq1-plane.jpg" style="width: 500px; height: 505px;" />
<pre>
<strong>Input:</strong> positions = [[1,2],[2,3],[6,1]]
<strong>Output:</strong> [2,5,5]
<strong>Explanation:</strong>
After the first drop, the tallest stack is square 1 with a height of 2.
After the second drop, the tallest stack is squares 1 and 2 with a height of 5.
After the third drop, the tallest stack is still squares 1 and 2 with a height of 5.
Thus, we return an answer of [2, 5, 5].
</pre>

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

<pre>
<strong>Input:</strong> positions = [[100,100],[200,100]]
<strong>Output:</strong> [100,100]
<strong>Explanation:</strong>
After the first drop, the tallest stack is square 1 with a height of 100.
After the second drop, the tallest stack is either square 1 or square 2, both with heights of 100.
Thus, we return an answer of [100, 100].
Note that square 2 only brushes the right side of square 1, which does not count as landing on it.
</pre>

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

<ul>
	<li><code>1 &lt;= positions.length &lt;= 1000</code></li>
	<li><code>1 &lt;= left<sub>i</sub> &lt;= 10<sup>8</sup></code></li>
	<li><code>1 &lt;= sideLength<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
</ul>

/* Sorted container 
- **Implementation Walk-through:**
  1. **Map Initialization:**
     - Initializes a map `mp` to track the heights at different points along a line. It initially contains two points, representing the ground level and the maximum boundary.
  2. **Iterating over Positions:**
     - Iterates over each square given in `positions`. For each square, calculates the `left` and `right` edges and its height `h`.
  3. **Height Calculation:**
     - Uses `lower_bound` to find the positions in the map where the square will affect and calculates the maximum height (`maxH`) under the square to know how high it will stack.
  4. **Map and Result Update:**
     - Erases the segments in the map that the square overlaps and sets the new height for these points.
     - Updates the map at `left` with the new height and `right` with the previous height if necessary.
     - Updates `cur` (current maximum height) and appends it to the result list.

- **Key Ideas:**
  - The solution models the problem as a height map, tracking the terrain's height as squares fall, using a map for efficient range updates and height lookups.
  - The maximum height is updated iteratively as each square falls, considering the overlay of new squares on the existing terrain.

- **Time Complexity:**
  - The main loop iterates through each square, with each iteration performing operations that can range up to O(n) for the map (for finding bounds and updating). Thus, the overall time complexity can be considered O(n^2) in the worst case when considering all insertions and deletions in the map.

- **Space Complexity:**
  - The map and result vector store entries proportional to the number of operations and squares, leading to O(n) space complexity, where n is the number of squares.
*/
// class Solution {
// public:
//     vector<int> fallingSquares(vector <vector<int>> &positions) {
//         map<int, int> mp;

//         // Define the initial boundary
//         mp[0] = 0;
//         mp[INT_MAX] = 0;
//         vector<int> res;
//         int cur = 0;

//         for (auto p: positions) {
//             // Define the current square metrics
//             int left = p[0];
//             int right = p[0] + p[1];
//             int h = p[1];
//             int maxH = 0;

//             // Find the left boundary: equal or after the left
//             auto ptri = mp.lower_bound(left);
//             // Find the right boundary: equal or after the right
//             auto ptrj = mp.lower_bound(right);

//             // Store temporary height of element at or before the current square right edge, this will be used later to update the right boundary height of the current square later
//             int temp = ptrj->first == right? ptrj->second : prev(ptrj, 1)->second;

//             // ptr is the iterator to set up the new height for the current square interval
//             // If the ptri is at the left boundary then we don't need to consider the previous one, otherwise we need to
//             auto ptr = ptri->first == left ? ptri : prev(ptri, 1);
//             // Iterate till the iterator after the right boundary, now all element affected by the current square are checked with their height, eventually finding the max height
//             while (ptr != ptrj) {
//                 maxH = max(maxH, ptr->second);
//                 ptr = next(ptr, 1);
//             }
//             // The current square will create a new flat surface, erasing previous elements are needed, note the erase function is left closed right open
//             if (ptri != ptrj)
//                 mp.erase(ptri, ptrj);
//             // Log in the new height with left corner
//             mp[left] = maxH + h;

//             // Log the right boundary height
//             if (right < ptrj->first)
//                 mp[right] = temp;

//             // Find the global max height after consiering the current square
//             cur = max(cur, maxH + h);
//             res.push_back(cur);
//         }

//         return res;

//     }
// };

/* Segment tree with lazy update 
### Detailed Walkthrough of the Implementation
1. **Segment Tree Node (`SegTreeNode` Class)**:
   - **Attributes**:
     - `start`, `end`: The range this node covers.
     - `info`: The maximum value in the range.
     - `tag`: A flag indicating whether the node's value needs to be propagated to its children.
     - `left`, `right`: Pointers to the left and right child nodes.
   - **Constructor (`SegTreeNode(int a, int b, int val)`)**:
     - Initializes the segment tree node for the range `[a, b]` with an initial value `val`.
     - If the range is not a single element, the constructor recursively initializes the left and right children.
   - **`pushDown()`**:
     - Propagates the node's value (`info`) to its children if the `tag` is set, ensuring correct values throughout the tree.
   - **`updateRange(int a, int b, int val)`**:
     - Updates the segment tree, setting the maximum value to `val` for the range `[a, b]`. The `pushDown()` method is used to propagate changes.
   - **`queryRange(int a, int b)`**:
     - Queries the maximum value in the range `[a, b]` in the segment tree. It also handles propagating any pending updates.
2. **Building Position Mapping**:
   - **`set<int> st`**: Collects all unique x-coordinates from the positions of the falling squares.
   - **`unordered_map<int, int> pos2idx`**: Maps each unique x-coordinate to a compressed index, reducing the size of the segment tree.
3. **Processing Squares (`fallingSquares` Function)**:
   - Iterate through each square in `positions`.
   - For each square, determine the range it covers using `pos2idx` for coordinate compression.
   - Query the current maximum height in the covered range using `queryRange()`.
   - Update the range with the new height using `updateRange()`.
   - Track the maximum height encountered so far and add it to the result vector `res`.
4. **Result Compilation**:
   - The result vector `res` contains the maximum height of the structure after each square falls, reflecting the sequence of height changes.

### Key Ideas
- **Segment Tree**: The segment tree efficiently handles range updates and queries, making it ideal for managing overlapping intervals such as falling squares.
- **Coordinate Compression**: Compresses the x-coordinates to reduce the segment tree's size, improving both space and time efficiency.
- **Lazy Propagation**: The `pushDown()` method ensures that updates are propagated only when necessary, optimizing the performance of range updates.

### Time Complexity
- **Building the Segment Tree**: O(n log n), where n is the number of unique x-coordinates.
- **Updating the Segment Tree**: O(k log n), where k is the number of squares. Each update can affect log n nodes in the segment tree.
- **Querying the Segment Tree**: O(log n) per query.

**Overall Time Complexity**: O((k + n) log n), where k is the number of squares and n is the number of unique x-coordinates.

### Space Complexity
- **Segment Tree Storage**: O(n), where n is the number of unique x-coordinates.
- **Mapping Storage**: O(n) for `pos2idx`.
- **Total Space Complexity**: O(n).

### Potential Optimizations
- **Segment Tree Optimization**: The implementation is already efficient, but a more advanced data structure like a dynamic or persistent segment tree could be considered if further optimizations are needed.
- **Coordinate Compression Refinement**: Ensuring optimal coordinate compression can help minimize the segment tree size and improve the efficiency of operations. Further refinement could involve using more compact data structures or optimizing the mapping process.
*/
// 线段树大小在初始化时固定。支持Lazy Tag（延迟标记）

class SegTreeNode
{
    public:
    SegTreeNode* left = nullptr;
    SegTreeNode* right = nullptr;
    int start, end;
    int info;  // the maximum value of the range
    bool tag; 
        
    SegTreeNode(int a, int b, int val)  // init for range [a,b] with val
    {                 
        tag = 0;
        start = a, end = b;
        if (a == b)
        {
            info = val;
            return;
        }        
        int mid = a + ((b - a) >> 1);
        if (left == nullptr)
        {
            left = new SegTreeNode(a, mid, val);
            right = new SegTreeNode(mid+1, b, val);            
            info = max(left->info, right->info);  // check with your own logic
        }        
    }    
    
    void pushDown()
    {
        if (tag==true && left)
        {
            left->info = info;
            right->info = info;
            left->tag = 1;
            right->tag = 1;
            tag = 0;
        }        
    } 
    
    void updateRange(int a, int b, int val)     // set range [a,b] with val
    {        
        if (b < start || a > end) // not covered by [a,b] at all
            return;        
        if (a <= start && end <=b)  // completely covered within [a,b]
        {
            info = val;
            tag = 1;
            return;
        }

        if (left)
        {
            pushDown();        
            left->updateRange(a, b, val);
            right->updateRange(a, b, val);
            info = max(left->info, right->info);  // write your own logic            
        }        
    }
    
    int queryRange(int a, int b)     // query the maximum value within range [a,b]
    {
        if (b < start || a > end )
        {
            return INT_MIN;  // check with your own logic
        }
        if (a <= start && end <=b)
        {
            return info;  // check with your own logic
        }          
        
        if (left)
        {
            pushDown();     
            int ret = max(left->queryRange(a, b), right->queryRange(a, b));        
            info = max(left->info, right->info);    // check with your own logic
            return ret;
        }
        
        return info;   // should not reach here
    }  

};

class Solution {       
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) 
    {
        set<int> st;
        for (auto & rect: positions)
        {
            st.insert(rect[0]);
            st.insert(rect[0]+rect[1]);
        }
        // 2D plane location and segment tree index mapping
        unordered_map<int,int>pos2idx;
        int idx = 0;
        for (auto x: st)
        {
            pos2idx[x] = idx;
            idx++;
        }
        int n = pos2idx.size();
        
        SegTreeNode* root = new SegTreeNode(0, n-1, 0);
        
        int maxH = 0;
        vector<int>res;
        for (auto & rect: positions)
        {
            int a = pos2idx[rect[0]];
            int b = pos2idx[rect[0]+rect[1]];
            int h = root->queryRange(a, b-1);  // [a,b)
            root->updateRange(a, b-1, h + rect[1]);
            maxH = max(maxH, h + rect[1]);
            res.push_back(maxH);
        }
        return res;        
    }
};

23315