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

2024-05-29 08:20

本文主要是介绍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
}

这篇关于Leetcode3161. 物块放置查询(Go语言的红黑树 + 线段树)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1013133

相关文章

go中空接口的具体使用

《go中空接口的具体使用》空接口是一种特殊的接口类型,它不包含任何方法,本文主要介绍了go中空接口的具体使用,具有一定的参考价值,感兴趣的可以了解一下... 目录接口-空接口1. 什么是空接口?2. 如何使用空接口?第一,第二,第三,3. 空接口几个要注意的坑坑1:坑2:坑3:接口-空接口1. 什么是空接

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

MySQL多列IN查询的实现

《MySQL多列IN查询的实现》多列IN查询是一种强大的筛选工具,它允许通过多字段组合快速过滤数据,本文主要介绍了MySQL多列IN查询的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析与优化1.

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu