C++ | Segment Tree | Order Set
Intuition\n Describe your first thoughts on how to solve this problem. \nUsing segment tree to store and query maximum size can palce in range\n# Approach\n Des
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUsing segment tree to store and query maximum size can palce in range\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 Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        const int MAX_POS = 50000;\n        vector<int> st(4 * MAX_POS, 0);\n        set<int> obstacles;\n        vector<bool> ans;\n\n        for (auto& q : queries) {\n            if (q[0] == 1) {\n                int x = q[1];\n                \n                auto it = obstacles.upper_bound(x);\n                // no any block in range [0, x] -> just update x with value (x - 0)          \n                if(obstacles.empty() || it == obstacles.begin()) {\n                    update(st, 0, 0, MAX_POS, x, x);\n                } \n                // there is an block in range [0, x] -> [0, y, x] --> update x with (x - y)               \n                else {\n                    auto pit = prev(it);\n                    update(st, 0, 0, MAX_POS, x, x - (*pit));\n                }\n                \n                // [..., x, z] -> update z with (z - x) after insert new block at x\n                if(it != obstacles.end()) {\n                    update(st, 0, 0, MAX_POS, (*it), (*it) - x);                                            \n                }\n                \n                obstacles.insert(x);\n            } \n            else if (q[0] == 2) {\n                int x = q[1];\n                int sz = q[2];\n                \n                auto it = obstacles.upper_bound(x);\n                // no any block in range [0, x] --> sz must be smaller than x  \n                if(obstacles.empty() || it == obstacles.begin()) {\n                    ans.push_back(x >= sz);\n                }     \n                // there is an block in range [0, x] -> [0, y, x] --> max (max value in [0, y], x - y)  \n                else {\n                    auto pit = prev(it);\n                    int maxSize = x - (*pit);\n                    maxSize = max(maxSize, get(st, 0, 0, MAX_POS, 0, (*pit)));\n                    ans.push_back(maxSize >= sz);\n                }\n            }\n        }\n\n        return ans;\n    }\n    \n    void update(vector<int>& st, int id, int l, int r, int i, int v) {\n        if (i < l || r < i) {\n            return;\n        }\n        if (l == r) {\n            st[id] = v;\n            return;\n        }\n\n        int mid = (l + r) / 2;\n        update(st, id * 2 + 1, l, mid, i, v);\n        update(st, id * 2 + 2, mid + 1, r, i, v);\n\n        st[id] = max(st[id * 2 + 1], st[id * 2 + 2]);\n    }\n\n    int get(vector<int>& st, int id, int l, int r, int u, int v) {\n        if (v < l || r < u) {\n            return INT_MIN;\n        }\n        if (u <= l && r <= v) {\n            return st[id];\n        }\n        int mid = (l + r) / 2;\n        return max(get(st, id * 2 + 1, l, mid, u, v), get(st, id * 2 + 2, mid + 1, r, u, v));\n    }\n};\n```
['Segment Tree', 'Ordered Set', 'C++']