Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n\nThe best explanation I could find: https://leetcode.com/problems/block-placement-quer
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe best explanation I could find: https://leetcode.com/problems/block-placement-queries/solutions/5206977/c-segment-tree-with-explaination-and-comments/\n\nIntuitively, if we are attempting segment tree, we can think upto trying to maintain the max distance between gaps in the tree.\n\nHowever the insert queries are problematic as they split some gap [l, r] into two, [l, x] and [x, r] - basically splitting a node in a segment tree - which it doesn\'t support and so we can\'t do this.\n\nSo instead of this, given that each obstacle is placed at a discrete location, instead of storing range information, we store simply the distance to the obstacle occurring just before an element. The default values can all be 0, they will be ignored while taking maximum.\n\nSo when we insert a new obstacle x, and the obstacles that already exist immediately behind and after it are l and r, we only have to update the value at r to r-x and the value at x to x-l. l already stores the distance from l to something immediately before it, so there is nothing to update at l. To track these l and r, we can use a set. Also, by default the set can contain 0 and 50000, which are the left and right limits set by the question (we know we will never get obstacles beyond this range).\n\nNow when we get a query of type two, we can range query the maximum in the range [0, x]. However, if there is no obstacle at x, then we only find the max distance between obstacles [0, l] where l is the obstacle immediately before position x, and we haven\'t seen if the object can fit between l and x (because there is no obstacle at x, it has not been set to x-l). So we have to check x-l as well in this case.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SegTree{\n    public:\n    vector<int> t;\n\n    SegTree(int n)\n    {\n        t.assign(2*n, 0);\n    }\n\n    void insert(int i, int l, int r, int pos, int x)\n    {\n        if(pos < l || pos > r || l > r)\n        {\n            return;\n        }\n        \n        if(l == r)\n        {\n            t[i] = x;\n            return;\n        }\n\n        int mid = l + (r-l)/2;\n        insert(i+1, l, mid, pos, x);\n        insert(i+2*(mid-l+1), mid+1, r, pos, x);\n        t[i] = max(t[i+1], t[i+2*(mid-l+1)]);\n    }\n\n    int query(int i, int l, int r, int lq, int rq)\n    {\n        if(l > rq || r < lq || l > r || lq > rq)\n        {\n            return 0;\n        }\n\n        if(lq <= l && r <= rq)\n        {\n            return t[i];\n        }\n\n        int mid = l + (r-l)/2;\n        return max(query(i+1, l, mid, lq, rq),\n                    query(i+2*(mid-l+1), mid+1, r, lq, rq));   \n    }\n};\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n\n        int n = 50010;\n\n        SegTree st(n);\n\n        set<int> s;\n        s.insert(0);\n        s.insert(50000);\n\n        vector<bool> ans;\n\n        for(int i = 0; i<queries.size(); i++)\n        {\n            int opt = queries[i][0];\n\n            if(opt == 1)\n            {\n                int x = queries[i][1];\n                \n                auto it = s.lower_bound(x);\n\n                int r = *(it);\n                int l = *(--it);\n\n                st.insert(0, 0, n-1, r, r-x);\n                st.insert(0, 0, n-1, x, x-l);\n                \n                s.insert(x);\n            }\n            else\n            {\n                int x = queries[i][1];\n                int sz = queries[i][2];\n\n                if(sz > x)\n                {\n                    ans.push_back(false);\n                }\n                else\n                {\n                    int v = st.query(0, 0, n-1, 0, x);\n\n                    if(v >= sz)\n                    {\n                        ans.push_back(true);\n                    }\n                    else\n                    {\n                        auto it = s.lower_bound(x);\n\n                        if(*it != x)\n                        {\n                            int l = *(--it);\n\n                            ans.push_back((x - l) >= sz);\n                        }\n                        else\n                        {\n                            ans.push_back(false);\n                        }\n                    }\n                }\n\n            }\n        }\n\n        return ans;\n\n    }\n};\n```
['C++']