BIT + SortedList, reverse temporal order
Intuition\nKeep track of the intervals in SortedList and use BIT to query for the largest gap length.\n\n# Approach\nYou can\'t reverse max() operations. Howeve
# Intuition\nKeep track of the intervals in `SortedList` and use BIT to query for the largest gap length.\n\n# Approach\nYou can\'t reverse `max()` operations. However, if you go back in time, the gaps only get larger and larger so BIT is sufficient. For type 2 query, query the largest gap length up to the last obstacle `before` and just check whether that or `x - before >= sz`.\n\n# Complexity\n- Time complexity:\n$$O(n\\log n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```python\nclass BIT:\n    def __init__(self, n):\n        self.n = n\n        self.l = [0] * (n + 1)\n    def add(self, i, x):\n        i += 1\n        while i <= self.n:\n            self.l[i] = max(x, self.l[i])\n            i += i & -i\n    def query(self, i):\n        i += 1\n        ans = 0\n        while i:\n            ans = max(ans, self.l[i])\n            i -= i & -i\n        return ans\n\nfrom sortedcontainers import SortedList\n    \nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        sl = SortedList()\n        n = min(5 * 10 ** 4, len(queries) * 3)\n        sl.add(0)\n        sl.add(n)\n        \n        ans = []\n        for q in queries:\n            if q[0] == 1:\n                x = q[1]\n                sl.add(x)\n        \n        bit = BIT(n + 1)\n        for x, y in pairwise(sl):\n            bit.add(y, y - x)\n        \n        for q in reversed(queries):\n            if q[0] == 1:\n                x = q[1]\n                index = sl.index(x)\n                after = sl[index + 1]\n                before = sl[index - 1]\n                sl.remove(x)\n                bit.add(after, after - before)\n            else:\n                _, x, sz = q\n                index = sl.bisect_right(x)\n                before = sl[index - 1]\n                ans.append(bit.query(before) >= sz or (x - before) >= sz)\n            \n        ans.reverse()\n        return ans\n```\n\n# Addendum\nIt turned out that by going backward in time, we can use the fact that gaps get larger and larger *and* we only care about gaps larger than all gaps to the left ("monotonic stack"-like) and also use `SortedList` to keep track of gap length. We need to update from the middle of `gap` and the time complexity is still $$O(n\\log n)$$, but now we don\'t need to implement our own BIT or segment tree.\n\n```python\nfrom sortedcontainers import SortedList\n    \nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        sl = SortedList()\n        n = min(5 * 10 ** 4, len(queries) * 3)\n        sl.add(0)\n        sl.add(n)\n        \n        ans = []\n        for q in queries:\n            if q[0] == 1:\n                x = q[1]\n                sl.add(x)\n        gap = SortedList()\n        gap.add((0, 0))\n        curr = 0\n        for x, y in pairwise(sl):\n            if (g := y - x) > curr:\n                gap.add((y, g))\n                curr = g\n        \n        for q in reversed(queries):\n            if q[0] == 1:\n                x = q[1]\n                index = sl.index(x)\n                after = sl[index + 1]\n                before = sl[index - 1]\n                sl.remove(x)\n                g = after - before\n                index = gap.bisect_left((x, 0))\n                while index < len(gap) and gap[index][1] <= g:\n                    gap.pop(index)\n                if gap[index - 1][1] < g:\n                    gap.add((after, g))\n            else:\n                _, x, sz = q\n                index = sl.bisect_right(x)\n                before = sl[index - 1]\n                index = gap.bisect_right((before, math.inf)) - 1\n                ans.append((x - before) >= sz or gap[index][1] >= sz)\n            \n        ans.reverse()\n        return ans\n```
['Python3']