莫队算法笔记

莫队算法——由莫涛提出的区间操作离线暴力算法，可用以解决离线区间询问问题。

以下章节由例题起头，展示莫队算法可应用的基本场景，然后分析例题并逐步优化，最后得到莫队算法模板，并尝试进行复杂度分析。

本笔记分析思路由相关博客以及视频内容整理而成，开头提供原文和原视频的链接。

资料来源

OI-wiki：https://oi-wiki.org/misc/mo-algo/

离线算法&在线算法

• 离线算法：一开始就需要提供全部输入。
• 在线算法：可以以串行方式输入，无需一开始知道所有输入。

例题

洛谷 SP3267 DQUERY - D-query

题目概述

一个长度为n的数列，a₁,a₂,…,a_n，有q个询问，每个询问给出数对(i,j) ，给出a_i,a_i+1…,a_j

这一段中有多少不同的数字。

输入格式

第一行：n(1 ≤ n ≤ 30000)。

第二行：数列的元素，a ₁ , a ₂, …, a_n(1 ≤ a _i ≤ 10 ⁶)。

第三行：q(1 ≤ q ≤ 200000)，查询的个数。

第四行：接下来有q行，每行包含两个数字对应 i, j ，此为查询的区间(1 ≤ i ≤ j ≤ n)。

输出格式

对于每一个查询区间(i, j)，输出子序列a中不同元素的数量，每个答案单独一行。

输入输出样例

// 输入 #1
5
1 1 2 1 3
3
1 5
2 4
3 5

// 输出 #1
3
2
3

例题分析

暴力枚举

最简单的想法是暴力枚举，创建一个cnt数组以下标表示a_n的值，数值等于l到r区间的各元素出现次数，即cnt_num，设数列中最大的元素为s，每次查询区间跨度都是n。

那么过程耗时最长就是查询q次，每次扫描一遍数列并计数，最后扫描一遍cnt数组看看出现次数不为0的元素个数，时间复杂度为O(q(n + s))，很可能不能通过一些测试用例。

暴力法优化（双指针跳跃）

优化1：每枚举一个数值num，增加出现次数时cnt_num判断cnt_num是否为0，如果为0，则代表从未出现过直接+1；反之区间内删除num后也判断cnt_num是否为0，如果为0则减去1。

优化2：大体思路是建立l、r两个指针，每次询问移动l、r指针使其与询问区间重合，统计时也只在指针处加减cnt。

图为上述例题输入1的示例，第一行是数组下标，第二行是具体数值。

1. 第一个查询区间为[1, 5]，将初始化区间设为[1, 0]，区间内不同元素的数量设为sum，建立下标位置为某元素i数值的cnt[]数组用以表示当前区间该元素出现次数。

   P.S. 区间移动过程相当于加入了[1, r]的元素，并删除了[1, l - 1]的元素。

   • 当l <= r，[1, l - 1]的元素相当于被加入一次后删除一次，[l, r]内元素相当于被加入一次，[r + 1， +∞]的元素没有被加入，是合法区间。
   • 当l = r + 1，[1, r]的元素相当于被加入一次后删除一次，[r + 1， +∞]的元素没有被加入。此时区间为空区间。
   • 当l > r + 1，[r + 1, l - 1]（该区间非空）的元素被删除了一次但未被加入，被加入次数为负数。非法区间。

   那么由此可知初始化区间为什么设为[1, 0]，因为设[1, 0]的话刚好相当于[1, 0]的元素被加入一次并删除一次（无额外添加），同时[1， +∞]的元素未被添加过。

   且可看出在区间移动过程中要保持l <= r + 1，故保持移动时先扩大区间再缩小的原则。

2. 初始化完成后，从l是否大于目标区间左端点开始判断，若是的话则需移动l指针直至与目标区间左端点重合，并作相应计数更新。但我们该次查询为[1, 5]，l指针已处于左端点位置，故暂不做操作。

3. 第二步判断r指针是否小于目标区间右端点，是则移动直至重合并更新计数。当前r为0，目标右端点为5，需移动r。++r后此时r = 1，看cnt [1]是否等于0，此时显然等于0，则做出对应添加或删除操作，因为在维护r指针右移，为添加操作，sum ++。这样就获取到了区间[1, 1]不同元素的个数为1。最后cnt数组中对应数字位置自增，即cnt[1]++。

4. 继续移动r指针，++r，此时在判断cnt[num] == 0时发现不符合条件，