3161. Block Placement Queries

Array
Binary Indexed Tree
Segment Tree

TIME

O(q log M)

SPACE

O(M)

Intuition

Obstacles split the number line into gaps. For a query [2, x, sz], a block can fit if either:

there is a complete gap of length at least sz ending at an obstacle at or before x
or the tail gap from the last obstacle at or before x to x has length at least sz

So we need two operations:

find the nearest obstacle before and after a newly inserted obstacle
query the maximum completed gap whose right endpoint is at most x

The coordinate values are bounded, so a Fenwick tree can store obstacle positions and find predecessor/successor by order. A segment tree stores completed gap lengths by their right endpoint.

Approach

Add a sentinel obstacle at 0.
Maintain a Fenwick tree over obstacle positions.
- It supports counting obstacles up to a coordinate.
- It can find the coordinate of the kth obstacle.
Maintain a segment tree where gap[pos] is the distance from the previous obstacle to obstacle pos.
For a type 1 query at x:
- find prev, the nearest obstacle before x
- find next, the nearest obstacle after x, if it exists
- add the new completed gap x - prev at position x
- if next exists, its old gap is split, so update gap[next] to next - x
- insert x into the Fenwick tree
For a type 2 query [2, x, sz]:
- find prev, the nearest obstacle at or before x
- get the maximum completed gap with right endpoint <= x
- also check the tail gap x - prev
- return whether the larger of those two values is at least sz

Complexity

Let M be the maximum coordinate appearing in the queries.

Time: O(q log M)
Space: O(M)

Edge Cases

No obstacle before x except 0 -> tail gap is x
Obstacle exactly at x -> tail gap is 0, but completed gaps up to x still count
Inserting an obstacle between two existing obstacles -> the right obstacle's gap must be reduced
A block may touch obstacles, so a gap of length exactly sz is valid

Code

from typing import List


class FenwickTree:
    def __init__(self, size: int) -> None:
        self.size = size
        self.tree = [0] * (size + 1)

    def add(self, index: int, delta: int) -> None:
        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, index: int) -> int:
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

    def find_by_order(self, order: int) -> int:
        index = 0
        bit = 1 << (self.size.bit_length() - 1)

        while bit:
            next_index = index + bit
            if next_index <= self.size and self.tree[next_index] < order:
                index = next_index
                order -= self.tree[next_index]
            bit >>= 1

        return index + 1


class SegmentTree:
    def __init__(self, size: int) -> None:
        self.size = 1
        while self.size < size:
            self.size *= 2
        self.tree = [0] * (2 * self.size)

    def update(self, index: int, value: int) -> None:
        index += self.size
        self.tree[index] = value
        index //= 2

        while index:
            self.tree[index] = max(self.tree[2 * index], self.tree[2 * index + 1])
            index //= 2

    def query(self, left: int, right: int) -> int:
        left += self.size
        right += self.size
        answer = 0

        while left <= right:
            if left % 2 == 1:
                answer = max(answer, self.tree[left])
                left += 1
            if right % 2 == 0:
                answer = max(answer, self.tree[right])
                right -= 1
            left //= 2
            right //= 2

        return answer


class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        """
        3161. Block Placement Queries
        Time: O(q log M)
        Space: O(M)
        """
        max_coordinate = max(query[1] for query in queries)
        fenwick = FenwickTree(max_coordinate + 1)
        segment_tree = SegmentTree(max_coordinate + 1)

        fenwick.add(1, 1)
        obstacle_count = 1
        results = []

        for query in queries:
            if query[0] == 1:
                x = query[1]

                before_count = fenwick.prefix_sum(x)
                previous_obstacle = fenwick.find_by_order(before_count) - 1

                if before_count < obstacle_count:
                    next_obstacle = fenwick.find_by_order(before_count + 1) - 1
                    segment_tree.update(next_obstacle, next_obstacle - x)

                segment_tree.update(x, x - previous_obstacle)
                fenwick.add(x + 1, 1)
                obstacle_count += 1
            else:
                x, size = query[1], query[2]
                count_until_x = fenwick.prefix_sum(x + 1)
                previous_obstacle = fenwick.find_by_order(count_until_x) - 1

                best_completed_gap = segment_tree.query(0, x)
                tail_gap = x - previous_obstacle
                results.append(max(best_completed_gap, tail_gap) >= size)

        return results

import java.util.ArrayList;
import java.util.List;

/**
 * 3161. Block Placement Queries
 * Time: O(q log M)
 * Space: O(M)
 */
class Solution {
    public List<Boolean> getResults(int[][] queries) {
        int maxCoordinate = 0;
        for (int[] query : queries) {
            maxCoordinate = Math.max(maxCoordinate, query[1]);
        }

        FenwickTree fenwick = new FenwickTree(maxCoordinate + 1);
        SegmentTree segmentTree = new SegmentTree(maxCoordinate + 1);
        fenwick.add(1, 1);
        int obstacleCount = 1;

        List<Boolean> results = new ArrayList<>();

        for (int[] query : queries) {
            if (query[0] == 1) {
                int x = query[1];
                int beforeCount = fenwick.prefixSum(x);
                int previousObstacle = fenwick.findByOrder(beforeCount) - 1;

                if (beforeCount < obstacleCount) {
                    int nextObstacle = fenwick.findByOrder(beforeCount + 1) - 1;
                    segmentTree.update(nextObstacle, nextObstacle - x);
                }

                segmentTree.update(x, x - previousObstacle);
                fenwick.add(x + 1, 1);
                obstacleCount++;
            } else {
                int x = query[1];
                int size = query[2];
                int countUntilX = fenwick.prefixSum(x + 1);
                int previousObstacle = fenwick.findByOrder(countUntilX) - 1;

                int bestCompletedGap = segmentTree.query(0, x);
                int tailGap = x - previousObstacle;
                results.add(Math.max(bestCompletedGap, tailGap) >= size);
            }
        }

        return results;
    }

    private static class FenwickTree {
        private final int size;
        private final int[] tree;

        FenwickTree(int size) {
            this.size = size;
            this.tree = new int[size + 1];
        }

        void add(int index, int delta) {
            while (index <= size) {
                tree[index] += delta;
                index += index & -index;
            }
        }

        int prefixSum(int index) {
            int total = 0;
            while (index > 0) {
                total += tree[index];
                index -= index & -index;
            }
            return total;
        }

        int findByOrder(int order) {
            int index = 0;
            int bit = Integer.highestOneBit(size);

            while (bit > 0) {
                int nextIndex = index + bit;
                if (nextIndex <= size && tree[nextIndex] < order) {
                    index = nextIndex;
                    order -= tree[nextIndex];
                }
                bit >>= 1;
            }

            return index + 1;
        }
    }

    private static class SegmentTree {
        private final int size;
        private final int[] tree;

        SegmentTree(int length) {
            int currentSize = 1;
            while (currentSize < length) {
                currentSize *= 2;
            }
            this.size = currentSize;
            this.tree = new int[2 * size];
        }

        void update(int index, int value) {
            index += size;
            tree[index] = value;
            index /= 2;

            while (index > 0) {
                tree[index] = Math.max(tree[2 * index], tree[2 * index + 1]);
                index /= 2;
            }
        }

        int query(int left, int right) {
            left += size;
            right += size;
            int answer = 0;

            while (left <= right) {
                if (left % 2 == 1) {
                    answer = Math.max(answer, tree[left]);
                    left++;
                }
                if (right % 2 == 0) {
                    answer = Math.max(answer, tree[right]);
                    right--;
                }
                left /= 2;
                right /= 2;
            }

            return answer;
        }
    }
}