C++ Segment tree approach
For each query of type 2, we need to know the maximum "gap" among all gaps in range [0, x]. To do this, first we need to find the last obstacles which is not gr
For each query of type 2, we need to know the maximum "gap" among all gaps in range [0, x]. To do this, first we need to find the last obstacles which is not greater than x, let\'s denote it as i. Then the maximum gap will be equal to maximum gap among all obstacles from [0, i] and the difference of x - i (as I visualize in the image). To maintain the coordinate of the obstacles, we can use a set. To find the maximum of all gaps that not greater than i, we can use a maximum-query segment tree. When we update a point x into the set, we need to update the gap between x and the nearest obstacle to the right of x, and the gap between x and the nearest obstacle to the left of x.\n\n![image.png](https://assets.leetcode.com/users/images/a83b8969-fdfa-4416-9c05-7c8582615e5d_1716662270.5742416.png)\n\n# Complexity\n- Time complexity: O(nlogn)\n\n\n# Code\n```\nclass Solution {\npublic:\n    \n    int st[1 << 20];\n    \n    void upd(int i, int x, int l = 1, int r = 50000, int idx = 0){\n        if(l == r){\n            st[idx] = x;\n            return;\n        }\n        int m = l + r >> 1;\n        if(i <= m){\n            upd(i, x, l, m, idx * 2 + 1);\n        }else\n            upd(i, x, m + 1, r, idx * 2 + 2);\n        st[idx] = max(st[idx * 2 + 1], st[idx * 2 + 2]);\n    }\n    \n    int query(int l, int r, int tl = 1, int tr = 50000, int idx = 0){\n        if(tl > r || tr < l) return INT_MIN;\n        if(tl >= l && tr <= r) return st[idx];\n        int tm = tl + tr >> 1;\n        return max(query(l, r, tl, tm, idx * 2 + 1), query(l, r, tm + 1, tr, idx * 2 + 2));\n    }\n    \n    vector<bool> getResults(vector<vector<int>>& qry) {\n        set<int> s;\n        s.insert(0);\n        vector<bool> res;\n        for(auto v: qry){\n            int type = v[0];\n            if(type == 1){\n                int x = v[1];\n                auto it = s.upper_bound(x);\n                if(it != s.end()){\n                    upd(*it, *it - x);\n                }\n                --it;\n                upd(x, x - *it);\n                s.insert(x);\n            }else{\n                int x = v[1], sz = v[2];\n                auto it = s.upper_bound(x);\n                --it;\n                \n                if(query(0, *it) >= sz || x - *it >= sz){\n                    res.push_back(true);\n                }else \n                    res.push_back(false);\n            }\n        }\n        return res;\n    }\n};\n```
['C++']