Going Backwards + Fenwick Tree
We need to track a max gap till x in a mutating array, but our gaps are decreasing.\n\nTo counter that, we process queries in the reverse order.\n\nFirst, we co
We need to track a max gap till `x` in a mutating array, but our gaps are decreasing.\n\nTo counter that, we process queries in the reverse order.\n\nFirst, we collect and sort all `blocks`. Then, we go left to right, and, for each block, we track the largest gap so far in BIT (AKA Fenwick Tree).\n\nFinally, we go right-to-left.\n1. For block (type = `1`):\n\t- We remove the block.\n\t- We update the largest gap in segment tree for the next block (if exists).\n2. For a query (type = `2`):\n\t- We get the previous block from the sorted set.\n\t- We check the distance to the previous block, and maximum gap till `x` using BIT.\n\n**C++**\n```cpp\nvector<bool> getResults(vector<vector<int>>& qs) {\n    vector<bool> res;\n    set<int> blocks{0}; // sentinel\n    for (const auto &q : qs)\n        if (q[0] == 1)\n            blocks.insert(q[1]);\n    for (auto it = next(begin(blocks)); it != end(blocks); ++it)\n        update(*it, *it - *prev(it));\n    for (int i = qs.size() - 1; i >= 0; --i) {\n        int t = qs[i][0], x = qs[i][1], sz = t == 1 ? 0 : qs[i][2];\n        auto it = blocks.lower_bound(x);\n        if (t == 1) {\n            if (next(it) != end(blocks))\n                update(*next(it), *next(it) - *prev(it));\n            blocks.erase(it);\n        }\n        else\n            res.push_back(x - *prev(it) >= sz || getmax(x) >= sz);\n    }\n    return vector<bool>(rbegin(res), rend(res));\n}\nint bit[50001] = {};\nint getmax(int r) {\n    int ret = 0;\n    for (; r >= 0; r = (r & (r + 1)) - 1)\n        ret = max(ret, bit[r]);\n    return ret;\n}\nvoid update(int idx, int val) {\n    for (; idx < 50001; idx = idx | (idx + 1))\n        bit[idx] = max(bit[idx], val);\n}\n```\n\n**Python**\n```python\nclass Solution:    \n    def getResults(self, queries: List[List[int]]) -> List[bool]:\n        bit, res = [0] * (min(50000, 3 * len(queries)) + 1), []\n        def bit_range(p, down=True):\n            while p >= 0 and p < len(bit):\n                yield p\n                p = (p & (p + 1)) - 1 if down else p | (p + 1)        \n        def get_max(p: int) -> int:\n            return max(bit[i] for i in bit_range(p))\n        def update(p, val):\n            for idx in bit_range(p, False):\n                 bit[idx] = max(bit[idx], val);\n            \n        blocks = [0] + sorted([x for t, x, *sz in queries if t == 1])\n        for i, b in enumerate(blocks[1:]):\n            update(b, b - blocks[i])\n        for t, x, *sz in reversed(queries):\n            p = bisect_left(blocks, x)\n            if t == 1:\n                if p + 1 < len(blocks):\n                    update(blocks[p + 1], blocks[p + 1] - blocks[p - 1])\n                del blocks[p]  # No difference if using sorted containers.\n            else:\n                res.append(x - blocks[p - 1] >= sz[0] or get_max(x) >= sz[0])\n        return reversed(res)\n```
['C', 'Python']