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

from dataclasses import dataclass


@dataclass
class Node:
    left: 'Node'
    right: 'Node'
    val: int
    biggest: int

class RangeTree:

    def __init__(self, n):
        self.size = 2**math.ceil(math.log2(n))
        self.root = Node(None, None, 0, 0)

    def setRange(self, bottom: int, top: int, val: int):
        self._set(self.root, bottom, top, self.size, val)

    def getMaxInRange(self, bottom: int, top: int):
        return self._getMax(self.root, bottom, top, self.size)

    def _getMax(self, node, bottom: int, top: int, size: int):
        if node is None:
            return 0

        if size - 1 == top and bottom == 0:
            return node.biggest

        mid = size // 2
        biggest = node.val
        if bottom < mid:
            biggest = max(biggest, self._getMax(node.left, bottom, min(top, mid - 1), mid))
        
        if top >= mid:
            biggest = max(biggest, self._getMax(node.right, max(0, bottom - mid), top - mid, mid))

        return biggest

    
    def _set(self, node, bottom: int, top: int, size: int, val: int):
        if node is None:
            return

        if top - bottom >= size:
            raise Exception(f"invalid state: {bottom, top, size}")

        if size - 1 == top and bottom == 0:
            node.val = val
            node.biggest = val
            node.left = None
            node.right = None
            return


        node.left = Node(None, None, node.val, node.val) if node.left is None else node.left
        node.right = Node(None, None, node.val, node.val) if node.right is None else node.right
        mid = size // 2
        if bottom < mid:
            self._set(node.left, bottom, min(top, mid - 1), mid, val)

        if top >= mid:
            self._set(node.right, max(0, bottom - mid), top - mid, mid, val)

        node.biggest = max(node.biggest, val)


class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        t = RangeTree(max(((p[0] + p[1]) for p in positions)) + 1)
        top_point = 0
        result = []
        for i, s in enumerate(positions):
            # for i in range(0, 400):
            #     print(i, t.getMaxInRange(i, i))

            highest = 0 
            if s[1] == 1:
                exists = False
                for j in range(i):
                    exists |= s[0] >= positions[j][0] and s[0] < positions[j][0] + positions[j][1]

                if exists:
                    highest = min((
                        t.getMaxInRange(s[0], s[0]),
                        t.getMaxInRange(s[0]+1, s[0]+1)))
            else:
                highest = t.getMaxInRange(s[0]+1, s[0] + s[1]-1)
            print(highest, s[0], s[0] + s[1])
            t.setRange(s[0], s[0] + s[1], highest + s[1])
            top_point = max(top_point, highest + s[1])
            result.append(top_point)
        return result

        
18400