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

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)
}

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);
}