Block Placement on a Number Line

# Block Placement on a Number Line An initially empty number line starts at zero and extends indefinitely in the positive direction. Process `queries` in order: 1. `[1, x]`: build an obstacle at coordinate `x`. No obstacle exists there when this query occurs. 2. `[2, x, sz]`: determine whether a block of length `sz` can fit anywhere entirely within `[0, x]`, without an obstacle in its interior. Its endpoints may touch obstacles. A type-2 query only asks whether a placement is possible. It does not place a block or change the obstacles. Return one boolean per type-2 query, in their original order; type-1 queries produce no output. ### Examples **Example 1** ```text Input: queries = [[2,5,5],[1,3],[2,5,3],[2,5,4]] Output: [true,true,false] ``` Before any obstacle, a block of length five fits in `[0,5]`. After inserting the obstacle at three, the available intervals within `[0,5]` have lengths three and two. A block of length three fits by touching the obstacle; one of length four does not. **Example 2** ```text Input: queries = [[1,4],[1,8],[2,8,4],[2,6,4],[2,6,5],[2,3,3]] Output: [true,true,false,true] ``` The obstacles at four and eight leave gaps of length four before eight. Within `[0,6]`, a length-four block still fits in `[0,4]`, but a length-five block does not fit. Within `[0,3]`, a length-three block fits before either obstacle. ### Constraints - `1 <= queries.length <= 15 * 10^4`. - `2 <= queries[i].length <= 3`. - `1 <= queries[i][0] <= 2`. - Type-1 queries have the form `[1,x]`; type-2 queries have the form `[2,x,sz]`. - `1 <= x, sz <= min(5 * 10^4, 3 * queries.length)` whenever the field occurs. - At each type-1 query, no obstacle already exists at `x`. - At least one query is type 2. ### Clarifying Questions - Can a block touch an obstacle? Yes; an obstacle may coincide with a block endpoint, but cannot be inside the block. - Can a block extend below zero or beyond the query's `x`? No. - Does a successful type-2 query reserve space for later queries? No; it changes no state. - Do earlier obstacles remain? Yes; only insertions occur, and query order matters. ### C++ Interface ```cpp class Solution { public: vector<bool> getResults(vector<vector<int>>& queries) { } }; ``` ### Reasoning Checkpoints - Preserve obstacle insertions in query order while keeping placement checks hypothetical. - Enforce full containment and allow exact fits touching obstacle endpoints. - Consider every possible location within the requested interval and justify resource use under the full bounds. ```hint Maintain the empty intervals Keep obstacle coordinates in an ordered set. Store each gap's length at its right endpoint in a segment tree. An insertion splits one gap; a query combines complete earlier gaps with the final interval truncated at its right boundary. ```