离线算法

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