2024-12-31：物块放置查询。用go语言，在一个无限延伸的数轴上，原点位于 0 处，沿着 x 轴向正方向无限延伸。 现在我

2024-12-31：物块放置查询。用go语言，在一个无限延伸的数轴上，原点位于 0 处，沿着 x 轴向正方向无限延伸。

现在我们有一个二维数组 queries，其中包含两种操作：

1.操作类型 1：queries[i] = [1, x]。在距离原点 x 的位置上建立一个障碍物。保证在执行该操作时，位置 x 上不会有任何障碍物。

2.操作类型 2：queries[i] = [2, x, sz]。检查在数轴范围 [0, x] 内，是否可以放置一个长度为 sz 的物体。该物体必须完全位于 [0, x] 的范围内，且不能与任何障碍物重叠，但可以与障碍物刚好接触。注意，这只是一个查询，不会实际放置物体。每个查询都是独立的。

最终，我们需要返回一个布尔数组 results，在第 i 个操作类型 2 的查询中，如果可以放置物体，则 results[i] 为 true，否则为 false。

1 <= queries.length <= 15 * 10000。

2 <= queries[i].length <= 3。

1 <= queries[i][0] <= 2。

1 <= x, sz <= min(5 * 10000, 3 * queries.length)。

输入保证操作 1 中，x 处不会有障碍物。

输入保证至少有一个操作类型 2 。

输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]。

输出：[false,true,true]。

解释：

查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。

答案2024-12-31：

chatgpt[1]

题目来自leetcode3161。

大体步骤如下：

1.我们首先遍历 queries 数组，找到所有操作中最大的位置值 m，用于初始化相关数据结构。

2.创建两个并查集 uf，分别表示左侧最近障碍物和右侧最近障碍物的位置。

3.创建树状数组 fenwick t，用于快速计算距离左右最近障碍物的距离。

4.对 pos 数组进行排序，pos 中保存所有障碍物位置，并初始化并查集和树状数组。

5.从后向前遍历 queries 数组：

• 对于操作类型 1，更新左右最近障碍物的位置和树状数组中的值。

• 对于操作类型 2，查询左侧最近障碍物的位置 pre，计算最大长度 maxGap，判断是否可以放置物体并记录结果。

最终返回结果数组 ans。

总的时间复杂度为 O(NlogN)，其中 N 为 queries 的长度。并查集和树状数组的构建和更新复杂度都是 O(logN)，排序复杂度为 O(NlogN)。

总的额外空间复杂度为 O(N)，主要是用于存储 pos、uf、fenwick 和结果数组 ans。

Go完整代码如下：

package main

import(

"fmt"

"slices"

)

type fenwick []int

func (f fenwick) update(i, val int){

for; i <len(f); i += i &-i {

      f[i]= max(f[i], val)

}

}

func (f fenwick) preMax(i int)(res int){

for; i >0; i &= i -1{

      res = max(res, f[i])

}

return res

}

type uf []int

func (f uf) find(x int)int{

if f[x]!= x {

      f[x]= f.find(f[x])

}

return f[x]

}

func getResults(queries [][]int)(ans []bool){

  m :=0

  pos :=[]int{0}

for _, q :=range queries {

      m = max(m, q[1])

if q[0]==1{

          pos =append(pos, q[1])

}

}

  m++

  left :=make(uf, m+1)

  right :=make(uf, m+1)

for i :=range left {

      left[i]= i

      right[i]= i

}

  t :=make(fenwick, m)

  slices.Sort(pos)

for i :=1; i <len(pos); i++{

      p, q := pos[i-1], pos[i]

      t.update(q, q-p)

for j := p +1; j < q; j++{

          left[j]= p // 删除 j

          right[j]= q

}

}

for j := pos[len(pos)-1]+1; j < m; j++{

      left[j]= pos[len(pos)-1]// 删除 j

      right[j]= m

}

for i :=len(queries)-1; i >=0; i--{

      q := queries[i]

      x := q[1]

      pre := left.find(x -1)// x 左侧最近障碍物的位置

if q[0]==1{

          left[x]= x -1// 删除 x

          right[x]= x +1

          nxt := right.find(x)// x 右侧最近障碍物的位置

          t.update(nxt, nxt-pre)// 更新 d[nxt] = nxt - pre

}else{

// 最大长度要么是 [0,pre] 中的最大 d，要么是 [pre,x] 这一段的长度

          maxGap := max(t.preMax(pre), x-pre)

          ans =append(ans, maxGap >= q[2])

}

}

  slices.Reverse(ans)

return

}

func main(){

  queries :=[][]int{{1,2},{2,3,3},{2,3,1},{2,2,2}}

  result := getResults(queries)

  fmt.Println(result)

}

在这里插入图片描述Rust完整代码如下：

use std::cmp::max;

use std::collections::HashMap;

structFenwick{

  data:Vec<i32>,

}

implFenwick{

fnnew(size:usize)->Self{

Self{

          data:vec![0; size +1],

}

}

fnupdate(&mutself, i:usize, val:i32){

letmut idx= i asusize;

while idx <self.data.len(){

self.data[idx]=max(self.data[idx], val);

          idx += idx &!(idx -1);

}

}

fnpre_max(&self,mut i:usize)->i32{

letmut res=0;

while i >0{

          res =max(res,self.data[i]);

          i &= i -1;

}

      res

}

}

structUf{

  parent:Vec<usize>,

}

implUf{

fnnew(size:usize)->Self{

letmut parent=Vec::with_capacity(size);

foriin0..size {

          parent.push(i);

}

Self{ parent }

}

fnfind(&mutself, x:usize)->usize{

ifself.parent[x]!= x {

self.parent[x]=self.find(self.parent[x]);

}

self.parent[x]

}

}

fnget_results(queries:Vec<Vec<i32>>)->Vec<bool>{

letmut m=0;

letmut pos=vec![0];

forqin&queries {

      m =max(m, q[1]);

if q[0]==1{

          pos.push(q[1]);

}

}

  m +=1;

letmut left=Uf::new((m +1)asusize);

letmut right=Uf::new((m +1)asusize);

letmut fenwick_tree=Fenwick::new(m asusize);

  pos.sort();

forwindowin pos.windows(2){

let(p, q)=(window[0], window[1]);

      fenwick_tree.update(q asusize, q - p);

forjin(p +1)..q {

          left.parent[j asusize]= p asusize;// 删除 j

          right.parent[j asusize]= q asusize;

}

}

forjin(pos.last().unwrap()+1)..m {

      left.parent[j asusize]=*pos.last().unwrap()asusize;// 删除 j

      right.parent[j asusize]= m asusize;

}

letmut ans=Vec::new();

forqin queries.iter().rev(){

letx= q[1];

letpre= left.find((x -1)asusize);// x 左侧最近障碍物的位置

if q[0]==1{

          left.parent[x asusize]=(x -1)asusize;// 删除 x

          right.parent[x asusize]=(x +1)asusize;

letnxt= right.find(x asusize);// x 右侧最近障碍物的位置

          fenwick_tree.update(nxt, nxt asi32- pre asi32);

}else{

// 最大长度要么是 [0,pre] 中的最大 d，要么是 [pre,x] 这一段的长度

letmax_gap=max(fenwick_tree.pre_max(pre), x - pre asi32);

          ans.push(max_gap >= q[2]);

}

}

  ans.reverse();

  ans

}

fnmain(){

letqueries=vec![vec![1,2],vec![2,3,3],vec![2,3,1],vec![2,2,2]];

letresult=get_results(queries);

println!("{:?}", result);

}

在这里插入图片描述引用链接