3161. 区块放置查询

Hard

题目描述

存在一条无限长的数线，原点位于 0，向正 x 轴方向延伸。

给你一个二维数组 queries，包含两种类型的查询：

对于类型 1 的查询，queries[i] = [1, x]。在距离原点 x 的位置建造一个障碍物。保证查询时在距离 x 处没有障碍物。
对于类型 2 的查询，queries[i] = [2, x, sz]。检查是否可以在范围 [0, x] 内的任何位置放置一个大小为 sz 的区块，使得区块完全位于范围 [0, x] 内。区块不能与任何障碍物相交，但可以接触。注意，你实际上并不放置区块。查询是独立的。

返回一个布尔数组 results，其中 results[i] 为 true 表示可以放置第 i 个类型 2 查询中指定的区块，否则为 false。

示例 1：

输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
输出：[false,true,true]
解释：
查询 0：在 x = 2 处放置障碍物。最多可以在 x = 3 之前放置大小为 2 的区块。

示例 2：

输入：queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
输出：[true,true,false]
解释：
查询 0：在 x = 7 处放置障碍物。最多可以在 x = 7 之前放置大小为 7 的区块。
查询 2：在 x = 2 处放置障碍物。现在最多可以在 x = 7 之前放置大小为 5 的区块，在 x = 2 之前放置大小为 2 的区块。

约束：

1 <= queries.length <= 15 * 10^4
2 <= queries[i].length <= 3
1 <= queries[i][0] <= 2
1 <= x, sz <= min(5 * 10^4, 3 * queries.length)
对于类型 1 的查询，保证查询时在距离 x 处不存在障碍物
保证至少有一个类型 2 的查询

解题思路

这道题的核心思路是维护每个位置到下一个障碍物的距离。

解题思路：

核心观察：要在区间 [0, x] 中放置大小为 sz 的区块，我们需要找到一个连续的空间，其长度至少为 sz。如果我们知道每个位置到下一个障碍物的距离，那么问题就转化为：在区间 [0, x-sz] 中是否存在某个位置 i，使得从位置 i 到下一个障碍物的距离大于等于 sz。
数据结构选择：使用线段树来维护区间最大值。对于每个位置 i，我们维护 d[i] 表示从位置 i 到下一个障碍物的距离。
算法流程：
- 初始化时，假设在很远的地方（如 50001）有一个虚拟障碍物
- 对于类型 1 查询（添加障碍物）：在位置 x 添加障碍物，更新所有受影响位置的 d 值
- 对于类型 2 查询（检查是否可放置区块）：查询区间 [0, x-sz] 的最大 d 值是否大于等于 sz
优化细节：
- 使用坐标压缩，只处理查询中出现的坐标
- 线段树支持单点更新和区间查询最大值
- 添加障碍物时，需要更新该障碍物前面所有位置到下一个障碍物的距离

代码实现

class Solution {
public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        set<int> obstacles;
        obstacles.insert(50001); // 虚拟障碍物
        
        vector<bool> results;
        
        for (auto& query : queries) {
            if (query[0] == 1) {
                // 添加障碍物
                obstacles.insert(query[1]);
            } else {
                // 检查是否可以放置区块
                int x = query[1], sz = query[2];
                if (sz > x) {
                    results.push_back(false);
                    continue;
                }
                
                bool canPlace = false;
                // 检查每个可能的起始位置
                for (int start = 0; start <= x - sz; start++) {
                    // 找到start位置之后的第一个障碍物
                    auto it = obstacles.upper_bound(start);
                    int nextObstacle = *it;
                    
                    if (start + sz <= min(nextObstacle, x)) {
                        canPlace = true;
                        break;
                    }
                }
                results.push_back(canPlace);
            }
        }
        
        return results;
    }
};

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        import bisect
        
        obstacles = [50001]  # 虚拟障碍物
        results = []
        
        for query in queries:
            if query[0] == 1:
                # 添加障碍物
                bisect.insort(obstacles, query[1])
            else:
                # 检查是否可以放置区块
                x, sz = query[1], query[2]
                if sz > x:
                    results.append(False)
                    continue
                
                can_place = False
                # 检查每个可能的起始位置
                for start in range(x - sz + 1):
                    # 找到start位置之后的第一个障碍物
                    idx = bisect.bisect_right(obstacles, start)
                    next_obstacle = obstacles[idx]
                    
                    if start + sz <= min(next_obstacle, x):
                        can_place = True
                        break
                
                results.append(can_place)
        
        return results

public class Solution {
    public IList<bool> GetResults(int[][] queries) {
        var obstacles = new SortedSet<int>();
        obstacles.Add(50001); // 虚拟障碍物
        
        var results = new List<bool>();
        
        foreach (var query in queries) {
            if (query[0] == 1) {
                // 添加障碍物
                obstacles.Add(query[1]);
            } else {
                // 检查是否可以放置区块
                int x = query[1], sz = query[2];
                if (sz > x) {
                    results.Add(false);
                    continue;
                }
                
                bool canPlace = false;
                // 检查每个可能的起始位置
                for (int start = 0; start <= x - sz; start++) {
                    // 找到start位置之后的第一个障碍物
                    int nextObstacle = obstacles.GetViewBetween(start + 1, int.MaxValue).Min;
                    
                    if (start + sz <= Math.Min(nextObstacle, x)) {
                        canPlace = true;
                        break;
                    }
                }
                results.Add(canPlace);
            }
        }
        
        return results;
    }
}

var getResults = function(queries) {
    const coordinates = [...new Set([0, ...queries.filter(query => query[0] === 1).map(query => query[1])])]
        .sort((a, b) => a - b);
    const rank = new Map(coordinates.map((value, index) => [value, index]));
    const activeTree = new Array(coordinates.length + 1).fill(0);
    const gapTree = new Array(4 * coordinates.length).fill(0);

    const addActive = index => {
        for (index++; index <= coordinates.length; index += index & -index) {
            activeTree[index]++;
        }
    };

    const activeCount = end => {
        let count = 0;
        for (let index = end; index > 0; index -= index & -index) count += activeTree[index];
        return count;
    };

    const findByOrder = order => {
        let index = 0;
        let step = 1;
        while ((step << 1) <= coordinates.length) step <<= 1;
        for (; step > 0; step >>= 1) {
            const next = index + step;
            if (next <= coordinates.length && activeTree[next] < order) {
                index = next;
                order -= activeTree[next];
            }
        }
        return index;
    };

    const updateGap = (node, left, right, index, value) => {
        if (left === right) {
            gapTree[node] = value;
            return;
        }
        const middle = (left + right) >> 1;
        if (index <= middle) updateGap(node * 2, left, middle, index, value);
        else updateGap(node * 2 + 1, middle + 1, right, index, value);
        gapTree[node] = Math.max(gapTree[node * 2], gapTree[node * 2 + 1]);
    };

    const queryGap = (node, left, right, queryRight) => {
        if (right <= queryRight) return gapTree[node];
        const middle = (left + right) >> 1;
        let result = queryGap(node * 2, left, middle, queryRight);
        if (queryRight > middle) {
            result = Math.max(result, queryGap(node * 2 + 1, middle + 1, right, queryRight));
        }
        return result;
    };

    addActive(0);
    const results = [];

    for (const query of queries) {
        if (query[0] === 1) {
            const index = rank.get(query[1]);
            const before = activeCount(index);
            const total = activeCount(coordinates.length);
            const predecessor = findByOrder(before);

            if (before < total) {
                const successor = findByOrder(before + 1);
                updateGap(1, 0, coordinates.length - 1, successor,
                    coordinates[successor] - coordinates[index]);
            }

            addActive(index);
            updateGap(1, 0, coordinates.length - 1, index,
                coordinates[index] - coordinates[predecessor]);
        } else {
            const x = query[1];
            const size = query[2];
            let right = coordinates.length - 1;
            while (right > 0 && coordinates[right] > x) {
                let low = 0;
                let high = right;
                while (low < high) {
                    const middle = Math.ceil((low + high) / 2);
                    if (coordinates[middle] <= x) low = middle;
                    else high = middle - 1;
                }
                right = low;
            }

            const count = activeCount(right + 1);
            const predecessor = findByOrder(count);
            const longest = Math.max(
                queryGap(1, 0, coordinates.length - 1, right),
                x - coordinates[predecessor]
            );
            results.push(longest >= size);
        }
    }

    return results;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(n × m)，其中 n 是查询数量，m 是坐标范围。对于每个类型2查询，最坏情况下需要检查 O(m) 个起始位置
空间复杂度	O(k)，其中 k 是障碍物的数量，用于存储障碍物位置

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目