今天花了一整天练习数据结构,尤其是基础根号算法。其中最有特色的当属离线算法。
在很久远的过去(大概是2017年春),无知的我在写洛谷月赛的数据结构题时,就有了离线的思想,但并没有想到太多有效的离线算法。
下面总结一些常见的离线算法。
- 莫队
莫队算是一种比较通用的离线算法。普通莫队可以处理没有修改操作、能够移动区间左右端点的题目,主要思想是对询问进行分块,使得在块内左端点移动量较小、右端点单调移动,时间复杂度。带修莫队增加时间维度,对左右端点都分块,支持单点的修改操作,时间复杂度。
代码实现上需要注意的是std::sort
的比较函数。
- 移动某一端点
在莫队的时间复杂度无法承受的时候,我们也可以考虑多记录一些信息,在使某一端点单调移动的同时,保留另一端点的所有信息。即移动端点或;对于某确定的,查询某一的答案的时间也为或。这样就可以实现。
典型题目有询问区间不同元素数。