莫队算法

莫队算法

概述

莫队算法是一种离线分块算法，用于解决序列上的区间查询问题。若区间 $[l,r]$ 的答案能 $O(1)$ 扩展到相邻区间 $[l-1,r],[l+1,r],[l,r+1],[l,r-1]$，则可在 $O(n\sqrt{n})$ 复杂度内求出所有询问。

排序与分块

以 $l$ 所在块编号为第一关键字，$r$ 为第二关键字排序。块大小取 $S=n/\sqrt{m}$ 时最优，总复杂度 $O(n\sqrt{m})$。

奇偶排序优化：奇数块 $r$ 升序，偶数块 $r$ 降序，减少 $r$ 指针回跳，可提速约 30%。

int unit;
struct Node {
  int l, r, id;
  bool operator<(const Node &x) const {
    if (l / unit != x.l / unit) return l < x.l;
    return (l / unit) & 1 ? r < x.r : r > x.r;
  }
};

模版框架

void move(int pos, int sign) { /* update nowAns */ }
 
void solve() {
  int block = ceil(pow(n, 0.5));
  sort(q, q + m);
  int l = 1, r = 0;
  for (int i = 0; i < m; ++i) {
    while (l > q[i].l) move(--l, 1);
    while (r < q[i].r) move(++r, 1);
    while (l < q[i].l) move(l++, -1);
    while (r > q[i].r) move(r--, -1);
    ans[q[i].id] = nowAns;
  }
}

四个 while 顺序：必须先扩大区间（--l / ++r），再缩小区间（l++ / r--），否则会导致 $l>r+1$ 使维护出错。

应用与例题

• P1972 HH的项链 — 区间不同数个数
• P2709 小B的询问 — 区间各数出现次数平方和
• P1494 小Z的袜子 — 区间随机两数相等的概率

题目	链接	难度
P1972	HH 的项链	省选/NOI-
P2709	小 B 的询问	普及/提高-
P1494	小 Z 的袜子	省选/NOI-

扩展阅读

• 带修莫队（modifiable-mo-algo）
• 树上莫队（mo-algo-on-tree）
• 回滚莫队（rollback-mo-algo）

更多练习题见 路径D-DSA算法刷题。

多平台练习

| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |