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

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

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

  1. 莫队

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

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

  1. 移动某一端点

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

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

评论