<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>

#include <vector>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    vector<int> lazy;
    int n;

    void update(int node, int start, int end, int l, int r, int height) {
        if (lazy[node] != 0) {
            tree[node] = max(tree[node], lazy[node]);
            if (start != end) {
                lazy[2 * node + 1] = max(lazy[2 * node + 1], lazy[node]);
                lazy[2 * node + 2] = max(lazy[2 * node + 2], lazy[node]);
            }
            lazy[node] = 0;
        }

        if (start > end || start > r || end < l) return;

        if (start >= l && end <= r) {
            tree[node] = max(tree[node], height);
            if (start != end) {
                lazy[2 * node + 1] = max(lazy[2 * node + 1], height);
                lazy[2 * node + 2] = max(lazy[2 * node + 2], height);
            }
            return;
        }

        int mid = (start + end) / 2;
        update(node * 2 + 1, start, mid, l, r, height);
        update(node * 2 + 2, mid + 1, end, l, r, height);
        tree[node] = max(tree[node * 2 + 1], tree[node * 2 + 2]);
    }

    int query(int node, int start, int end, int l, int r) {
        if (start > end || start > r || end < l) return 0;

        if (lazy[node] != 0) {
            tree[node] = max(tree[node], lazy[node]);
            if (start != end) {
                lazy[2 * node + 1] = max(lazy[2 * node + 1], lazy[node]);
                lazy[2 * node + 2] = max(lazy[2 * node + 2], lazy[node]);
            }
            lazy[node] = 0;
        }

        if (start >= l && end <= r) return tree[node];

        int mid = (start + end) / 2;
        int left_query = query(node * 2 + 1, start, mid, l, r);
        int right_query = query(node * 2 + 2, mid + 1, end, l, r);
        return max(left_query, right_query);
    }

public:
    SegmentTree(int size) : n(size), tree(4 * size, 0), lazy(4 * size, 0) {}

    void update(int l, int r, int height) {
        update(0, 0, n - 1, l, r, height);
    }

    int query(int l, int r) {
        return query(0, 0, n - 1, l, r);
    }
};




class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
            set<int> x_coords;
    for (const auto& pos : positions) {
        int left = pos[0];
        int right = pos[0] + pos[1] - 1;
        x_coords.insert(left);
        x_coords.insert(right);
    }

    vector<int> sorted_x_coords(x_coords.begin(), x_coords.end());
    map<int, int> coord_map;
    for (int i = 0; i < sorted_x_coords.size(); ++i) {
        coord_map[sorted_x_coords[i]] = i;
    }

    int n = sorted_x_coords.size();
    SegmentTree segTree(n);
    vector<int> result;

    for (const auto& pos : positions) {
        int left = pos[0];
        int length = pos[1];
        int right = left + length - 1;
        int left_idx = coord_map[left];
        int right_idx = coord_map[right];

        int height = segTree.query(left_idx, right_idx) + length;
        segTree.update(left_idx, right_idx, height);

        result.push_back(segTree.query(0, n - 1));
    }

    return result;
    }
};
19855