Sweetlemon 的博客

Sweetlemon 的博客

离线算法

posted on 2019-04-09 20:41:58 | under 算法笔记 |

今天花了一整天练习数据结构,尤其是基础根号算法。其中最有特色的当属离线算法。

在很久远的过去(大概是2017年春),无知的我在写洛谷月赛的数据结构题时,就有了离线的思想,但并没有想到太多有效的离线算法。

下面总结一些常见的离线算法。

  1. 莫队

莫队算是一种比较通用的离线算法。普通莫队可以处理没有修改操作、能够 $\mathrm{O}(1)$ 移动区间左右端点的题目,主要思想是对询问进行分块,使得在块内左端点移动量较小、右端点单调移动,时间复杂度 $\mathrm{O}(n\sqrt{n})$ 。带修莫队增加时间维度,对左右端点都分块,支持单点的修改操作,时间复杂度 $\text{O}(n^{\frac{5}{3}})$ 。

代码实现上需要注意的是std::sort的比较函数

  1. 移动某一端点

在莫队的时间复杂度无法承受的时候,我们也可以考虑多记录一些信息,在使某一端点单调移动的同时,保留另一端点的所有信息。即移动端点 $\mathrm{O}(1)$ 或 $\mathrm{O}(\log n)$ ;对于某确定的 $r$ ,查询某一 $l$ 的答案的时间也为 $\mathrm{O}(1)$ 或 $\mathrm{O}(\log n)$ 。这样就可以实现 $\mathrm{O}(m\log n)$ 。

典型题目有询问区间不同元素数