最近整理并学习了一些根号算法，总共分为三个。

$1.$ 莫队

$2.$ 分块

$3.$ 根号分治

$1.$ 莫队

$1_.$ 序列莫队

这是一个离线算法（当然有在线的，但是 CCF 不会卡吧）。

它可以在 $q\sqrt{n}+n\sqrt{n}$ 的时间内解决数列上多组询问的问题，问题大多给一个区间 $l$ $r$，让你输出 $[l,r]$ 的某个信息，比如区间和。

莫队的思想就是维护一个当前拥有信息的指针 $L$ $R$，通过不断地移动 $L$ $R$ 的位置添加或删除数字来得到 $l$ $r$ 的答案。

假如要求 $[2,5]$ 的区间和，现在手头上有 $[3,4]$ 的区间和，加上 $a[2]$ 和 $a[5]$ 的值就可以了。

现在归纳一下，假如有的信息是 $[L,R]$，要求 $[l,r]$，就可以通过 $|L-l| + |R-r|$ 次移动得到答案了。

所以我们要把所有的询问排一下序，使得 $\sum\limits_{i=2}^n |a[i].l - a[i - 1].l|+|a[i].r - a[i -1].r|$ 最小，这个有人证明过最小是值域乘以 $\log$ 值域的，但怎么排列是一个 NP Hard，莫队算法的优势就是简洁好写，如果和 NP hard 弄在一起...

所以现在要做的就是找到一种容易求得的排列方式，代价又小。

如果仅仅按照右端点来排序，左端点一次在很前面，一次在很后面的交替，就卡死了。

如果按照左端点排序，右端点也可以移来移去还是不行。

我们需要找到一种兼顾左端点和右端点的排序方法，如果按照左端点所在的块排序，块相同的按照右端点排序就会很快。

设块长为 $b$，右端点在每个块内都会移动 $n$ 次，一共 $\frac{n}{b}$ 个块，所以 $\frac{n^2}{b}$。

左端点在每个块内每次都会移动 $b$，跨越块的移动 $b$ 次，每次 $\frac{n}{b}$，所以需要 $nb+n$

现在找到 $b$ 使得这两个加起来最小，显然 $b=\sqrt{n}$，这就是莫队算法。

$0xFF$ 浅谈在线莫队

在线莫队的思想其实很简单，先预处理出一些区间的答案，询问时找到离询问参数 $l$ $r$ 最近的预处理过的 $L$ $R$ 然后转移过去。

怎样预处理呢？我们每隔 $\sqrt{n}$ 个数就留下一个特征点，这样就有 $\sqrt{n}$ 个特征点，每两个特征点搭配组成特征区间，所以大约有 $\frac{n}{2}$ 个特征区间。

每次询问给定参数 $l$ $r$，对于部分莫队题目，加操作（即 l 向左，r 向右）能做，减操作无法处理，就要找到被 $l$ $r$ 包含的最大的特征区间，这样在线莫队代替回滚莫队？！！

对于加操作减操作都能处理的，那就找最近的特征区间啦！

莫队核心代码:：

while (r < a[i].r) add (++ r);
while (l > a[i].l) add (-- l);
while (r > a[i].r) rem (r --);
while (l < a[i].l) rem (l ++);

$0xFE$ 莫队总结

讲完这个，我们就来看几道例题。

能用莫队解决的题目，大概具有什么特点呢？

询问可支持离线（在线莫队不管），数据范围不卡 $n\sqrt{n}$（废话），没有修改操作（只是对于简单的莫队而言）

可以以较低的复杂度移动左右指针（为什么是较低，因为后面有一道题 $\log n$ 移动然后卡过了）。

$0x00$ 例题

P2709 小 B 的询问

当然不像我们说的那么简单，维护区间和，这题要维护一个桶。

加入一个数 $x$ 之前其出现次数为 $b[x]$，那么加完后区间的答案 $ans$ 就变成 $ans - b[x]^2+(b[x] + 1)^2$。

当然可以化简成 $ans+2\times b[x]+1$，减去一个数同理啦，略。

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, k;
int l, r, sum = 1, block;
int c[50010], ans[50010], cnt[50010];
struct Sec{int l, r, id;}a[50010];
void add (int x)
{
    sum += 2 * cnt[c[x]] + 1;
    cnt[c[x]] ++;
}
void rem (int x)
{
    sum -= 2 * cnt[c[x]] - 1;
    cnt[c[x]] --;
}
bool cmp (Sec s1, Sec s2){return s1.l / block < s2.l / block || s1.l / block == s2.l / block && s1.r < s2.r;}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    block = sqrt(n);
    for (int i = 1; i <= n; i ++) scanf("%d", &c[i]);
    for (int i = 1; i <= m; i ++)
    {
        scanf("%d%d", &a[i].l, &a[i].r);
        a[i].id = i;
    }
    sort (a + 1, a + m + 1, cmp);
    l = r = a[1].l;
    cnt[c[l]] ++;
    for (int i = 1; i <= m; i ++)
    {
        while (r < a[i].r) add (++ r);
        while (l > a[i].l) add (-- l);
        while (r > a[i].r) rem (r --);
        while (l < a[i].l) rem (l ++);
        ans[a[i].id] = sum;
    }
    for (int i = 1; i <= m; i ++) cout << ans[i] << "\n";
    return 0;
}

P4462 异或序列

属于是半思维半莫队啦！

首先你需要知道异或具有自反性，即 $a\oplus a=0$。

令 $o_i=a_1\oplus a_2\cdots \oplus a_i$，那么 $a_x\oplus a_{x+1}\cdots \oplus a_y$ 就等于 $o_y \oplus o_{x-1}$。

询问有多少子区间异或和为 $k$ 其实就相当于询问有多少个点 $x$ $y$，其中 $l-1 \leq x\leq r-1$，$l\leq y\leq r$，使得 $o_x \oplus o_y = k$。

$k$ 是已知的，假如我们要假如第 $R$ 个位置，那就需要统计在合法的范围内，$o_L \oplus o_R = k$，$L$ 的数量喽，可以先算出 $o_L$ 的值 $=k\oplus o_R$。

那么我们用一个桶维护，$b[x]$ 维护的就是 $o_L=x$ 的数量，减也同理就不说了。（注意这里我没有加减函数都写，而是用一个参数使一个函数替代这两个的作用了，码风更加清新）

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, k;
int l = 1, r, res;
int a[100005], b[100005], ans[100005];
struct Node {int l, r, id;}q[100005];
bool cmp (Node n1, Node n2) {return n1.l / 300 < n2.l / 300 || n1.l / 300 == n2.l / 300 && n1.r < n2.r;}
void fun (int x, int s) {
    res += s * b[x ^ k];
    b[x] += s;
}
int main () {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        a[i] ^= a[i - 1];
    }
    for (int i = 1; i <= m; i ++) {
        cin >> q[i].l >> q[i].r;
        -- q[i].l;
        q[i].id = i;
    }
    sort (q + 1, q + m + 1, cmp);
    for (int i = 1; i <= m; i ++) {
        while (r < q[i].r) fun (a[++ r], 1);
        while (l > q[i].l) fun (a[-- l], 1);
        while (l < q[i].l) fun (a[l ++], -1);
        while (r > q[i].r) fun (a[r --], -1);
        ans[q[i].id] = res;
    }
    for (int i = 1; i <= m; i ++) cout << ans[i] << "\n";
    return 0;
}