普通莫队算法
什么是莫队算法
在给定一个含不同颜色的序列 \(c\)，求某些区间 \([L,R]\) 中颜色的数量时，一种常见的做法是将询问按照 \(R\) 为第一关键字进行排序，然后维护一个数组 \(a\) ， \(a[i]\) 表示第 \(i\) 个位置上的颜色 \(c[i]\) 是否是从序列头（左）到当前位置最右侧出现的位置，是的话则 \(a[i]=1\) ，否则 \(a[i]=0\) ，那么答案就是 \(sum[L,R]\) ，这可以用线段树或树状数组完成。
但是，当题目不仅仅需要求颜色的数量时，而是需要求区间内各种颜色各出现了多少次，这时上述方法就不再适用了。而莫队算法可以很好地解决这类问题。
莫队算法适用于在序列长度为 \(n\) 的 \(m\) 次区间询问时，已知区间 \([L,R]\) 的答案，并且能够 \(O(1)\)转移到 \([L-1,R]\),\([L+1,R]\),\([L,R-1]\),\([L,R+1]\) 的场合，那么就可以在询问离线分块排序的基础上，使用暴力转移的方法，在 \(n=m\) 时在 \(O(n\sqrt{n})\) 的时间复杂度内求出所有询问的答案。
像上述多次区间询问求不同颜色出现次数的问题场景，我们就可以将这些区间询问按照一定的规则进行排序后，先求出第一个区间询问的答案，然后通过一位一位地向相邻的区间转移，直到到达下一个区间并得出答案，以此类推求出所有区间询问的答案。为了减少需要进行的暴力转移的次数，我们需要借助分块的思想对询问进行排序。那么块的大小呢？在运用分块思想时，我们常常将长度为 \(n\) 序列分为长度为 \(\sqrt{n}\) 的 \(\sqrt{n}\) 块。而对于莫队算法，在 \(n=m\) 时，这样的分块方法依旧是适用的。关于 \(n\neq m\) 的情况，将在之后讨论。
另外，莫队算法是一个离线算法，它适用于一次性给出所有询问区间的场合，而不适用于强制在线的场合。
莫队算法的实现
具体而言分为以下几个步骤：
1.对序列进行分块(通常是长度为 \(\sqrt{n}\) 的 \(\sqrt{n}\) 块)；
2.将询问进行分块排序，即以 \(L\) 所在块为第一关键字， \(R\) 为第二关键字；
3.通过暴力删除或增加求出排序后第一个询问的答案，并通过暴力删除或增加转移到下一个询问区间，直到求出所有询问的答案；
4.将询问的答案按照原顺序输出。
struct query
{
int l, r, id;
bool operator <(const query& y)const//重载运算符用于排序
{
return tag[l] == tag[y.l] ? r < y.r : l < y.l;
}
}q[MAXN];
void solve()
{
int l = 1, r = 0;
for (int i = 1; i <= m; i++)
{
for (; l > q[i].l; l--) update();
for (; r < q[i].r; r++) update();
for (; l < q[i].l; l++) update();
for (; r > q[i].r; r--) update();//暴力转移更新答案
ans[q[i].id] = tmp;//记录答案回原询问顺序
}
}
int main()
{
int len = sqrt(n);//分块大小
for (int i = 1; i <= n; i++)//分块并计算第i个位置所在块的序号
{
tag[i] = (i - 1) / len + 1;
}
sort(q + 1, q + m + 1);//分块排序，tag[l]为第一关键字，r为第二关键字
solve();
return 0;
}
莫队算法的另一种理解
考虑将区间的 \(L\) 和 \(R\) 视为平面坐标系的两个坐标轴，那么所有的区间都可以被表示成为坐标系上的点，那么相邻区间的转移就可以理解为坐标系上一次曼哈顿距离为 \(1\) 的移动。 在这样的基础上，从一个点到另一个点需要的移动次数，就是两个点之间的曼哈顿距离。那么对于所有的查询，最佳答案就是对所有询问代表的点建立曼哈顿最小生成树。
但实际上我们不需要使用曼哈顿最小生成树这样复杂的算法，关于曼哈顿最小生成树的学习将在日后补充。对于莫队算法来说，就是做 \(n/len-1\) 条垂直于 \(x\) 的直线，将整个坐标系切分为 \(x\) 轴长度为 \(len\) 的 \(n/len\) 块。那么对于同一块内的点，我们按照 \(R\) 轴从小到大的顺序移动，在本块的点移动完毕后继续移动到下一块中 \(R\) 轴最小的点。
时间复杂度和一些特殊情况
先简单证明一下 \(n=m\) 时莫队算法的时间复杂度是 \(O(n\sqrt{n})\)。对于 \(R\) 而言，每块内 \(R\) 已按顺序排序好，因此每块内最多移动 \(n\) 次 \(R\) ，一共有 \(\sqrt{n}\) 个块，时间复杂度为 \(O(n\sqrt{n})\) 。对于 \(L\) 而言，每一次块内的移动都是 \(O(\sqrt{n})\) 级别的，最多有 \(n\)次 ，而不同块之间的移动是 \(O(n)\) 级别的，最多有 \(\sqrt{n}\) 次，因此， \(L\) 的总时间复杂度为 \(O(n\sqrt{n})\) 。因此，莫队算法总体的时间复杂度为 \(O(n\sqrt{n})\) 。
前面提到了，在 \(n\neq m\) ，如 \(m<n\) 时最优的分块大小可能会有所不同。先考虑 \(R\) ，我们设块长为 \(S\) ，那么共有 \(\frac{n}{S}\) 块，每块的移动距离为 \(O(n)\) 级别的，时间复杂度为 \(O(\frac{n^2}{S})\)。再考虑 \(L\) ,共有 \(m\) 次询问，每次移动的距离是 \(O(S)\) 级别的，时间复杂度为 \(O(mS)\) 。综合起来，算法总体的时间复杂度为 \(O(\frac{n^2}{S}+mS)\) 。
不难发现，当 \(S=\frac{n}{\sqrt{m}}\) 时，时间复杂度取得最小值，为 \(O(n\sqrt{m})\) 。即便如此，在大部分的情况下，\(\sqrt{n}\) 的分块大小都是适用的。
带修改的莫队算法
问题升级
在一些区间查询的莫队算法题目中，可能会在查询中引入修改操作。普通莫队算法显然不能很好地解决引入了修改操作的问题，因为如果我们要因为修改操作将所有询问切成若干块的话，分块思想的优势就将不复存在。因此需要一些方法使得莫队算法能够很好地处理引入修改操作的区间询问问题。
在普通的莫队算法中，我们提到过将不同的区间视为平面坐标系上不同的点，而新引入的修改操作有着严格的先后顺序，是否可以在坐标系中引入新的维度，来表示修改操作带来的、类似于“时间”一样的影响呢？
第三个坐标轴——时间
我们考虑将 \(l\) 和 \(r\) 都进行分块处理，而修改操作按照先后顺序形成了第三个坐标轴——时间。这样的感觉，是不是和普通莫队有些相似。区别是，普通莫队的分块是线性的，只有 \(l\) 被分成了一个一个小段;而带修莫队的分块是二维的，\(l\) 和 \(r\) 都被分块，共同形成了一个一个小矩形。这样，我们就可以按照普通莫队类似的方法来处理带修莫队了。需要注意的是时间轴上的移动和 \(l\) 和 \(r\) 轴上的移动有所不同。
当发生时间上的移动时，就直接暴力地应用时间改变造成的影响，包括：
1.如果当前莫队算法所在的询问区间包含被修改的点，那么应用被修改的点对答案造成的影响；
2.交换这次修改和原序列的内容，一是为了正确的处理后续在这个时间后的询问，而是为了方便后续时间退回时的还原。
带修改的莫队算法的实现
这里以 P1903 [国家集训队] 数颜色 / 维护队列 为例，这是一道经典的带修改的莫队问题。代码仅给出莫队算法相关部分。
void update1(int pos, int op)
{
ans -= cnt[a[pos]] > 0;
cnt[a[pos]] += op;
ans += cnt[a[pos]] > 0;
}
void update2(int pos, int cur)
{
if (p[pos].pos >= q[cur].l && p[pos].pos <= q[cur].r)
{
ans -= cnt[a[p[pos].pos]] > 0;
cnt[a[p[pos].pos]]--;
ans += cnt[a[p[pos].pos]] > 0;
ans -= cnt[p[pos].x] > 0;
cnt[p[pos].x]++;
ans += cnt[p[pos].x] > 0;
}
swap(a[p[pos].pos], p[pos].x);
}
void solve()
{
int l = 0, r = 0, t = 0;
for (int i = 1; i <= cntq; i++)
{
for (; l > q[i].l; l--)
update1(l - 1, 1);
for (; r < q[i].r; r++)
update1(r + 1, 1);
for (; r > q[i].r; r--)
update1(r, -1);
for (; l < q[i].l; l++)
update1(l, -1);
for (; t < q[i].t; t++)
update2(t + 1, i);
for (; t > q[i].t; t--)
update2(t, i);
q[i].ans = ans;
}
}
最优块长与时间复杂度
我们设序列长为 \(n\) ，询问长度为 \(m\) ，\(t\) 次修改 ，设块长为 \(s\) ，则有 \(\frac{n}{s}\) 块，此时时间复杂度为 \(ms+\frac{n^2t}{s^2}\) ，当 \(s=\sqrt[3]{\frac{2n^2t}{m}}\) 时，时间复杂度取得最小值。考虑 \(n,m,t\) 均为同数量级的情况，设为 \(O(n)\) ，那么最优块长取 \(n^{\frac{2}{3}}\) 时，时间复杂度为 \(n^{\frac{5}{3}}\)。在实际的场景中， \(n,m,t\) 很可能并不是同一数量级，但是考虑到 \(m,t\) 的实际数量级很可能是难以确定的， \(n^{\frac{2}{3}}\) 的分块大小依旧适用。
回滚莫队/不删除莫队
最大，次大，还有次次大
在一般的莫队算法中，我们通过删除和增加操作来实现不同区间的移动。然而在部分场景中，删除操作后难以实现答案的更新。考虑使用莫队算法解决以下两个场景：
1.求不同区间范围内，相同的数的最远间隔距离。
2.定义重要度为一个区间范围内，一个数的值乘以它的出现次数，求不同区间范围内，最高的重要度的值。
在第一个场景中，如果删除操作删除了一个当前区间贡献了最远间隔距离的位置（端点），那么删除后的区间由哪个数对贡献新的最远间隔距离呢？
在第二个场景中，如果删除了一个贡献了最大重要度的数，那么删除后的最大重要数依然是这个数呢，还是另有其数呢？
或许你能在这两个场景中维护次大答案的信息，那次大被删除时的次次大呢？最大和次大还有次次大的问题在莫队算法中难以维护，因此这类问题难以用常规莫队算法来解决，我们考虑引入回滚莫队/不删除莫队，通过避免维护次大甚至是次次大的信息，来减少删除操作给莫队算法带来的影响。
用回滚来避免删除
如果要避免删除操作，那么就只能使用增加操作来替代。假设现在有 \(3\) 个区间询问，那么怎样增加才能效率最高呢？答案是取这 \(3\) 个区间询问的重叠部分，记录重叠部分的左右端点 \(l,r\) ，然后分别向左和向右进行增加操作。然而这又带来的新的问题，如果左右指针 \(l,r\) 只是一味地增加，那么如果有两段区间不是完全的包含关系，就不可避免地要进行删除操作。事实上，这种做法就和普通莫队无异了，因此需要进一步改进。
考虑我们只在一边进行单调增长，另一边进行“选择性遗忘”。即我们在右区间进行移动时，右端点 \(r\) 也跟着移动，并记录下右区间的移动信息，直到遇到一个区间询问的右端点，此时我们建立临时的指针 \(p=l\) ，将 \(p\) 不断地向左移动，在这个过程中 \(l\) 保持不动，并用一个临时的数组来记录左区间的信息，直到遇到与右端点相对应的左端点，并计算带来的贡献。然后将左区间所有的内容“遗忘”掉，再接着在右区间移动。
至于为什么是记录右区间并遗忘左区间，想想我们分块的时候，左端点在同一块的询问，它们的右端点可能遍布整个序列，而左端点一定在一个块内，因此不断重复在左区间移动的代价较小。
回滚莫队的实现
这里以洛谷 P5906 【模板】回滚莫队&不删除莫队 为例。
void solve()
{
int temp1 = 0, temp2 = 0;
for (int i = 1, block = 0, l = 1, r = 0; i <= m; i++)
{
temp1 = 0;
if (tag[q[i].l] == tag[q[i].r])//在同一块时暴力
{
for (int j = q[i].l; j <= q[i].r; j++)
{
vis1[a[j]] = 0;
}
for (int j = q[i].l; j <= q[i].r; j++)
{
if (!vis1[a[j]])
vis1[a[j]] = j;
temp1 = max(temp1, j - vis1[a[j]]);
}
for (int j = q[i].l; j <= q[i].r; j++)
{
vis1[a[j]] = 0;
}
ans[q[i].id] = temp1;
continue;
}
if (tag[q[i].l] != block)//发生块的变化
{
for (int j = l; j <= r; j++)
{
vis1[a[j]] = vis2[a[j]] = 0;//新的块中，原右区间数据不可用
}
block = tag[q[i].l];
l = R[block];
r = l;//当前区间为[l,r-1]
temp2 = 0;
}
for (; r <= q[i].r; r++)//遍历右边
{
if (!vis1[a[r]])//在右区间最左出现的位置
vis1[a[r]] = r;
vis2[a[r]] = r;//在右区间最右出现的位置
temp2 = max(temp2, vis2[a[r]] - vis1[a[r]]);
}
for (int j = l - 1; j >= q[i].l; j--)//遍历左边
{
if (!vis3[a[j]])//在左区间最右出现的位置
vis3[a[j]] = j;
temp1 = max(temp1, vis2[a[j]] - j);
temp1 = max(temp1, vis3[a[j]] - j);//更新答案
}
for (int j = l - 1; j >= q[i].l; j--)
{
vis3[a[j]] = 0;//清空
}
ans[q[i].id] = max(temp1, temp2);
}
}
需要注意的是，为什么有两个记录答案的变量。我们知道，右区间的信息应该被正确地记录，并在左端点属于同一块的后续区间询问中使用。如果不使用一个独立的变量来记录右区间贡献的答案，而是在每次完成一个询问后清零，那么右区间中贡献的答案就无法给后续的区间询问使用。因此记录右区间贡献答案的变量应在区间询问左端点所属区间块发生变化时清零。
树上莫队
树与欧拉序
我们知道，树型结构显然不是一个线性的数据结构，那么要怎么样在树上用莫队算法呢？在讨论这个问题之前，我们要先讨论一下DFS序和欧拉序。
DFS序相信不少人都不陌生，在树上跑一遍DFS，遍历的先后顺序就是DFS序。如果默认先连的子节点在左的的话，那DFS序就是先序遍历。像下面这颗树，它的DFS序就是 \(1,2,4,7,8,5,3,6,9\) 。
那么欧拉序呢，它和DFS序有一些区别，它不仅要记录一个节点被遍历的时刻，还需要记录一个节点遍历结束的时刻。对于上面这颗树，它的欧拉序就是 \(1,2,4,7,7,8,8,4,5,5,2,3,6,9,9,6,3,1\) 。我们发现欧拉序中一个节点出现了两次，第二次出现就携带了一个节点结束遍历返回时的信息。
如果我们认为一个点在欧拉序中第一次访问是增加，第二次访问是删除，再观察欧拉序我们会发现一些有意思的现象。比如节点 \(1\) 到节点 \(9\) 的路径上的节点，就是欧拉序\(1,2,4,7,7,8,8,4,5,5,2,3,6,9\) 所表示的节点，也是上面的欧拉序的前 \(14\) 个元素，其中 \(2,3,7,8,5\) 都因为在欧拉序中出现了两次而被删除，只剩下 \(1,3,6,9\) 。而节点 \(7\) 到节点 \(5\) 没法直接用某一段欧拉序表示出来，但是可以被表示为 \(7,8,8,4,5\) ，再加上它们的LCA—— \(2\) 。
上面这两种情况分别对应于：
设一个节点 \(x\) 第一次出现在欧拉序时的位置为 \(st[x]\) ，第二次出现在欧拉序时的位置为 \(ed[x]\)，设 \(st[a]<st[b]\)，
1.如果 \(LCA(a,b)==a\) ，那么 \(a\) 到 \(b\) 的路径上的节点可以用欧拉序中的 \([st[a],st[b]]\) 来表示；
2.如果 \(LCA(a,b)\neq a\) ，那么 \(a\) 到 \(b\) 的路径上的节点可以用欧拉序中的 \([ed[a],st[b]]\) 外加 \(LCA(a,b)\) 表示。
这样，我们就通过欧拉序，将树上的区间询问转化为了序列上的区间询问，可以使用莫队算法来解决了。至于为什么会想出这个东西，只能说是前人的智慧了。
另外有的题目可能问的不是树上路径，而是某个子树的全部节点，那这时就直接使用正常的DFS序即可解决。这也说明，关于怎么将一棵树转换成为一个序列，会因题目的询问要求而异。
树上莫队的实现
树上莫队相较于普通莫队，需要额外实现的部分就是求欧拉序和LCA了。此外还需要注意在暴力移动时，要将欧拉序列上的位置正确地映射回原树上的点。
这里以 SP10707 COT2 - Count on a tree II 为例，给定 \(n\) 个结点的树，每个结点有一种颜色，有 \(m\) 次询问，每次询问 \( (u,v)\) 之间路径上结点的不同颜色数。
void discretizing()//颜色离散化
{
int pre = -1, tot = 0;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i++)
{
if (p[i].x != pre)
tot++;
a[p[i].id] = tot;
pre = p[i].x;
}
}
void dfs(int fa, int u)//倍增预处理深度，求欧拉序
{
d[u] = d[fa] + 1;
dfn[++cnt] = u;
st[u] = cnt;
f[u][0] = fa;
for (int i = 1; (1 << i) < d[u]; i++)
{
f[u][i] = f[f[u][i - 1]][i - 1];
}
for (auto v : e[u])
{
if (v == fa) continue;
dfs(u, v);
}
dfn[++cnt] = u;
ed[u] = cnt;
}
int lca(int x, int y)
{
if (d[x] < d[y]) swap(x, y);
int h = d[x] - d[y];
for (int i = 0; h; i++)
{
if (h & 1) x = f[x][i];
h >>= 1;
}
if (x == y) return x;
for (int i = lg[d[x] - 1]; i >= 0; i--)
{
if (f[x][i] != f[y][i])
{
x = f[x][i];
y = f[y][i];
}
}
return f[x][0];
}
void update(int x)//更新x位置的答案
{
if (vis[x])
{
temp -= c[a[x]] > 0;
c[a[x]]--;
temp += c[a[x]] > 0;
}
else
{
temp -= c[a[x]] > 0;
c[a[x]]++;
temp += c[a[x]] > 0;
}
vis[x] ^= 1;
}
void solve()
{
int l = 1, r = 0;
for (int i = 1; i <= m; i++)
{
for (; l > q[i].l; l--) update(dfn[l - 1]);
for (; r < q[i].r; r++) update(dfn[r + 1]);
for (; r > q[i].r; r--) update(dfn[r]);
for (; l < q[i].l; l++) update(dfn[l]);
if (q[i].lca) update(q[i].lca);
ans[q[i].id] = temp;
if (q[i].lca) update(q[i].lca);
}
}
int main()
{
n = read();
m = read();
for (int i = 1; i <= n; i++)
{
p[i].x = read();
p[i].id = i;
}
discretizing();
for (int i = 1; i < n; i++)
{
int u = read();
int v = read();
e[u].push_back(v);
e[v].push_back(u);
}
lg[1] = 0;
for (int i = 2; i <= n; i++)
{
lg[i] = lg[i - 1] + ((2 << lg[i - 1]) == i);
}
dfs(0, 1);
for (int i = 1; i <= m; i++)
{
int x = read();
int y = read();
if (st[x] > st[y]) swap(x, y);
int LCA = lca(x, y);
if (LCA == x)
{
q[i] = { st[x],st[y],i,0 };
}
else
{
q[i] = { ed[x],st[y],i,LCA };
}
}
int len = sqrt(n << 1);
for (int i = 1; i <= (n << 1); i++)
{
tag[i] = (i - 1) / len + 1;
}
sort(q + 1, q + m + 1);
solve();
for (int i = 1; i <= m; i++)
{
printf("%d\n", ans[i]);
}
return 0;
}
Comments NOTHING