Runtime 732 ms Beats 98.40% Analyze Complexity Memory 307.98 MB Beats 74.14%
Intuition\nThe problem involves processing a series of queries on an array to manage blocks and query the maximum length of unblocked segments. This requires ef
# Intuition\nThe problem involves processing a series of queries on an array to manage blocks and query the maximum length of unblocked segments. This requires efficient handling of both point updates (adding blocks) and range queries (finding the maximum unblocked segment). A segment tree is a suitable data structure for this task as it can handle both efficiently.\n\n# Approach\nSegment Tree Structure:\n\nEach node in the segment tree stores three pieces of information:\nleftMostBlock: The leftmost position of a block within the segment.\nrightMostBlock: The rightmost position of a block within the segment.\nmaxUnblockedLength: The maximum length of the unblocked segment within the current segment.\nBuilding the Segment Tree:\n\nThe buildSegmentTree function initializes the segment tree. For a single element segment, it sets default values indicating no blocks (leftMostBlock is set to a high value and rightMostBlock to a low value).\nFor larger segments, it recursively builds the left and right subtrees and then sets the values for the current node based on its children.\nAdding a Block:\n\nThe addBlockToSegmentTree function updates the segment tree when a new block is added.\nIt propagates the update down to the appropriate leaf node and then updates the parent nodes accordingly, adjusting leftMostBlock, rightMostBlock, and maxUnblockedLength.\nQuerying the Maximum Unblocked Segment:\n\nThe calculateMaxBlockInSegmentTree function calculates the maximum unblocked length for a given query.\nIt traverses the segment tree to the relevant segments and combines results to find the maximum unblocked length.\nHandling Queries:\n\nThe getResults function processes the input queries.\nFor block addition queries, it updates the segment tree.\nFor range queries, it uses the calculateMaxBlockInSegmentTree function to get the desired result.\n\n# Complexity\n- Time complexity:\nBuilding the Segment Tree: O(n)\nUpdating a Block: O(logn)\nQuerying Maximum Unblocked Length: O(logn)\nOverall, for m queries: O((m+n)logn)\n\n- Space complexity:\nThe space complexity is O(n) for storing the segment tree.\n\n# Code\n```\nclass Solution {\npublic:\n    struct SegmentTreeNode {\n        int leftMostBlock = 1e5;\n        int rightMostBlock = -1;\n        int maxUnblockedLength = 0;\n    };\n\n    void buildSegmentTree(std::vector<SegmentTreeNode>& segmentTree, int segStart, int segEnd, int idx) {\n        if (segStart == segEnd) {\n            segmentTree[idx] = { (int)1e5, -1, 0 };\n            return;\n        }\n        int mid = (segStart + segEnd) / 2;\n        buildSegmentTree(segmentTree, segStart, mid, 2 * idx + 1);\n        buildSegmentTree(segmentTree, mid + 1, segEnd, 2 * idx + 2);\n\n        segmentTree[idx] = { (int)1e5, -1, segEnd - segStart };\n    }\n\n    void addBlockToSegmentTree(std::vector<SegmentTreeNode>& segmentTree, int segStart, int segEnd, int idx, int block) {\n        if (segStart > block || segEnd < block) {\n            return;\n        }\n        if (segStart == segEnd) {\n            segmentTree[idx] = { segStart, segEnd, 0 };\n            return;\n        }\n\n        int mid = (segStart + segEnd) / 2;\n        addBlockToSegmentTree(segmentTree, segStart, mid, 2 * idx + 1, block);\n        addBlockToSegmentTree(segmentTree, mid + 1, segEnd, 2 * idx + 2, block);\n\n        segmentTree[idx].leftMostBlock = std::min(segmentTree[2 * idx + 1].leftMostBlock, segmentTree[2 * idx + 2].leftMostBlock);\n        segmentTree[idx].rightMostBlock = std::max(segmentTree[2 * idx + 1].rightMostBlock, segmentTree[2 * idx + 2].rightMostBlock);\n\n        segmentTree[idx].maxUnblockedLength = std::max(segmentTree[2 * idx + 1].maxUnblockedLength, segmentTree[2 * idx + 2].maxUnblockedLength);\n\n        int secondLeft = std::min(segEnd, segmentTree[2 * idx + 2].leftMostBlock);\n        int firstRight = std::max(segStart, segmentTree[2 * idx + 1].rightMostBlock);\n\n        segmentTree[idx].maxUnblockedLength = std::max(segmentTree[idx].maxUnblockedLength, secondLeft - firstRight);\n    }\n\n    int calculateMaxBlockInSegmentTree(std::vector<SegmentTreeNode>& segmentTree, int segStart, int segEnd, int idx, int x) {\n        if (segStart == segEnd) {\n            return 0;\n        }\n\n        int mid = (segStart + segEnd) / 2;\n        if (x <= mid) {\n            return calculateMaxBlockInSegmentTree(segmentTree, segStart, mid, 2 * idx + 1, x);\n        }\n        int ans = segmentTree[2 * idx + 1].maxUnblockedLength;\n        ans = std::max(ans, calculateMaxBlockInSegmentTree(segmentTree, mid + 1, segEnd, 2 * idx + 2, x));\n\n        int crossoverLimit = x;\n        if (segmentTree[2 * idx + 2].leftMostBlock <= x) {\n            crossoverLimit = segmentTree[2 * idx + 2].leftMostBlock;\n        }\n\n        int crossoverLeftEnd = std::max(segStart, segmentTree[2 * idx + 1].rightMostBlock);\n\n        ans = std::max(ans, crossoverLimit - crossoverLeftEnd);\n\n        return ans;\n    }\n\n    int ceil_pwr_2(int n) {\n        int cnt = 0;\n        n--;\n        while (n > 0) {\n            cnt++;\n            n >>= 1;\n        }\n        return (1 << cnt);\n    }\n\n    std::vector<bool> getResults(std::vector<std::vector<int>>& queries) {\n        int lim = std::min(3 * (int)queries.size(), 50000);\n        lim++;\n        \n        int segTreeSize = 2 * ceil_pwr_2(lim);\n\n        std::vector<SegmentTreeNode> segmentTree(segTreeSize);\n\n        buildSegmentTree(segmentTree, 0, lim - 1, 0);\n\n        std::vector<bool> ans;\n\n        for (auto& q : queries) {\n            if (q[0] == 1) {\n                addBlockToSegmentTree(segmentTree, 0, lim - 1, 0, q[1]);\n            } else {\n                ans.push_back(calculateMaxBlockInSegmentTree(segmentTree, 0, lim - 1, 0, q[1]) >= q[2]);\n            }\n        }\n\n        return ans;\n    }\n};\n```
['C++']