Block-Building Operations: Check Whether a Free Segment Starts at a Position

Positions on a number line start out empty. Process a list of operations in order:

• [1, x]: build a block at position x.
• [2, x, k]: check whether something of length k can be built starting at position x, meaning that positions x, x + 1, ..., x + k - 1 hold no block. Record "1" if all of them are free and "0" otherwise. A check builds nothing.

Return the recorded characters concatenated in the order of the checks.

Function Signature

def process_operations(operations: list[list[int]]) -> str:

Rules

• Building at a position that already holds a block changes nothing.
• A check depends only on blocks built by earlier operations in the list.
• Only positions x through x + k - 1 matter for a check; blocks at x - 1 or x + k do not make it fail.
• Return the empty string if there are no checks.

Constraints

• 1 <= len(operations) <= 10^5
• Each operation is either [1, x] or [2, x, k].
• 1 <= x <= 10^9 and 1 <= k <= 10^9, so x + k - 1 <= 2 * 10^9 - 1, which fits in a 32-bit signed integer.

Examples

Example 1

Input:  operations = [[1, 2], [1, 5], [2, 3, 2], [2, 3, 3], [2, 1, 1], [2, 1, 2]]
Output: "1010"

Blocks stand at 2 and 5. Positions 3 and 4 are free: "1". Positions 3, 4 and 5 include the block at 5: "0". Position 1 is free: "1". Positions 1 and 2 include the block at 2: "0".

Example 2

Input:  operations = [[2, 10, 5], [1, 12], [1, 12], [2, 10, 2], [2, 10, 3], [2, 13, 100]]
Output: "1101"

The first check runs before any block exists: "1". The second build at 12 changes nothing. Positions 10 and 11 are free: "1". Positions 10 to 12 include the block at 12: "0". Positions 13 to 112 are free, and the block at 12 just before them does not matter: "1".

Example 3

Input:  operations = [[1, 1]]
Output: ""

There are no checks.

Block Building and Free-Window Checks on a Number Line

Hints

1. A check fails exactly when at least one block built by an earlier operation lies in the closed range from x to x + k - 1, so think about the blocks rather than about every position in the window.
2. k can be as large as 10^9, so visiting every position in a window one by one is far too slow.
3. Only earlier operations count, and building where a block already stands adds nothing: process the list strictly in order.

Approach

Collect every position that any build operation names, sort them and remove duplicates. These at most 10^5 values are the only places a block can ever stand, so each one gets a slot in a Fenwick (binary indexed) tree that counts built blocks, plus a built flag. Then replay the operations in order. A build finds its slot by binary search and, only if that slot is not built yet, marks it and adds 1 to the tree, so building where a block already stands changes nothing. A check computes last = x + k - 1, finds lo = the first slot whose position is >= x and hi = the first slot whose position is > last, and counts the built blocks in slots lo..hi-1 as prefix(hi) - prefix(lo); it records '1' when that count is 0 and '0' otherwise. Invariant: just before operation i is processed, the tree holds a 1 exactly at the slots of positions built by operations 0..i-1, so a check sees only earlier builds. Correctness: slots lo..hi-1 are exactly the build positions inside the closed range [x, x + k - 1], so the count is zero if and only if every position in the range is free; a block at x - 1 has a slot below lo and a block at x + k has a slot at or above hi, so neither is counted. Edge cases: with no builds the tree is empty and every check records '1'; with no checks the result is the empty string; k up to 10^9 is never walked position by position. x + k - 1 is at most 2 * 10^9 - 1, which fits in 32 bits; the Java and C++ references still widen it to 64 bits before adding.

• Time complexity: O(n log n)
• Space complexity: O(n)