众所周知，莫队是由莫涛大神提出的，一种玄学毒瘤暴力骗分区间操作算法，它以简短的框架、简单易记的板子和优秀的复杂度闻名于世。然而由于莫队算法应用的毒瘤，很多可做的莫队模板题都有着较高的难度评级，令很多初学者望而却步。然而，如果你真正理解了莫队的算法原理，那么它用起来还是很简单的。当然某些套左套右的毒瘤除外
0、前置芝士：
莫队算法还是比较独立的。不过你还是得了解了解以下的一些知识：
\(1\)、分块的基本思想（开根号等）
\(2\)、STL中sort的用法（手写cmp函数或重载运算符实现结构体的多关键字排序）
\(3\)、基(du)础(liu)的卡常技巧（包含#pragma GCC optimize系列）
\(4*\)、倍增/树剖 求LCA（树上莫队所需）
\(5*\)、数值离散化（用于应付很多题目）
至此全部完毕。撒花~~（雾
诶，别走啊qwq，我可不是在劝退qwq，如果你认为自己不懂这些东西也没关系，往下看吧qwq
1、莫队算法是个啥
来历：
前面已经介绍过了（逃
有兴趣的同学可以看一下莫涛大神的知乎
然而这个算法到底是用来搞什么操作的呢？我们先看个例题：
Luogu P1972 [SDOI2009]HH的项链
题目描述
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。
输入输出格式
输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：
M 行，每行一个整数，依次表示询问对应的答案。
输入输出样例
输入样例#1：
6
1 2 3 4 3 5
3
1 2
3 5
2 6输出样例#1：
2
2
4说明
数据范围：
对于100%的数据，N <= 500000，M <= 500000。
题意简明易懂：给你一个长度不大于\(n≤5×10^5\)的序列，其中数值都小于等于\(10^6\)，有\(m≤5×10^5\)次询问，每次询问区间\([l,r]\)中数值个数（也就是去重后数字的个数）。
不过这个例题卡了莫队，所以请左转数据弱化版：SP3267 DQUERY - D-query
题目到手，我们开始分析本题的算法。这题最简单做法无非暴力——用一个\(cnt\)数组记录每个数值出现的次数，再暴力枚举\(l\)到\(r\)统计次数，最后再扫一遍cnt数组，统计\(cnt\)不为零的数值个数，输出答案即可。设最大数值为\(s\)，那么这样做的复杂度为\(O(m(n+s))∽O(n^2)\)，对于本题实在跑不起。
我们可以尝试优化一下：
优化1：每次枚举到一个数值\(num\)，增加出现次数时判断一下\(cnt_{num}\)是否为0，如果为0，则这个数值之前没有出现过，现在出现了，数值数当然要+1。反之在从区间中删除\(num\)后也判断一下\(cnt_{num}\)是否为0，如果为0数值总数-1。这样我们优化掉了一个\(O(ms)\)，但还是跑不起。
优化2：我们弄两个指针 \(l\) 、\(r\) ，每次询问不直接枚举，而是移动 \(l\) 、\(r\) 指针到询问的区间，直到\([l,r]\)与询问区间重合。在统计答案时，我们也只在两个指针处加减\(cnt\)，然后我们就可以用优化1中的方法快速地统计答案啦\(qwq\)！
优化2具体步骤如下：
假设这个序列是这样子的：（其中\(Q1\)、\(Q2\)是询问区间）
我们初始化\(l=1\)、\(r=0\)（如果\(l=0\)，那么我们还需要删除一个数值\(0\)，使其出现次数变成-1，导致一些奇奇怪怪错误），如下图（由于画图软件中\(l\)和\(1\)看不出区别，我只好在图中使用\(L\)和\(R\)来表示qwq）：
我们发现 \(l\) 已经是第一个查询区间的左端点，无需移动。现在我们将 \(r\) 右移一位，发现新数值1：
\(r\) 继续右移，发现新数值2：
继续右移，发现新数值4：
当 \(r\) 再次右移时，发现此时的新位置中的数值2出现过，数值总数不增：
接下来是两个7，由于7没出现过，所以总数+1：
继续右移发现3：
继续右移，但接下来的两个数值都出现过，总数不增。
至此，\(Q1\)区间所有数值统计完成，结果为5。
现在我们又看一下\(Q2\)区间的情况：
首先我们发现， \(l\) 指针在\(Q2\)区间左端点的左边，我们需要将它右移，同时删除原位置的统计信息。
将\(l\)右移一位到位置2，删除位置1处的数值1。但由于操作后的区间中仍然有数值1存在，所以总数不减。
接下来的两位也是如此，直接删掉即可，总数不减。
当 \(l\) 指针继续右移时，发现一个问题：原位置上的数值是2，但是删除这个2后，此时的区间\([l,r]\)中再也没有2了（回顾之前的内容，这种情况就是删除后\(cnt_2 = 0\)），那么总数就要-1，因为有一个数值已经不在该区间内出现了，而本题需要统计的就是区间内的数值个数。此步骤如下图：
再右移一位，发现无需减总数，而且\(l\)已经移到了\(Q2\)区间的左端点，无需继续移下去（如下图）。当然 \(r\) 还是要移动的，只不过没图了，我相信大家应该知道做法的\(qwq\)。
\(r\)的最后位置：
至于删除操作，也是一样的做法，只不过要先删除当前位置的数值，才能移动指针。
有了以上的内容，这段代码就可以很容易写出啦qwq：
int aa[maxn], cnt[maxn], l = 1, r = 0, now = 0; //每个位置的数值、每个数值的计数器、左指针、右指针、当前统计结果（总数）
void add(int pos) {//添加一个数if(!cnt[aa[pos]]) ++now;//在区间中新出现，总数要+1++cnt[aa[pos]];
}
void del(int pos) {//删除一个数--cnt[aa[pos
