Python Diffenrent Concise Solutions
Thanks this great work : https://leetcode.com/articles/falling-squares/ \n\n\nApproach 1 :\njust like this article said , there are two operations: \n>update, w
Thanks this great work : https://leetcode.com/articles/falling-squares/ \n\n\n**Approach 1 :**\njust like this article said , there are two operations: \n>update, which updates our notion of the board (number line) after dropping a square; \n>query, which finds the largest height in the current board on some interval.\n\nInstead of asking the question "what squares affect this query?", lets ask the question "what queries are affected by this square?"\n```python\n    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n        max_h_of_p = [0]*len(positions)\n        \n        for i,(left,size) in enumerate(positions):\n            right = left+size-1\n            max_h_of_p[i] += size\n            for offset,(left2,size2) in enumerate(positions[i+1:]):\n                j = offset+i+1\n                right2 = left2+size2-1\n                if left2 <= right and left <= right2: # intersect\n                    max_h_of_p[j] = max(max_h_of_p[j], max_h_of_p[i])\n                    \n        res = [] \n        for h in max_h_of_p:\n            res.append(max(res[-1],h)) if res else res.append(h)\n        return res\n```\n-------------------------\n\n**Approach 2 :**\nSegment tree with coordinates compression\n```python\nclass SegmentTreeNode:\n    def __init__(self, low, high):\n        self.low = low\n        self.high = high\n        self.left = None\n        self.right = None\n        self.max = 0\n\nclass Solution:       \n    def _build(self, left, right):\n        root = SegmentTreeNode(self.coords[left], self.coords[right])\n        if left == right:\n            return root\n        \n        mid = (left+right)//2\n        root.left = self._build(left, mid)\n        root.right = self._build(mid+1, right)\n        return root\n    \n    def _update(self, root, lower, upper, val):\n        if not root:\n            return\n        if lower <= root.high and root.low <= upper:# intersect\n            root.max = val\n            self._update(root.left, lower, upper, val)\n            self._update(root.right, lower, upper, val)\n        \n    def _query(self, root, lower, upper):\n        if lower <= root.low and root.high <= upper:\n            return root.max\n        if upper < root.low or root.high < lower:\n            return 0\n        return max(self._query(root.left, lower, upper), self._query(root.right, lower, upper))\n    \n    def fallingSquares(self, positions: List[List[int]]) -> List[int]:\n\t\t# coordinates compression\n        coords = set()\n        for left, size in positions:\n            right = left+size-1\n            coords.add(left)\n            coords.add(right)\n        self.coords = sorted(list(coords))\n        root = self._build(0, len(self.coords)-1)\n        \n        res = []\n        for left, size in positions:\n            right = left+size-1\n            h = self._query(root, left, right) + size\n            res.append(max(res[-1],h)) if res else res.append(h)\n            self._update(root, left, right, h)\n        return res\n```
['Python3']