Python 3 || Segment Tree + SortedList with Comments
Approach\nNot optimal but intuitive.\n\naxis: A sorted list that stores the blocks along the axis.\nitvl: A segment tree that stores the intervals between the b
# Approach\nNot optimal but intuitive.\n\n`axis`: A sorted list that stores the blocks along the axis.\n`itvl`: A segment tree that stores the intervals between the blocks and supports range query of the maximal interval from 0 to each block.\n\nWhen adding a block, we need to update the interval of the next block (from `nxt - prv` to `nxt - q[1]`) and the current block (added as `q[1] - prv`).\n\nWhen answering a type-2 queries, we query the maximal interval before the previous block (`itvl.query(prv)`) and compare it with the last interval (`q[1] - prv`). The answer is true iff `sz` is less than or equal to the maximal interval we found.\n\n# Complexity\n- Time complexity: $Q \\log Q + Q \\log M$, where $Q$ is the length of `queries` and $M$ is the range of the axis, i.e. `max(q[1])`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $Q + M$.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3\nfrom sortedcontainers import SortedList\nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n\n        # Blocks along the axis\n        axis = SortedList()\n\n        # Range Max of intervals from 0 to each block\n        itvl = SegTree(max(q[1] for q in queries))\n\n        res = []\n        axis.add(0)\n        itvl.update(0,0)\n\n        for q in queries:\n            if q[0] == 1:\n                ind = axis.bisect(q[1])\n                if ind < len(axis):\n                    # Update the interval of the next block\n                    nxt = axis[ind]\n                    itvl.update(nxt, nxt-q[1])\n                # Set the interval of the current block\n                itvl.update(q[1], q[1] - axis[ind-1])\n                # Add the current block on axis\n                axis.add(q[1])\n            else:\n                # Find the previous block\n                prv = axis[axis.bisect(q[1])-1]\n                # Range query the max interval before prv\n                mx = max(q[1]-prv, itvl.query(prv))\n\n                res.append(q[2] <= mx)\n        return res\n\nclass SegTree:\n\n    def __init__(self, n: int):\n        self.n = 1 << n.bit_length()\n        self.tree = [0] * (self.n*2)\n\n    def update(self, ind: int, val: int):\n        ind += self.n\n        self.tree[ind] = val\n        while ind > 1:\n            ind //= 2\n            self.tree[ind] = max(self.tree[ind*2], self.tree[ind*2+1])\n    \n    def query(self, ind: int) -> int:\n        ind += self.n\n        res = self.tree[ind]\n        while ind > 1:\n            if ind%2 == 1:\n                res = max(res, self.tree[ind-1])\n            ind //= 2\n        return res\n```
['Segment Tree', 'Python3']