莫队算法笔记
莫队算法——由莫涛提出的区间操作离线暴力算法，可用以解决离线区间询问问题。
以下章节由例题起头，展示莫队算法可应用的基本场景，然后分析例题并逐步优化，最后得到莫队算法模板，并尝试进行复杂度分析。
本笔记分析思路由相关博客以及视频内容整理而成，开头提供原文和原视频的链接。
资料来源
OI-wiki：https://oi-wiki.org/misc/mo-algo/
离线算法&在线算法
- 离线算法：一开始就需要提供全部输入。
- 在线算法：可以以串行方式输入，无需一开始知道所有输入。
例题
洛谷 SP3267 DQUERY - D-query
题目概述
一个长度为n的数列，a1,a2,…,an，有q个询问，每个询问给出数对(i,j) ，给出ai,ai+1…,aj
这一段中有多少不同的数字。
输入格式
第一行：n(1 ≤ n ≤ 30000)。
第二行：数列的元素，a 1 , a 2, …, an(1 ≤ a i ≤ 10 6)。
第三行：q(1 ≤ q ≤ 200000)，查询的个数。
第四行：接下来有q行，每行包含两个数字对应 i, j ，此为查询的区间(1 ≤ i ≤ j ≤ n)。
输出格式
对于每一个查询区间(i, j)，输出子序列a中不同元素的数量，每个答案单独一行。
输入输出样例
1
2
3
4
5
6
7
| // 输入 #1
5
1 1 2 1 3
3
1 5
2 4
3 5
|
例题分析
暴力枚举
最简单的想法是暴力枚举，创建一个cnt数组以下标表示an的值，数值等于l到r区间的各元素出现次数，即cntnum，设数列中最大的元素为s，每次查询区间跨度都是n。
那么过程耗时最长就是查询q次，每次扫描一遍数列并计数，最后扫描一遍cnt数组看看出现次数不为0的元素个数，时间复杂度为O(q(n + s))，很可能不能通过一些测试用例。
暴力法优化（双指针跳跃）
优化1：每枚举一个数值num，增加出现次数时cntnum判断cntnum是否为0，如果为0，则代表从未出现过直接+1；反之区间内删除num后也判断cntnum是否为0，如果为0则减去1。
优化2：大体思路是建立l、r两个指针，每次询问移动l、r指针使其与询问区间重合，统计时也只在指针处加减cnt。
图为上述例题输入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，故保持移动时先扩大区间再缩小的原则。
初始化完成后，从l是否大于目标区间左端点开始判断，若是的话则需移动l指针直至与目标区间左端点重合，并作相应计数更新。但我们该次查询为[1, 5]，l指针已处于左端点位置，故暂不做操作。
第二步判断r指针是否小于目标区间右端点，是则移动直至重合并更新计数。当前r为0，目标右端点为5，需移动r。++r后此时r = 1，看cnt [1]是否等于0，此时显然等于0，则做出对应添加或删除操作，因为在维护r指针右移，为添加操作，sum ++。这样就获取到了区间[1, 1]不同元素的个数为1。最后cnt数组中对应数字位置自增，即cnt[1]++。
继续移动r指针，++r，此时在判断cnt[num] == 0时发现不符合条件，
