Explained 2 solutions: O(N log N) and O(N sqrt N)
Main Algorithm ApproachThe solution uses a Fenwick Tree (Binary Indexed Tree) to efficiently track and query maximum segment lengths. The key strategies include
# Main Algorithm Approach\nThe solution uses a Fenwick Tree (Binary Indexed Tree) to efficiently track and query maximum segment lengths. The key strategies include:\n\n1. Dynamically maintaining obstacle segment boundaries\n2. Tracking available segment lengths\n3. Efficiently querying maximum possible segment sizes\n\n## Key Invariants\n- Maintain a sorted list of segment boundaries\n- Dynamically update segment lengths when obstacles are added\n- Use Fenwick Tree to quickly retrieve maximum segment length at any point\n\n## Complexity\n- Time Complexity: $$O(n \\log n)$$\n  - Sorting borders\n  - Fenwick Tree operations are $$O(\\log n)$$\n- Space Complexity: $$O(n)$$\n  - Storing borders, Fenwick Tree, and result array\n\n## Core Implementation Strategy\n1. First pass: Collect and sort obstacle boundaries\n2. Build Fenwick Tree with initial segment lengths\n3. Process queries in reverse order:\n   - For obstacle addition: Split and merge segments\n   - For length queries: Find maximum passable segment length using Fenwick Tree\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<bool> getResults(const vector<vector<int>>& queries) {\n        return getResults_qbw_unite_max_fenw(queries);\n        return getResults_len2begs(queries);\n    }\n\n    /** Primary implementation using Fenwick Tree (Binary Indexed Tree)\n      * Key strategy: Dynamically track segment lengths and maximum possible segment sizes */\n    vector<bool> getResults_qbw_unite_max_fenw(const vector<vector<int>>& queries) {\n        // Borders: Tracks the boundaries of obstacle segments\n        // Starts with 0 as the global beginning of the number line\n        vector<int> borders(1);\n        int max_qx = 0; // Track the maximum x-coordinate to size the Fenwick tree\n        int questions_size = 0;\n        // First pass: Collect all borders and count query type 2 queries\n        for (const auto& q : queries) {\n            if (q[0] == 1) {\n                borders.push_back(q[1]);\n                max_qx = max(max_qx, q[1] + 1);\n            } else {\n                max_qx = max(max_qx, q[1]);\n                ++questions_size;\n            }\n        }\n        sort(borders.begin(), borders.end());\n        if (borders.back() < max_qx) // Ensure the last border extends to max_qx if needed\n            borders.push_back(max_qx);\n\n        map<int, int> beg2len;\n        for (int i = 1; i < borders.size(); ++i)\n            beg2len[borders[i - 1]] = borders[i] - borders[i - 1];\n\n        // Fenwick Tree for tracking maximum segment sizes\n        // Key data structure for efficient\n        vector<int> fenw(borders.back() + 2);\n        auto upd = [&fenw](int i, int v) {\n            ++i;\n            for (; i < fenw.size(); i += i & -i)\n                fenw[i] = max(fenw[i], v);\n        };\n        auto get = [&fenw](int i) {\n            int res = 0;\n            ++i;\n            for (; i > 0; i -= i & -i)\n                res = max(res, fenw[i]);\n            return res;\n        };\n        for (auto [beg, len] : beg2len) // Populate Fenwick Tree with segment lengths\n            upd(beg + len, len);\n\n        vector<bool> res(questions_size);\n        int resp = questions_size;\n\n        // Process queries in reverse order\n        // Invariant: Maintain a dynamic representation of obstacle segments\n        for (int i = queries.size() - 1; i >= 0; --i) {\n            if (queries[i][0] == 1) {\n                int segment_beg = queries[i][1];\n                // Find the segment containing this obstacle\n                auto it = beg2len.find(segment_beg);\n                // Merge segments by extending the previous segment\n                int segment_end = segment_beg + it->second;\n                auto prev_it = prev(it);\n                prev_it->second += it->second;\n                // Update Fenwick Tree with new maximum segment length\n                upd(segment_end, prev_it->second);\n                beg2len.erase(it); // Remove the current segment\n            } else {\n                int lim = queries[i][1];\n                int len = queries[i][2];\n                auto it = beg2len.upper_bound(lim);\n                --it; // Find the last segment before the limit\n                int prev_end = it->first;\n                int max_seg_size = lim - prev_end; // Either till limit\n                if (prev_end >= 0)\n                    max_seg_size = max(max_seg_size, get(prev_end)); // Or preceding entire segment\n                res[--resp] = max_seg_size >= len;\n            }\n        }\n\n        return res;\n    }\n\n    vector<bool> getResults_len2begs(const vector<vector<int>>& queries) {\n        int max_qx = max_element(\n            queries.begin(), queries.end(),\n            [](const auto& a, const auto& b) { return a[1] < b[1]; })->at(1) + 1;\n\n        map<int, set<int>> len2begs;\n        len2begs[max_qx].insert(0);\n        set<int> begs; // Multimap tracking available segment lengths to their start points\n        begs.insert(0); // Ordered set of all segment start and end points\n        begs.insert(max_qx);\n\n        vector<bool> res;\n\n        for (const auto& q : queries) {\n            if (q[0] == 1) {\n                int segment_mid = q[1];\n                // Find the segment containing the new obstacle\n                auto begs_it = begs.upper_bound(segment_mid);\n                int segment_end = *begs_it;\n                --begs_it;\n                int segment_beg = *begs_it;\n                int len_old = segment_end - segment_beg;\n                auto len_old_it = len2begs.find(len_old);\n                assert(len_old_it != len2begs.end());\n                // Replace old len with 2 new in both len2begs and begs\n                len_old_it->second.erase(segment_beg);\n                if (len_old_it->second.empty())\n                    len2begs.erase(len_old_it);\n                len2begs[segment_mid - segment_beg].insert(segment_beg);\n                len2begs[segment_end - segment_mid].insert(segment_mid);\n                begs.insert(segment_mid);\n            } else {\n                int lim = q[1];\n                int len = q[2];\n                int pass_beg = -1; // Check all greater length options, total time O(sqrt(N))\n                for (auto it = len2begs.lower_bound(len); it != len2begs.end(); ++it) {\n                    int beg = *it->second.begin();\n                    int end = beg + len;\n                    if (end <= lim) {\n                        pass_beg = beg;\n                        break;\n                    }\n                }\n                res.push_back(pass_beg > -1);\n            }\n        }\n\n        return res;\n    }\n};\n\n```
['C++']