Segment Tree || Beat 100%
Intuition\n Describe your first thoughts on how to solve this problem. \n- Use set to maintain set of x.\n- Use segment tree update position x by the value of x
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Use set to maintain set of x.\n- Use segment tree update position x by the value of x and previous of x. \n![image.png](https://assets.leetcode.com/users/images/171567dd-dd20-49c4-9dd3-cb3bccc55673_1716795896.002929.png)\n- Now, we have a segment tree to store the distance of x and previous of x. \n- Which each query, set p is the maximum of the set x (which is chosen) that less than x. The maximum distance d to put the block size sz is max of (0, p) and x - p.\n![image.png](https://assets.leetcode.com/users/images/c8892731-ff90-4f4a-b0ae-0d221508b2f1_1716796104.4005086.png)\nUse segment tree to find the maximum distance that p manage\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    struct SegmentTree {\n        int n;\n        vector<int> st;\n\n        SegmentTree(int n) : n(n) { st.assign(4 * n + 7, 0); }\n\n        void update(int id, int l, int r, int pos, int val) {\n            if (pos < l || pos > r)\n                return;\n            if (l == r) {\n                st[id] = val;\n                return;\n            }\n            int m = (l + r) / 2;\n            if (pos <= m) {\n                update(id * 2 + 1, l, m, pos, val);\n            } else {\n                update(id * 2 + 2, m + 1, r, pos, val);\n            }\n            st[id] = max(st[id * 2 + 1], st[id * 2 + 2]);\n        }\n\n        int getMax(int id, int l, int r, int u, int v) {\n            if (r < u || l > v)\n                return 0;\n            if (u <= l && r <= v)\n                return st[id];\n            int m = (l + r) / 2;\n            return max(getMax(id * 2 + 1, l, m, u, v),\n                       getMax(id * 2 + 2, m + 1, r, u, v));\n        }\n\n        void update(int pos, int val) { update(0, 0, n - 1, pos, val); }\n\n        int getMax(int u, int v) { return getMax(0, 0, n - 1, u, v); }\n    };\n    vector<bool> getResults(vector<vector<int>>& queries) {\n        vector<bool> res;\n        set<int> s;\n        s.insert(0);\n        SegmentTree st(50001);\n        for (vector<int> q : queries) {\n            int type = q[0];\n            if (type == 1) {\n                int x = q[1];\n                auto it = s.lower_bound(x);\n                if (it != s.end()) {\n                    int aft = *it;\n                    st.update(aft, aft - x);\n                }\n                int pre = *(--it);\n                st.update(x, x - pre);\n                s.insert(x);\n            } else {\n                int x = q[1];\n                int sz = q[2];\n\n                int d = st.getMax(0, x);\n                int d1 = *(--s.lower_bound(x));\n                d = max(d, x - d1);\n                res.push_back((sz <= d));\n            }\n        }\n        return res;\n    }\n};\n```
['C++']