离线算法

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

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

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

1. 莫队

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

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

2. 移动某一端点

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

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