Leetcode3161. 物块放置查询(Go语言的红黑树 + 线段树）

本文主要是介绍Leetcode3161. 物块放置查询(Go语言的红黑树 + 线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目截图

在这里插入图片描述

题目分析

每次1操作将会分裂成两块区间长度，以最近右端点记录左侧区间的长度即可
因此涉及到单点更新和区间查询
然后左右侧最近端点则使用redBlackTree，也就是python中的sortedlist

ac code

type seg []int// 把 i 处的值改成 val
func (t seg) update(o, l, r, i, val int) {if l == r {t[o] = valreturn}m := (l + r) >> 1if i <= m {t.update(o<<1, l, m, i, val)} else {t.update(o<<1|1, m+1, r, i, val)}t[o] = max(t[o<<1], t[o<<1|1])
}// 查询 [0,R] 中的最大值
func (t seg) query(o, l, r, R int) int {if r <= R {return t[o]}m := (l + r) >> 1if R <= m {return t.query(o<<1, l, m, R)}return max(t[o<<1], t.query(o<<1|1, m+1, r, R))
}func getResults(queries [][]int) (ans []bool) {m := 0for _, q := range queries {m = max(m, q[1])}m++set := redblacktree.New[int, struct{}]() // kv对，v就这样摆着先set.Put(0, struct{}{}) // 哨兵set.Put(m, struct{}{})t := make(seg, 2<<bits.Len(uint(m)))for _, q := range queries {x := q[1]pre, _ := set.Floor(x - 1) // x 左侧最近障碍物的位置if q[0] == 1 {nxt, _ := set.Ceiling(x) // x 右侧最近障碍物的位置set.Put(x, struct{}{})t.update(1, 0, m, x, x-pre.Key)       // 更新 d[x] = x - pret.update(1, 0, m, nxt.Key, nxt.Key-x) // 更新 d[nxt] = nxt - x} else {// 最大长度要么是 [0,pre] 中的最大 d，要么是 [pre,x] 这一段的长度maxGap := max(t.query(1, 0, m, pre.Key), x-pre.Key)ans = append(ans, maxGap >= q[2])}}return
}