莫队算法主要是用于离线解决 通常不带修改只有查询的一类区间问题。
以前遇到区间问题的时候一般都是用线段树解决，当然能用线段树解决的问题也在多数。线段树的主要思路就是通过一个左半拉序列 和一个右半拉序列
来维护它们的父亲（也就是两条序列接合在一起的完整序列）
，通过层层递归下去从而完成对整体序列的维护。但在有些时候可能会遇到如下的问题：
给定一个大小为N的数组，数组中所有元素的大小a[i]<=N。你需要回答M个查询。每个查询的形式是L，R。你需要回答在范围[ L，R ]中至少重复3次的数字的个数。
假设此时我们已经分别维护好了左右两边序列中每个数字重复的个数，然后开始向上维护，我们就会发现。。。
Read full article from 莫队算法 (Mo's Algorithm) - 知乎
No comments:
Post a Comment