Without segment tree, an alternative solution beating 80%
Approach\n Describe your first thoughts on how to solve this problem. \nThis problem can be typically solved by using segment tree. However, my solution approac
# Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem can be typically solved by using segment tree. However, my solution approaches the problem from an alternative way. I process the queries from the reversed order and merge the split segments gradually. \n\nWe maintain a binary search tree that keeps all current segments and another binary search tree that contains only *good* segments $(l_1, r_1), (l_2, r_2), ..., (l_k, r_k)$ satisfying the monotonic property $(r_1-l_1) > (r_2-l_2) > ... > (r_k - l_k)$ and $r_1 < r_2 < ... < r_k$. \n\nFor finding a segment for each query, we can do binary search on the monotonic good segments. In my solution, the segment tree is not required. What we need is only the usual binary search tree. In Python, the `sortedcontainers` package is simple and powerful.  \n\n# Complexity\n- Time complexity: $O(\\log N)$ for each operation, and $O(N \\log N)$ in overall. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        segments = [0] + sorted([q[1] for q in queries if len(q) == 2]) + [1000000000]\n        segments = SortedList([(l, r) for l, r in zip(segments, segments[1:])])\n        stack = SortedList()\n        for seg in segments:\n            if not stack or stack[-1][1] < seg[1] - seg[0]:\n                stack.add((seg[1], seg[1] - seg[0]))\n        ans = []\n        for q in reversed(queries):\n            if len(q) == 2:\n                x = q[1]\n                p = segments.bisect_left((x, -inf))\n                (l2, r2) = segments.pop(p)\n                (l1, r1) = segments.pop(p-1)\n                l, r = l1, r2\n                segments.add((l, r))\n\n                stack.discard((r1, r1-l1))\n                stack.discard((r2, r2-l2))\n                p = stack.bisect_left((r, r-l))\n                if p == 0 or stack[p-1][1] < r - l:\n                    stack.add((r, r-l))\n                    while p + 1 < len(stack) and stack[p+1][1] <= r-l:\n                        stack.pop(p+1)\n            else:\n                x, l = q[1], q[2]\n                if x - l < 0:\n                    ans.append(False)\n                    continue\n                p = segments.bisect_left((x - l, inf)) - 1\n                if x <= segments[p][1]:\n                    ans.append(True)\n                else:\n                    p = bisect_left(stack, (x, inf)) - 1\n                    ans.append(p >= 0 and stack[p][1] >= l)\n        return reversed(ans)\n\n```
['Binary Search Tree', 'Monotonic Queue', 'Python3']