[链接登录后可见]
0x10 莫队算法的概念
莫队算法是由莫涛提出的算法。莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。 ——摘自 $Oi-wiki$。
0x20 普通莫队算法
0x21 形式
给定一个序列 $Q$ ，我们设 $n$ 和 $m$ 同阶。对于序列上的查询问题，给定查询区间 $[L_ i,R_ i]$，我们可以以 $O(1)$ 的速度扩展答案到与查询区间相邻的四个区间，即：$[L_ {i-1}, R]$， $[L_ {i+1}, R]$ ，$[L_ i, R_ {i+1}]$ 和 $[L_ i,R_ {i-1}]$。 这样，我们实现的时间复杂度就是 $O(n×$块长$）$。而我们通常设的块长为 $\sqrt{n}$ ，那么我们的时间复杂度就是 $O(n\sqrt{n})$，这对于我们 $n$ 达到 $10^ 5$ 时，是一个非常快速的做法，且代码实现较易。
代码模板如下：
for (int i = 1; i <= m; i ++) {
while (r < mt[i].r) add (++ r);
while (l > mt[i].l) add (-- l);
while (l < mt[i].l) del (l ++);
while (r > mt[i].r) del (r --);
ans[mt[i].id] = res;
}
0x22 实现
对于 $m$ 个询问，我们将其先存储起来，然后再排序，最后离线处理这些数据。
0x23 排序
正常来说，我们的排序方法都是以 $[L_ i, R_ i]$ 所在的块的编号为第一关键字，以右端点为第二关键字从小到大排序。
代码实现如下：
inline bool cmp (MOTEAM x, MOTEAM y) {
if (block[x.l] == block[y.l]) {
//x和y的左端点都在同一个块中时，按右端点进行排序。
return x.r < y.r;
}
if (block[x.l] != block[y.l]) {
//x和y的左端点不在同一个块中时，按左端点进行排序。
return x.l < y.l;
}
}
0x24 优化
在很多时候，我们会盲目的将块长设置为 $\sqrt{n}$，所以如果遇到 $m$ 和 $\sqrt{n}$ 同阶时，而恰好我们将块长设置为 $\sqrt{n}$ 时，这样我们就有可能被构造出的数据卡掉。
那我们应该将块长设为什么呢？在随机数据下，设为 $\frac{n}{\sqrt{\frac{2}{3} m}}$ 会快一些，大概能优化 $\frac{1}{10}$ 左右。证明留给读者自行探索。
我们发现，莫队算法实际上看上去仅仅是暴力的优化。但是为什么使用这种"看似暴力"的做法却可以通过高难度数据结构题目呢？很显然，我们的算法复杂度在离线进行排序的时候被优化了。所以，这一排序节省了我们很多的时间。
于是又有神仙创造出了一种新的排序方法：奇偶性排序。
首先，我们原来的排序方法，虽然让右端点的大跳动减少了很多。但是，右端点的跳动依旧存在，使我们的时间复杂度大幅度升高。我们能否创造一种方法排序使其更优化呢？
我们在选择奇数块时，按照右端点从小到大排序，在偶数块时从大到小排序，这样可以减少右端点进行大跳动的次数。
而为什么这样排序会快呢？是因为右指针移动到右边后就不需要跳回左边了，而跳回左边后处理下一个块是要跳动到右边的。很明显，这样就会优化近一半的时间复杂度。
代码实现如下：
inline bool cmp (MOTEAM x, MOTEAM y) {
return block[x.l] == block[y.l] ? (block[y.l] & 1) ? x.r < y.r : x.r > y.r : x.l < y.l
}
0x30 普通莫队算法例题
0x31 例题 $1$
[链接登录后可见]
很经典的一道题。这道题求 $[L_ i,R_ i]$ 区间只出现过一次的数字个数。这样我们的 $add$ 和 $del$ 函数就很好设计。
inline void add (int x) {
cnt[a[x]] ++;
if (cnt[a[x]] == 1) {
res ++;
}
}
inline void del (int x) {
cnt[a[x]] --;
if (cnt[a[x]] == 0) {
res --;
}
}
但是这道题的出题人也许特意卡莫队做法，正常写法应该是 $65pts$ ，会 $TLE$ $5$个点。
所以我们需要大力卡常！我们运用上面的优化技巧，修改块长，使用奇偶性排序方法，将 $add$ 和 $del$ 改成位运算，提前预处理左端点所在块，吸口氧就可以通过该题了。
[链接登录后可见]
0x32 例题 $2$
[链接登录后可见]
这道题和上道题几乎相同，我们只需要用正常的莫队做法就可以通过。
核心代码如下：
inline void add(int x, int &res) {
if (num[a[x]] == 0) {
//次数未增加前该数次数出现次数为0，就没有出现过，即不重复。
res ++;
}
num[a[x]] ++;
}
inline void del(int x, int &res) {
num[a[x]] --;
if (num[a[x]] == 0) {
//次数减少后该数次数出现次数为0，就出现过，个数减少。
res --;
}
}
0x33 例题 $3$
[链接登录后可见]
我们看到题目，每个数字贡献为出现次数的平方，这样我们的 $add$ 和 $del$ 函数就不太好编写。
这样我们就需要用到完全平方的小知识解决此题。
即：
$(a+1)^ 2 = a^ 2+1+2a$
于是我们的 $add$ 函数和 $del$ 函数有这种写法：
inline void add (int x) {
ans += cnt[a[x]] * 2 + 1;
cnt[a[x]] ++;
}
inline void del (int x) {
ans -= cnt[a[x]] * 2 - 1;
cnt[a[x]] --;
}
但是不要忘记，莫队是暴力美学，当然我们的 $add$ 函数和 $del$ 函数也可以暴力模拟。
核心代码如下：
inline void add (int x) {
memo -= cnt[a[x]] * cnt[a[x]];
cnt[a[x]] ++;
memo += cnt[a[x]] * cnt[a[x]];
}
inline void del (int x) {
memo -= cnt[a[x]] * cnt[a[x]];
cnt[a[x]] --;
memo += cnt[a[x]] * cnt[a[x]];
}
0x34 例题 $4$
[链接登录后可见]
$0x33$ 的双倍经验，直接计算答案贡献即可。
0x35 例题 $5$
[链接登录后可见]
模板题要做吐了qwq。
同样是统计区间内出现次数为 $1$ 的数字个数，最后判断出现次数为 $1$ 的数字个数是否为该区间所有数字个数就可以了。
核心代码如下：
for (int i = 1; i <= q; i ++) {
while (l < mt[i].l) del (l ++);
while (r < mt[i].r) add (++ r);
while (l > mt[i].l) add (-- l);
while (r > mt[i].r) del (r --);
if (res == mt[i].r - mt[i].l + 1) {
ans[mt[i].id] = 1;
}
}
0x36 例题 $6$
[链接登录后可见]
需要稍微了解异或的性质，其实还是一道普通莫队模板题。
题目要求求异或为 $k$ 的子区间个数，我们可以先做一个前缀异或和，运用前缀和的性质，我们求的答案就是 $R-(L-1)$的答案，为了方便我们可以存储左端点的时候就将其减一。
我们进行 $add$ 和 $del$ 函数的时候操作的是异或 $k$ 后的答案，这样查询的答案也是异或 $k$ 后的，就得到了题目要求的答案。
核心代码如下：
inline void add (int x) {
res += num[(a[x]^ k)];
num[a[x]] ++;
}
inline void del (int x) {
num[a[x]] --;
res -= num[(a[x]^ k)];
}
0x37 例题 $7$
[链接登录后可见]
这是上道题的双倍经验，依旧是存储答案异或 $k$ 后的数字，查询次数也需要查询异或 $k$ 的次数，就可以了。
0x38 例题 $8$
[链接登录后可见]
普通莫队操作。$add$ 和 $del$ 时判断次数是否与元素相同即可。
核心代码如下：
inline void add (int x) {
if (num[a[x]] == a[x]) {
res --;
}
num[a[x]] ++;
if (num[a[x]] == a[x]) {
res ++;
}
}
inline void del (int x) {
if (num[a[x]] == a[x]) {
res --;
}
num[a[x]] --;
if (num[a[x]] == a[x]) {
res ++;
}
}
0x40 带修莫队
