一、要解决的问题
静态数组（无修改）上有 q 个区间询问 [l, r]，每次问区间内某种统计量（如"出现次数平方和""不同颜色数"）。如果"已知 [l, r] 的答案，能在 O(1) 增删一个端点得到相邻区间的答案"，莫队就能以 O((n+q)√n) 解决全部询问——不用任何高级数据结构。
生活类比：快递员要送 q 个地址。按提交顺序送会全城来回跑；聪明做法是先按街区把地址排好序，同一街区的集中送。莫队就是给询问设计一个"顺路的访问顺序"，让区间端点移动的总路程最短。
端点移动怎么更新答案？（以颜色次数平方和为例）
| 当前区间状态 | 动作 | 答案变化 |
|---|---|---|
| 颜色 {红:1, 蓝:1}，答案 1²+1² = 2 | R 右移，加入一个"红" | 红从 1 变 2：1²→2²，增量 2×1+1 = 3，答案 5 |
| 颜色 {红:2, 蓝:1}，答案 5 | L 右移，移出一个"红" | 红从 2 变 1：2²→1²，减量 2×1+1 = 3，答案 2 |
二、核心：询问的排序魔法
- 把位置 1..n 按大小 B = √n 分块，块号 = (l − 1) / B。
- 询问排序：先按 l 的块号升序；同块内按 r 升序（奇偶优化：奇数块 r 升序、偶数块 r 降序，指针掉头更少）。
- 维护当前区间 [L, R] 的答案与桶 cnt[]；按排序后的顺序处理询问，移动 L、R 逐个增删元素更新答案。
复杂度：L 每块内移动 O(n)，跨块 O(B)；R 在每块内单调 O(n)。总计 O(n·(n/B) + q·B)，B = √n 时 O((n+q)√n)
三、模板代码（P2709 小 B 的询问）
问题：每次询问区间 [l, r] 的 Σ cnt[c]²（每种颜色出现次数的平方和）。增删一个元素时维护当前和：
struct Q { int l, r, id, blk; } qs[M];
bool cmp(Q a, Q b) {
if (a.blk != b.blk) return a.blk < b.blk;
return (a.blk & 1) ? a.r < b.r : a.r > b.r; // 奇偶优化
}
long long cur = 0;
void add(int x) { cur += 2 * cnt[x] + 1; cnt[x]++; } // (k+1)²−k² = 2k+1
void remove(int x) { cnt[x]--; cur -= 2 * cnt[x] + 1; }
// 主循环：按 cmp 排序后，移动 L/R 到 [q.l, q.r]，记录 ans[q.id] = cur四、适用范围与边界
| 适用 | 不适用 |
|---|---|
| 静态数组（无修改）、可离线、端点增删 O(1) | 带修改（需带修莫队，多一维时间轴，常数大） |
| n, q ≤ 10⁵ 量级，统计量可增量维护 | 强制在线（询问依赖上次答案）→ 上主席树/树状数组 |
五、易错点清单
- add / remove 的更新顺序：先改答案再改 cnt（或反之）必须与自己的公式自洽，写错一位全盘错。
- 区间是闭区间 [l, r]：指针初始位置（L=1, R=0 的空区间）与移动方向要想清楚。
- 块长 B 取 √n 只是默认；q 远大于 n 时调大到 n/√q 附近更优，卡常题可试。
- 答案累加用
long long；下标 0/1 混用是莫队最常见的翻车点。
六、练习
- P2709 小 B 的询问（莫队模板）
- P1972 [SDOI2009] HH的项链（不同颜色数，也可用树状数组对照）