关于静态 RMQ 问题
1. 普通做法
- ST 表:\(O(n\log n+q)\)
- Sqrt Tree:\(O(n\log\log n+q)\)
- 线段树 / zkw 线段树:\(O(n + q\log n)\) .
- 猫树:\(O(n\log n+q)\)
- 单调栈:\(O(q\log q+q\log n)\)
2. Four Russian 算法
先分块,假设块长为 \(B\) .
预处理整块的最小值,把每个整块连起来然后开个 ST 表,对每个零散块也开 ST 表
我们可以将询问区间划分为不超过 \(1\) 个整块数组上的连续块区间和不超过 \(2\) 个原数组上的整块内的连续区间。显然这些问题我们通过 ST 表上的区间查询解决。
取 \(B=\log n\),预处理复杂度就是 \(O(n\log\log n)\) 的,常数较大 .
一个小优化:我们发现,在询问的两个端点属于不同的块的时候,块内的询问是关于每一块前缀或者后缀的询问,用 \(O(n)\) 预处理答案,这样子我们只需要在询问的时候进行至多一次 ST 表上的查询操作了 .
3. 随机数据的一种做法
题目:由乃救爷爷
分块,设块长为 \(B\),当然先预处理每个整块的最小值
若区间跨过了多个块,那么整块可以 st 表处理,零散块可以预处理每个块内的前缀后缀最小值处理 .
若区间左右端点正好在同一个块内,暴力扫,复杂度 \(O(B)\) 比较高,但注意到询问区间随机的情况下,不难得出两个端点在同一个块内的概率是 \(\dfrac Bn\) .
所以这种情况期望复杂度 \(O\left(\dfrac{B^2}n\right)\) .
当 \(b\) 至少为 \(O(\log n)\) 时,预处理整块 st 表复杂度 \(O\left(\dfrac nB\log\dfrac nB\right)\) 不超过 \(O(n)\) .
当 \(b\) 至多为 \(O(\sqrt n)\) 时,预处理整块 st 表复杂度 \(O\left(q\dfrac Bn\right)\) 不超过 \(O(q)\) .
所以 \(b\) 取 \(O(\log n)\) 到 \(O(\sqrt n)\) 之间的一个值即可 .
当 \(b=\sqrt n\) 时,直接暴力预处理所有可能区间的最大值即可,复杂度不变,常数可能小一些 .
4. 有关转 LCA 的做法
1.1. RMQ 转 LCA 再转 ±1RMQ(RMQ 标准算法)
先 \(O(n)\) 建序列的笛卡尔树,不难发现两个点之间的最小值就是它们的 LCA 的权值 .
使用基于 RMQ 的树上 LCA 算法,发现笛卡尔树的欧拉序相邻两个节点深度差必然为 \(\pm 1\) .
我们假设我们在 word-RAM model 中 .
由于相邻两个元素之差为 \(1\),那么长度为 \(n\) 的本质不同的序列只有 \(2^n\) 个 .
考虑将序列按照 \(\dfrac12\log n\) 分段,在 word-RAM model 中,一个常见的假设是字长 \(w\ge \log n\),注意到长度为 \(\dfrac 12\log_2 n\) 的本质不同的数列只有 \(O(\sqrt n)\) 个,我们可以枚举所有可能的情况,并枚举左右端点,这可以在 \(O(\sqrt n\log^2 n)\) 的时间复杂度内完成 .
因为一个数列长度为 \(n\) 的数列可以用二进制串编码(对于一个序列 \(a\),其二进制串编码的第 \(j\) 位为 \([a_j<a_j+1]\))
对于分成的 \(O\left(\dfrac{n}{\log n}\right)\) 段,使用 ST 表维护 .
从而对于零散块来说,查表即可得出答案,我们也就得到了 \(O(n)\) - \(O(1)\) 的求解一般 RMQ 问题的解法
好像可以把块内用线段树维护,整块用 st 表,或许会更快 .
1.2. 一个优化
对于每个块维护一个单调队列,再把单调队列状压 .
这份提交 好像是这种写法
2. RMQ 转 LCA 然后 tarjan 求 LCA
RMQ 转 LCA 上面已经说过了,tarjan 求 LCA 是可以优化到线性的,给两个链接:
- tarjan 的论文:https://core.ac.uk/download/pdf/82125836.pdf
- UOJ 大佬的博客:https://ljt12138.blog.uoj.ac/blog/4874
离线并查集是 \(O(n\alpha(n))\) 的,本质相似,实际跑起来会快一些 .
3. RMQ 转 LCA 然后 Schieber Vishkin algorithm 求 LCA
同 \(2\),Schieber Vishkin algorithm 的描述可以在 这里 找到
5. 一个 \(O(n\log^*n)\) - \(O(1)\) 的算法
考虑左右端点在同一块内的时候,把小块当成一个整序列,也是分块,从而预处理时间 \(T(n)\) 满足
\]
不难发现,递归的深度是 \(O(\log^* n)\)
从而预处理时间复杂度 \(O(n\log ^* n)\),询问时间复杂度 \(O(\log^* n)\)
我们不妨假设每层大块长都是 \(2\) 的幂,这样分出来的小段长都是一样的:\(\log n,\log\log n,\cdots,1\)
对于一个询问,若其区间长度是 \(L\),我们找出第一个小段长 \(\le L\) 的层,可以发现这个询问一定可以在这一层或者上一层 \(O(1)\) 回答出来。这样只要对每个询问长度预处理找的层就可以做到 \(O(1)\) 询问了 .
最新文章
- Google副总裁的管理经验
- 浏览器的visibilitychange 事件ie10以下不兼容
- html5非常火,他究竟与html4有何差别?
- Cocos2d-x 创建(create)动画对象CCAnimation报错分析
- [刷题]算法竞赛入门经典(第2版) 5-10/UVa1597 - Searching the Web
- cat和tac的用法
- 初识CSS
- HDU 2503 a/b + c/d(最大公约数与最小公倍数,板子题)
- [转帖]/etc/security/limits.conf的含义
- Python 入门基础16 -- ATM + 购物车
- 从返回的json格式的data数据内随机取得n个
- nginx 添加虚拟主机 支持php 伪静态
- 《Python》 基础数据类型补充和深浅copy
- virsh 操作kvm虚拟机
- QT之QML控件篇
- Nginx not running with no error message
- 如何往eclipse中导入maven项目
- 【原创】U盘插入磁盘显示脱机解决
- eclipse.ini X64 Oxygen.2 Release (4.7.2) lombok
- SQL DISTINCT 用法(去重)
热门文章
- Go内存管理一文足矣
- linux篇-linux mysql5.6.27源码安装和错误解决
- pyecharts世界地图用:国家中英文对照表.xlsx
- python读取csv、excel、mysql内容
- SQLServer2008中的Merge
- 《Unix 网络编程》08:基本UDP套接字编程
- vue运行npm run dev时候,自动打开页面
- 树莓派开发笔记(十五):树莓派4B+从源码编译安装mysql数据库
- Halodoc使用 Apache Hudi 构建 Lakehouse的关键经验
- python实现对简单的运算型验证码的识别【不使用OpenCV】