Segment Tree [c++]
Intuition\n Describe your first thoughts on how to solve this problem. \nThe key here is how to merge the two segment.\nWe need to tract 3 things for a segment\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key here is how to merge the two segment.\nWe need to tract 3 things for a segment\n1 Position of most Left block (l)\n2 Position of most right block (r)\n3 Max avalible space in current segment (space)\n\nHow to merge 2 segment :\n1 if both segment has block \n2 only left sub segment has block\n3 only right sub segment has block\n4 none of sub segments has block\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```\nstruct node {\n    node() {}\n    node(int c) {v = c;}\n    int l = INT_MAX;\n    int r = INT_MIN;\n    int v = 0;\n\n    bool valid() { return v >= 0; }\n};\n\nstruct tree {\n\n    unordered_map<int, int> pos;\n    int n;\n    vector<node> arr;\n    void init(int n1) {\n        n = n1;\n        arr = vector<node>(n * 4 + 2);\n    }\n\n    void merge(const node& ln, const node& rn, node& cur, int l, int r)\n    {\n        cur.l = min(ln.l, rn.l);\n        cur.r = max(ln.r, rn.r);\n        cur.v = max(ln.v, rn.v);\n        if (cur.l > cur.r)\n        {\n            cur.v = r - l + 1;\n        }\n        else if (ln.r != INT_MIN && rn.l != INT_MAX)\n        {\n\n            cur.v = max(cur.v, rn.l - ln.r);\n        } else if (ln.r == INT_MIN)\n        {\n            cur.v = max(cur.v, rn.l - l);\n        } else {\n            cur.v = max(cur.v, r - ln.r);\n        }\n    }\n    // l, r, range of current node cur, \n    // p the target point\n    node& update(int l, int r, int cur, int p) {\n        if (p < l || p > r)  return arr[cur];\n        if (r - l <= 1) {\n            arr[cur].l = min(arr[cur].l, p);\n            arr[cur].r = max(arr[cur].r, p);\n            arr[cur].v = r - l;\n            return arr[cur];\n        }\n        int m = (l + r) / 2;\n        auto& ln = update(l, m,  cur * 2, p);\n        auto& rn = update(m, r, cur * 2 + 1, p);\n\n        merge(ln, rn, arr[cur], l, r);\n        return arr[cur];\n    }\n\n    node search(int l, int r, int cur, int x, int y)\n    {\n        if (y < l || x > r)  return node(-1);\n        if (x <= l && r <= y) {\n            return arr[cur];\n        }\n        if (r - l <= 1)\n        {\n            return node(-1);\n        }\n        int m = (l + r) / 2;\n        auto ln = search(l, m,  cur * 2, x, y);\n        auto rn = search(m, r, cur * 2 + 1, x, y);\n        \n        if (ln.valid() && rn.valid()) \n        {\n            node cn;\n            merge(ln, rn, cn, max(l, x), min(r, y));\n            return cn;\n        }\n        else if (ln.valid())\n        {\n            return ln;\n        } else {\n            return rn;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    vector<bool> getResults(vector<vector<int>>& qs) {\n         int n = 0;\n         tree t;\n         for (auto& q : qs) \n         {\n            n = max(n, q[1] + 1);\n         }\n         t.init(n);\n         vector<bool> ans;\n         for (auto& q : qs) \n         {\n            if (q[0] == 1)\n            {\n                t.update(0, n - 1, 1, q[1]);\n            } else {\n                auto cur = t.search(0, n - 1, 1, 0, q[1]);\n                if (cur.l == INT_MAX)\n                {\n                    cur.v = q[1];\n                }\n                \n                if (cur.v >= q[2])\n                {\n                    ans.push_back(true);\n                } else {\n                    ans.push_back(false);\n                }\n            }\n         }\n         return ans;\n    }\n};\n```
['C++']