对于一个区间问题，莫队总是一个很好的选择。

现在，我们就来学习一下莫队这个好用毒瘤的算法——莫队。

什么是莫队&莫队的基本思路

比如说，现在你有个序列，每次询问求出 $l$ 到 $r$ 所有数的和。

虽然你可以用最最最普通的前缀和轻松做出，但是我们假装不行。

假设，题目中所给出的序列为 $"1537562"$，现在，如果已经求出 $2$ 到 $4$ 的和为 $15$ ，那么如果题目要求求出 $2$ 到 $5$ 的和怎么办？显然很简单，只要将第 5 位的数字 $5$ 加上，就可以得出答案 $15+5=20$.

反之，如果题目问你 $3$ 到 $4$ 的呢？跟上述方法相似，只需将第 2 位减掉，就能算出答案为 $15-5=10$ 了。于是，我们便用一个数组存储答案，不断记录即可。这就是莫队的基本思想。

但如何用代码实现呢，我们可以定义两个指针为 $l,r$ 分别指向当前所处理到的位置，如果 $l$ 小于答案所需的 $l$ 就将 $l$ 后移，同时舍弃当前数，反之，将 $l$ 指针前移，加上前面的数即可，$r$ 的操作和 $l$ 类似。

但是，该算法复杂度堪忧，最坏情况下可达到 $O(nq)$ 其中 $q$ 表示询问个数。

如何改进莫队的算法复杂度？

我们发现，每一次移动指针的时间复杂度很少，只有 $O(1)$，算法的时间复杂度主要消耗在挪动的次数上，那有什么办法使得移动次数减少呢？显然，通过简单思考发现，询问的顺序大大影响了算法的复杂度，那么我们可以将询问一个一个存储下来然后排序，离线算出答案，按照答案原先的顺序输出就好了。

现在我们把主要的难点放在了排序上。

那么如何排序呢？

首先最简单的办法就是按照左端点升序排列，这样可以保证左端点只向右挪，但右端点可能从 $1$ 移到 $n$ 所以复杂度还是 $O(nq)$.

在重声一遍，我们要使左右端点移动的次数和最少。

那么我们可以使用分块的思想，将这个数列分成 $\sqrt{n}$ 个块，每个块的长度为 $\sqrt{n}$ ，将左端点是否在同一个块为第一关键字，按右端点的大小作为第二关键字进行排序，那么复杂度就是 $O(n\sqrt{n})$ 的，证明笔者不会wtcl。

但对于某些毒瘤恶心的出题人，$O(n\sqrt{n})$ 的时间还是不够的，我们需要更多的卡常优化，过掉这道题。

优化一：调整块长

调整块长是一种技巧
——by Mini

如果假设块长为 $L$ 那么对于很多个在同一块内的询问，挪动的距离最多就是 $n$，那么，有 $\frac{n}{L}$ 个块，那么最多会有 $\frac{n^2}{L}$ 次挪动，但是移动可能会跨越到另一个块上，所以还需加上 $q\times L$ 的时间复杂度，则整理后复杂度则为 $\mathcal{O}(\frac{n^2}{L}+qL)$ ，那么这个 $L$ 的长度可以任题意取值，下面的内容是我的习惯，不喜勿喷。

我认为长度最好为 $\frac{n}{\sqrt{m}}$ 则套用后复杂度为 $\mathcal{O}(n\sqrt{m})$，在 $n$ 与 $m$ 同阶的话没什么用。

不过如果块长为 $\frac{n}{\sqrt{m\times \frac{2}{3}}}$ 似乎会好一些，酌情使用吧~~

优化二：快读

给一个非常 nice 的快读模板，运用了位运算：

inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}

几道例题：

1. P1972 [SDOI2009]HH的项链

2. P2709 小B的询问

和lxl出的大多数题，感谢观看

小B的询问 题解

一道很经典的莫队题。

用 $cn{t}_i$ 表示数 $i$ 出现的次数，用上述方法使用莫队，则核心代码为：

add:

inline void add(int x) {
cnt[a[x]] ++;
ans += 2 * cnt[a[x]] - 1;
}

del:

inline void del(int x) {
cnt[a[x]] --;
ans -= 2 * cnt[a[x]] + 1;
}

主函数就很简单了，大家把他切掉吧~

最后

以上就是踏实烧鹅为你收集整理的普通莫队学习笔记什么是莫队&莫队的基本思路如何改进莫队的算法复杂度？几道例题：的全部内容，希望文章能够帮你解决普通莫队学习笔记什么是莫队&莫队的基本思路如何改进莫队的算法复杂度？几道例题：所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。