前言
莫队是由莫涛提出的一种离线算法，是分块与双指针的结合，一般可以在 \(O(n \sqrt n)\) 或者 \(O(n \sqrt m)\) 的复杂度解决一些种类问题。
普通莫队
给你一个长度为 \(n\) 的数列 \(A\)，\(m\) 次询问，每次询问区间 \([l,r]\) 内的不同数字的个数。
如果要在线的话，需要用主席树。
我们考虑离线，把每个操作离线下来，然后挂到序列上。
每一个颜色代表一个询问。
可以想到用双指针来做，代表区间 \([l, r]\)，如果任意指针移动就更新答案，是 \(O(1)\) 的。
想象是美好的，现实是残酷的。
如果询问是这样子的话：
那么尽管排完序左端点的移动可以做到 \(O(n)\)，但是啊但是，右端点是无序的，就又会把复杂度打会 \(O(nm)\)。
那么这时候，莫队诞生了。
莫队在原来的基础上加了一个分块与排序。
可以证明复杂度是 \(O(n\sqrt n)\) 的。
对于左端点，如果每一个块中有 \(x\) 个询问的左端点，那么对于这个块的最坏复杂度是 \(O(x_i\sqrt n)\)。对于整个块，跨越一次需要 \(O(\sqrt n)\)，最坏会跨整个序列，也就是 \(O(n)\)，那么复杂度就是 $ O (\sum x_i\sqrt n + n\sqrt n) = O (n \sqrt n)$。
对于右端点，因为已经排完序，最坏需要跨整个序列，也就是 \(O(n)\)，有 \(O(\sqrt n)\) 块，所以复杂度就是 \(O(n \sqrt n)\)。
所以总复杂度就是 \(O(n \log n + n \sqrt n + n \sqrt n) = O(n \sqrt n)\)。
回到这题，我们已经可以基本写出来了。
int n, m, len, tot;
int a[N], cnt[V];
bool cmp (Query A, Query B) { return A.x / len == B.x / len ? (A.y == B.y ? 0 : ((A.x / len) & 1) ^ (A.y < B.y)) : A.x < B.x; }
bool Cmp (Query A, Query B) { return A.id < B.id; } // 这里用了两个 cmp，实际不需要，用一个 ans 数组记录即可。
// 移动指针的修改
void add (int x) {
if (!cnt[a[x]]) tot++;
cnt[a[x]]++;
}
void del (int x) {
if (cnt[a[x]] == 1) tot--;
cnt[a[x]]--;
}
int main () {
len = sqrt (n); // 这句话千万别漏了
sort (q + 1, q + m + 1, cmp);
for (int i = 1, l = 1, r = 0; i <= m; ++i) {
while (l > q[i].x) add (--l);
while (r < q[i].y) add (++r);
while (l < q[i].x) del (l++);
while (r > q[i].y) del (r--);
q[i].ans = tot;
}
sort (q + 1, q + m + 1, Cmp);
return 0;
}
带修莫队
给你一个长度为 \(n\) 的序列 \(A\) 以及 \(m\) 个操作，要你支持单点修改，并且询问区间颜色种类数。
现在带修了（恼）。
我们可以把每个询问抽象成 \((l, r)\) 的一个点对，这样我们可以构建出一个二维空间。
我们不妨把每一个操作用时间戳来表示，这样我们就可以多一个维度 \(t\)，用来记录每次询问的时间维度。
初始化时，只需要找到最近的那个时间维度即可。
再来考虑考虑这个维度该怎么转移。
我们假设当前这个区间已经修改了 \(x\) 次，要转移到修改 \(y\) 次的序列。
如果 \(x \lt y\)，那么我们需要把 \(x + 1\) 到 \(y\) 个修改全都加上。
如果 \(x \gt y\)，那么我们需要把 \(x\) 到 \(y + 1\) 个修改全部还原。
什么？你问 \(x = y\)？
这种情况还需要转移吗。。。
于是我们在原来莫队的基础上加了一维，成功地实现了带修莫队。
int n, m, len, qcnt, rcnt;
int a[N], ans[N], cnt[V], tot;
struct Query {
int id, l, r, t;
bool operator < (const Query &T) {
if (l / len != T.l / len) return l < T.l;
if (r / len != T.r / len) return r < T.r;
return t < T.t;
}
} q[N];
void add (int x) {
if (!cnt[x]) tot++;
cnt[x]++;
}
void del (int x) {
if (cnt[x] == 1) tot--;
cnt[x]--;
}
int main () {
for (int i = 1; i <= m; ++i) {
char opt;
int x, y;
cin >> opt >> x >> y;
if (opt == 'Q') q[++qcnt] = (Query){qcnt, x, y, rcnt};
else r[++rcnt] = (Modify){x, y};
}
len = pow (n, 2.0 / 3.0);
int L = 1, R = 0, now = 0;
sort (q + 1, q + qcnt + 1);
for (int i = 1; i <= qcnt; ++i) {
while (L > q[i].l) add (a[--L]);
while (R < q[i].r) add (a[++R]);
while (L < q[i].l) del (a[L++]);
while (R > q[i].r) del (a[R--]);
while (now < q[i].t) {
now++;
if (L <= r[now].x && r[now].x <= R) {
add (r[now].y);
del (a[r[now].x]);
}
swap (a[r[now].x], r[now].y);
}
while (now > q[i].t) {
if (L <= r[now].x && r[now].x <= R) {
add (r[now].y);
del (a[r[now].x]);
}
swap (a[r[now].x], r[now].y);
now--;
}
ans[q[i].id] = tot;
}
return 0;
}
树上莫队
众所周知，莫队是用于序列上的一种算法，如果要用到树上，我们最先想到的就是把树序列化。
树上莫队？
但是一般的 DFS 序这样肯定是不行的，毕竟要方便统计路径上权值的种类数。
但是欧拉序很好的满足了这个要求。
如图，可以发现欧拉序只有标红圈的节点没有算上，而这个标红圈的节点正是 \(2\) 与 \(6\) 的 Lca。
所以我们只需要在转移过程中特判一下即可。
SP10707 COT2 - Count on a tree II
给你一棵 \(n\) 个节点的树，每次询问路径 \(u\) 到 \(v\) 上的权值种类数。
典，直接上。
const int N = 2e5 + 5;
int n, m, len;
int dep[N], fa[N][31], lg[N], eu[N], ucnt;
int fi[N], ls[N];
void dfs (int now, int fath){
fa[now][0] = fath;
dep[now] = dep[fath] + 1;
eu[++ucnt] = now;
fi[now] = ucnt;
for (int i = 1; i < 31; ++i){
fa[now][i] = fa[fa[now][i-1]][i-1];
}
for (int i = head[now]; i; i = e[i].nxt)
if (e[i].v != fath)
dfs(e[i].v, now);
eu[++ucnt] = now;
ls[now] = ucnt;
}
int Lca (int x, int y)
void modify (int x) {
if (!vis[x]) {
if (!cnt[a[x]]) tot++;
cnt[a[x]]++;
} else {
if (cnt[a[x]] == 1) tot--;
cnt[a[x]]--;
}
vis[x] ^= 1;
}
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
b[i] = a[i];
}
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
addEdge (u, v);
addEdge (v, u);
}
sort (b + 1, b + n + 1);
int ret = unique (b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = lower_bound (b + 1, b + n + 1, a[i]) - b;
len = sqrt (n);
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
if (fi[x] > fi[y]) swap (x, y);
q[i].id = i, q[i].lca = Lca (x, y);
if (q[i].lca == x) {
q[i].x = fi[x];
q[i].y = fi[y];
q[i].lca = 0;
} else {
q[i].x = ls[x];
q[i].y = fi[y];
}
}
sort (q + 1, q + m + 1);
int l = 1, r = 0;
for (int i = 1; i <= m; ++i) {
while (l > q[i].x) modify (eu[--l]);
while (r < q[i].y) modify (eu[++r]);
while (l < q[i].x) modify (eu[l++]);
while (r > q[i].y) modify (eu[r--]);
if (q[i].lca) modify (q[i].lca); // 注意特判
ans[q[i].id] = tot;
if (q[i].lca) modify (q[i].lca);
}
return 0;
}