莫队是永远也卡不住的。
—————— 许多dalao
很久以前 老师讲了莫队，目的是让我们理解分块思想，当时没时间做笔记（其实是懒的），现在来补上OVO。
使用范围（纯属个人理解）
区间求元素种类个数，每种种类元素个数……
一些看似线段树能做的题但实际上不满足加和性质的题。
大部分树状数组能做的题。
（如果有错误请大佬轻点打（doge））
大概需要的东西
分块（我不会）
结构体排序（这个应该是得心应手了）
疯狂卡常小技巧（不一定需要）
一个清明的脑子和一双别老手残的手（这个很重要）
思路过程
先分块，再排序，最后四个 while 结束一切。
放个例题（老师的例题）
题意概括
有一个长度为 (n) 的序列，里面的元素为 (c_i) ，有 (m) 组询问，每次询问给出 (l) 和 (r)，
求如果在 ([l,r]) 里任意选两个数字选到相同数字的概率是多少，
输出答案以分数形式存在。
数据范围：(n,min[1,50000])，(c_i,l,rin[1,n]) 。
分析
很明显，这道题符合之前我说的莫队适用情况。
这时候，就是莫队发威的时候了！！（雾）
注意：以下过程可能会让人不明不白的，但我会在后面细讲的。
First
以每个块为 (sqrt n) 的大小分成 (sqrt n) 个块 。
Second
以每个查询区间的左端点所在块顺序排序，
如果左端点所在块相同，就按照右端点所在块的序数奇偶性排序：
若右端点在奇数块，顺序排序；
若右端点在偶数块，倒叙排序。
Third
开始遍历所有查询区间，设 (l) 和 (r) 两个指针作为遍历到的区间，
初始 (l = 1)，(r = 0) 代表现在所在区间不存在，
然后从排好序的查询区间作为询问区间 (ql) 和 (qr)，
如果 (l < ql)，就让 (l) 向右移动直到与 (ql) 重合；
如果 (l > ql)，就让 (l) 向左移动直到与 (ql) 重合；
如果 (r < qr)，就让 (r) 向右移动直到与 (qr) 重合；
如果 (r > qr)，就让 (r) 向左移动直到与 (qr) 重合，
同时让记录 (l) 到 (r) 之间所有种类元素的个数的数组 (cnt) 随遍历到的数字来加减计数。
Last
最后求出概率的分母与分子，约分后全部输出。
解释
Third
先说第三步，便于下面的解释。
一开始，还没有遍历的时候，(l) 和 (r) 是初始化的，大概是这样：
请不要在意奇怪的数字
很明显，此时 (l) 和 (r) 之间没有任何元素 。
我们假定 (ql = 2)，(qr = 6)，
而此时 (l) 小于 (ql)，所以 (l) 向右移动直到与 (ql) 重合 。
现在是这样的：
关于更新 (cnt) 数组
每次扫到一个数字（无论是 (l) 还是 (r)），
如果之前扫到过，就说明 (cnt) 数组已经记录下来了这个元素，而现在再扫到说明要将这个元素从 (l) 到 (r) 这个区间中删去，这时候 (cnt--)；
如果之前没有扫到过，就说明 (cnt) 数组没有记录下来，而现在扫到说明要将这个元素从 (l) 到 (r) 这个区间中加上，这时候 (cnt++) 。
现在继续模拟：
既然 (l) 和 (ql) 已经重合了，那么现在需要更新的是 (r) 的位置，于是 (r) 开始向 (qr) 靠拢直到重合：
于是现在 (cnt) 数组里存的是 (ql) 到 (qr) 的统计值，剩下的只需要在统计的时候按照求概率的公式来就行了，记得用 (ans) 数组记录下当前值，
毕竟查询下一个区间是在当前区间的基础下完成的。
First
分块不必多说，如果不懂就看看 这个
分块的作用大概就是让上面说的两个指针 (l) 和 (r) 每次不会移动太大的距离：
(r) 从头到尾一直是从左到右的，而 (l) 则是在一个块里来回移动咣当。
Second
莫队的奇偶性排序简直是最玄学的，经老师的一番解释，我大约明白了是怎么回事。
但我说不出来……
不过这不重要，最重要的是知道要这么做就好啦（护头，大佬轻点打/doge）
Last
个人 jiao 得，这个才是最难得（确信脸），如果不会请看大佬们的题解（这个不属于莫队里的）
最后
如果看到这里还不懂的话，就看看这篇吧，
反正我是看这篇才会的（老师讲课永远 emmmm 懂得）
膜拜大佬 %%%