莫队是一种对于询问做转移的算法。
对于可以离线, 运算可逆的题目。
如果按题目给的顺序操作, 可以被以下数据 hack
1 1
n n
1 1
n n
1 1
n n
1 1
n n
...
时间复杂度 \(O(n^2)\)。
我们可以通过某一些排序来降低时间复杂度。
首先, 把这个序列分成 \(\sqrt{n}\) 块, 每一块按右端点递增排序。
证明时间复杂度。
对于每一块, 右端点移动总共次数最多为 \(n\), 左端点一次最多移动 \(\sqrt{n}\), 所有快左端点移动一起最多一起 \(q \sqrt {n}\)。对于任意两个快, 最多右端点移动 \(n\), 最短点移动 \(\sqrt{n}\), 有 \(\sqrt{n}\) 个这种, 所以总时间复杂度为 \(O((n + q)\sqrt{n})\)。
伪代码
for(; l > q[i].l; add(--l)){ // 前面已经算过了 l 的贡献
}
for(; r < q[i].r; add(++r)){ // 前面已经算过了 r 的贡献
}
for(; l < q[i].l; del(l++)){ // 前面已经算过了 l 的贡献, 当前查询不在区间
}
for(; r > q[i].l; del(r--)){ // 前面已经算过了 r 的贡献, 不在当前查询区间
}