优雅的暴力——莫队算法学习笔记

首先，如果有一道区间可扩张收缩的题（不需要支持离线），你是不是可以先求出第一个区间的答案，然后通过左右端点的扩张和收缩求出其它区间的答案，但是你会发现最坏时间复杂度跟暴力的
\(O(qn)\) 一样，但是这个时候神奇的事情就来了，我们给它将询问离线一下，然后通过一种神奇的排序之后，它的时间复杂度就变成了
\(O((q+n) \sqrt n)\) 了！这个神奇的排序是什么呢，就是先将
\(1\) 到
\(n\) 的所有点分个块，然后排序时先按照
\(l\) 所在的块从小到大排序，如果有两个
\(l\) 相等，再按照
\(r\) 的从小到大排序。