K大数查询

news/2024/10/4 13:21:59

标记永久化:1:26:00

如果外层线段树为下标线段树会发现没有办法快速维护,这个时候我们就要想到权值线段树:外层采用权值线段树,其每个节点维护一颗下标线段树,表示这个节点所代表的权值在序列中有多少个。如果\(n=5\),值域大小为\(5\),那么权值线段树如下

image

比如\([4,5]\)这个节点,维护了一颗线段树,如下

image

对于这棵线段树中的\([1,3]\)这个节点,表示的是\(4\)\(5\)在序列下标为\([1,3]\)中出现的总次数

于是修改就可以变成\(O(\log^2n)\)

对于查询,很容易想到用二分,但是时间复杂度为\(O(\log^3n)\);线段树加二分我们一定要想到线段树二分,这样时间复杂度就会变成\(O(\log^2n)\)

对于内层线段树,肯定要使用动态开点;对于区间修改可以使用懒标记和标记永久化,这里如果使用懒标记的话,下传的时候如果儿子没有开点是要先开一个点的,这样可能会导致多开很多个点,于是MLE,所以用标记永久化更能过

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

相关文章

Java--网络编程

目录计算机网络定义网络编程定义网络体系结构OSI 七层参考模型TCP/IP 四层协议TCP/IP 协议族TCP/IP 协议关系常见网络协议IP 协议TCP 协议UDP 协议TCP 与 UDP 区别HTTP 协议Socket 套接字网络通信五要素Socket 通信模型Socket 客户端编程Socket 服务器端编程 计算机网络定义 计…

进程和计划任务管理

查看进程信息 ps ps命令 查看静态的进程统计信息 ps -elf 查看进程信息 top top命令 查看动态的进程排名信息 top 查看进程信息 pgrep pgrep命令 根据特定条件查询进程 PID 信息 pgrep -l “log” pgrep -l -U teacher -t tty1 查看进程信息 pstree pstree命令 以树形结构列出进…

分析和排查系统故障

日志文件2-1 日志的功能 用于记录系统、程序运行中发生的各种事件 通过阅读日志,有助于诊断和解决系统故障 日志文件的分类 内核及系统日志 由系统服务rsyslog统一进行管理,日志格式基本相似 用户日志 记录系统用户登录及退出系统的相关信息 程序日志 由各种应用程序独立管理…

linux基础网络设置

查看网络接口信息 ifconfig 查看所有活动网络接口的信息 执行 ifconfig 命令 查看指定网络接口信息 ifconfig 网络接口名 查看主机名称hostname hostname命令 查看或设置当前主机名 hostname 查看路由表条目 route route命令 查看或设置主机中路由表信息 route -n 查看网络连接…

磁盘和文件系统管理(一)

检测并确认新硬盘 fdisk命令 查看或管理磁盘分区 fdisk -l [磁盘设备] 或 fdisk [磁盘设备] 交互模式中的常用指令 m、p、n、d、t、w、q d delete a partition * 删除分区 g create a new empty GPT partition table 创建一个新的空的GPT分区表(可以对大于2T磁盘进行分区) l li…

linux操作系统

Linux操作系统安装及服务控制 开源软件 没有商业化软件版权约束,源代码开发,可无约束自由传播---自由并不意味着免费 FSF 自由软件基金会,由1984年创办;主要的项目包含了GNU项目 为什么选择Linux? 开源 免费 稳定 服务器 不但降低企业运行成本,而且还提升了更高的稳定性和…

记录vue3写项目遇到的奇奇怪怪怪的小问题(持续更新)

<el-table:header-cell-style="{ color: #fff, background:rgba(78, 131, 211, 0.8) }"// 设置table表头样式> </el-table>表头居中 :cell-style="{text-align:center}" 表行居中<el-table-columnprop="xxx"align="center&q…

如何安装peiqi文库

一:安装包下载 方法一:hithub上搜索peiqi方法二:使用自己搭建的ubuntu,kali,linux都可。我用的ubuntu 输入命令:git clone https://gitee.com/peiqi0/PeiQi-WIKI-Book.git二:查看安装情况 1:ls查看是否安装成功2:cd 进入3:安装nmp sudo apt-get install npm4:通过np…