Leetcode每日一题 —— 3161. 物块放置查询

3161. 物块放置查询 - 力扣（LeetCode）

3161. 物块放置查询 - 有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。 给你一个二维数组 queries ，它包含两种操作： 1. 操作类型 1 ：queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。 2. 操作类型 2 ：queries[i] = [2, x, sz] 。判断在数轴范围 [0, x] 内是否可以放置一个长度为 sz 的物块，这个物块需要 完全 放置在范围 [0,...

力扣我真得控制你了，昨天给把糖，今天直接来一巴掌。这题挺有难度，看了题解才磨出来。

综合考察了二分查找和常见线段树（单点修改、区间查询）。

思路

1. 新增与查询

题目中主要是两个操作，新增一个障碍物，或者查询一个障碍物左边最长的空闲段长度是否 \ge sz。

1. 每次 [1, x] 在 x 位置新增障碍物，都会把一段空闲区间切分为两段。
2. 而每次 [2, x, sz] 进行查询时，我们只在意 [0, x] 区间中最大的空闲区间长度是否至少为 sz。

对于第 2 点，我们会进行多次的单点修改，且需要查询一个区间的最大值，因此可以用到常见的单点修改、区间查询线段树。

对于第 1 点，为了方便后续查询以及进一步的障碍物插入，我们每次插入肯定要知道 x 左边和右边的障碍物位置。这里就可以用有序集合来维护。

2. 线段树维护的内容

我们在查询的时候只在意某个位置 x 的左边最大的空闲区间长度，也就是说查询时希望能查出 [0, x] 区间的最大值。但注意，查询的这个 x 不一定是障碍物。

题目中插入的是障碍物，为了方便起见，线段树中修改的点位也应该都是障碍物，没有经历过任何修改的点位值置为 0，说明此处没有障碍物。

查询已经知道了，线段树中单个节点其实表示的就应该是：这个障碍物节点对应的区间内，所有以障碍物为结束端点的空闲段长度的最大值。

叶子节点值就表示某个障碍物距离左边相邻障碍物的长度（即某个障碍物位置左边相邻的空闲段长度），单点修改，其实修改的就是这个值。

• 如果值为 0，则表示这个位置没有障碍物。

3. 线段树的更新

每次插入新的障碍物 x 时，设其左边和右边相邻的障碍物位置为 prev 和 next，x 会把 [prev, next] 劈开成 [prev, x] 和 [x, next]。

上面已经提到我们单点修改修改的是叶结点值，而叶节点值表示某个位置左侧相邻的空闲段长度，因此这里涉及 x 和 next 两个障碍物端点的修改。

显然修改后的值分别为 x-prev, next-x。

• 修改完后上推更新树的非叶节点。

4. 查询

查询时题目给出 [2, x, sz]，我们只需要找到 [0, x] 区间内最长的空闲段长度，看看是不是 \ge sz 即可。

但是要注意，这里不能直接用线段树，从上面第 2 节可以看到线段树是根据障碍物位置来更新的，查询的 x 位置不一定是障碍物。

因此我们要先找到 x 的左边相邻障碍物位置 prev，在线段树中查询 [0, prev]，然后再计算 x-prev 这个空闲段长度，最后再在二者中取最大值和 sz 比较。

• 显然 x 位置为障碍物时，x-prev=0

代码

class SegmentTree{
private:
    int n;
    vector<int> tree; // 为了方便，下标从 1 开始
public:
    SegmentTree(int n){
        this->n=n;
        // 线段树预留 4N 空间，因为这里下标从 1 开始，所以 N=n+1，留 4*(n+1)
        // 初始全为 0，表示没有障碍物
        tree.resize(n*4+4,0);
    }

    // 单点更新
    // idx 为新加入的障碍物下标
    // dist 为新障碍物 idx 距离其左边上一个障碍物 prev 的距离
    // node 为树中结点下标，从 1 开始
    // l, r 表示 node 结点对应的区间
    void update(int idx,int dist,int node,int l, int r){
        if(l==r){
            // 单个点
            tree[node]=dist;
            return;
        }

        int mid=l+((r-l)>>1);
        if(idx<=mid){
            // 下标在区间左侧，进入左半边树
            update(idx,dist,node<<1,l,mid);
        }else{
            // 否则进入右半边树
            update(idx,dist,(node<<1)+1,mid+1,r);
        }
        // 上推更新区间最大值
        tree[node]=max(tree[node<<1],tree[(node<<1)+1]);
    }

    // 重载函数，作为更简便的入口
    void update(int idx,int dist){
        update(idx,dist,1,0,n);
    }

    // 查询区间
    int query(int queryL,int queryR,int node,int l, int r){
        if(queryL>queryR){
            // 区间不合法
            return 0;
        }
        if(queryL<=l&&r<=queryR){
            // [l, r] 已经在 [queryL, queryR] 区间内，返回 [l, r] 区间最大值
            return tree[node];
        }
        int mid=l+((r-l)>>1);
        int res=0;

        // [queryL, queryR] 拆为两半处理
        if(queryL<=mid){
            res=max(res,query(queryL,queryR,node<<1,l,mid));
        }

        if(queryR>mid){
            res=max(res,query(queryL,queryR,(node<<1)+1,mid+1,r));
        }

        // 取最大值作为查询结果
        return res;
    }

    // 重载函数，作为更简便的入口
    int query(int queryL,int queryR){
        return query(queryL,queryR,1,0,n);
    }
};

class Solution {
public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        // 肯定要用到线段树，应该是单点修改区间查询
        // 
        // 1. 每次新增障碍物，都会把一段空闲区间切成两段
        //    对于插入操作 [1, x]，需要知道插入 x 时 x 左边、右边最近的障碍物在哪
        //
        // 2. 而查询 [2, x, sz] 时，我们只在意 [0, x] 区间**最大**的空闲长度是否至少为 sz
        //
        // 对于第 1 点可以用有序集合
        // 第 2 点的话就要用线段树来维护**区间最大值**了
        //
        // 线段树中叶子节点值表示**某个障碍物**左边相邻空闲区间的长度
        // 
        // 注意线段树维护的是障碍物为结束端点的区间最大值，但我们查询时的点并不一定是障碍物
        // 因此查询 x 时需要：  
        // 1. 找到距离 x 左边最近的障碍物 prev，线段树查询 [0, prev] 最大值
        // 2. 计算 x-prev （因为查询的 x 并不一定是障碍物，不在线段树中，这段距离得补上）
        // 二者取最大值

        int maxX=0; // 找到涉及的 x 最大值，用于开树
        for(auto&q:queries){
            maxX=max(maxX,q[1]);
        }

        // 用有序集合维护障碍物位置
        set<int> obs;
        // 添加哨兵，0 和 maxX+1 这个位置都可以算障碍物，方便后面查询 prev 和 next
        obs.insert(0);
        obs.insert(maxX+1);
        maxX++;
        // 开树
        SegmentTree tree(maxX);

        vector<bool> res;

        // 处理查询
        for(auto& q:queries){
            int x=q[1]; // 要查询 / 插入的 x
            if(q[0]==1){
                // 插入障碍物 x，保证插入时这里没有障碍物
                // 先利用 C++ 标准库的二分 upper_bound 算法找到 x 位置的下一个障碍物
                auto nextIt=obs.upper_bound(x);
                // nextIt 的上一个位置就是 x 的上一个障碍物
                auto prevIt=std::prev(nextIt);
                int next=*nextIt;
                int prev=*prevIt;
                // 把 x 插入有序集合（插入新障碍物）
                obs.insert(x);
                // 插入新障碍物后要上推更新线段树
                // 插入 x 后，[prev, next] 被截为 [prev, x], [x, next]
                // 线段树维护的是某个障碍物左边的最大空闲区间长度，因此这里要更新 x 和 next 两个端点
                tree.update(next,next-x); // next 端点，左边空闲区间长度变成 next-x
                tree.update(x,x-prev); // x 端点，左边空闲区间长度变成 x-prev
            }else{
                // 查询
                int sz=q[2];
                // 注意线段树只维护障碍物
                // 查询时 x 不一定是障碍物，因此要先找到 prev
                auto nextIt=obs.upper_bound(x);
                int prev=*(std::prev(nextIt));
                // obs 存的是障碍物，所以 prev 肯定是障碍物，我们可以查询 [0, prev]
                int prevMaxLen=tree.query(0,prev);
                // x 相邻的还有一段 x-prev，如果 x 是障碍物，显然 x-prev=0
                int adjMaxLen=x-prev;
                res.emplace_back(max(prevMaxLen,adjMaxLen)>=sz);
            }
        }
        return res;
    }
};

[!WARNING]
这里最开始我还踩了个坑导致 TLE（时间超限），最开始我用的是 C++ <algorithm> 头中的 upper_bound 二分找上界方法。
但是其主要适用于能随机访问的容器，如 vector，对于无法随机访问的 set ，其时间复杂度会退化到 O(n)。

解决方式就是用 set 自己的成员函数 upper_bound 来实现红黑树结构上的近似二分查找。

2 个帖子 - 2 位参与者

阅读完整话题