查詢的順序不影響答案的正確性，但影響計算的效率——莫隊把這個自由度榨乾。
問題設定
靜態陣列，q 個區間查詢（例如「[L, R] 內有幾個不同的數字」）。
暴力：每個查詢從頭計算，O(n) per query，總 O(nq)。
更聰明的做法：如果上一個查詢是 [3, 7]，下一個是 [4, 9]，只需要移動兩步（左邊縮一個、右邊擴兩個），而不是重新計算。
莫隊的核心洞察：查詢的順序可以自由排列（答案不依賴查詢的先後）。選一個讓總移動步數最小的順序。
分塊排序
把陣列分成 √n 個塊（每塊大小 √n），查詢排序規則：
- 先按左端點所在的塊號排序
- 同一塊內，按右端點排序（奇數塊升序，偶數塊降序——奇偶優化）
int blockSize = (int) Math.sqrt(n);
Arrays.sort(queries, (a, b) -> {
int ba = a.l / blockSize, bb = b.l / blockSize;
if (ba != bb) return ba - bb;
return (ba & 1) == 0 ? a.r - b.r : b.r - a.r; // 奇偶優化
});移動分析
右指標：同一塊內右端點排好序，R 只往右走
每塊內總移動 O(n) → 共 √n 個塊 → 右指標總移動 O(n√n)
左指標：每次換塊最多移動 O(√n)
共 q 個查詢 → 左指標總移動 O(q√n)
總移動：O((n + q)√n)
q ≈ n 時：O(n√n) ≈ O(n^1.5)
n = q = 10^5：O(n√n) ≈ 3×10^7，可以接受實作框架
int curL = 0, curR = -1;
for (Query q : queries) {
while (curR < q.r) add(++curR); // 右邊擴展
while (curL > q.l) add(--curL); // 左邊擴展
while (curR > q.r) remove(curR--); // 右邊收縮
while (curL < q.l) remove(curL++); // 左邊收縮
answers[q.idx] = getAnswer();
}add(pos) 和 remove(pos) 需要 O(1) 更新（維護計數陣列等）：
int[] count = new int[MAXVAL];
int distinct = 0;
void add(int pos) {
if (count[arr[pos]]++ == 0) distinct++;
}
void remove(int pos) {
if (--count[arr[pos]] == 0) distinct--;
}限制
莫隊的兩個硬性限制：
- 離線：必須提前知道所有查詢（不支援在線查詢）
- 靜態：陣列不能被修改（有支援修改的「帶修莫隊」，但複雜度降到 O(n^(5/3))）
如果問題是離線且靜態的，莫隊幾乎是最簡單的 O(n^1.5) 解法。上面 distinct 那組 add/remove 換個維護目標就能解別的題：想求「區間眾數」，就把計數陣列外加一個「目前最大計數」，add/remove 時順手更新——莫隊的框架不動，只換 add/remove 的內容物。
莫隊 vs 其他區間查詢
| 方法 | 時間 | 支援修改 | 特點 |
|---|---|---|---|
| 暴力 | O(nq) | ✅ | 最簡單 |
| 線段樹 | O(q log n) | ✅ | 通用、可在線 |
| 莫隊 | O((n+q)√n) | ❌ | 離線，程式碼短 |
| 帶修莫隊 | O(n^(5/3)) | ✅ | 多一維時間軸，較複雜 |
莫隊真正的甜蜜區，是那種「線段樹寫不出漂亮合併、但 add/remove 只要 O(1)」的題——像區間不同元素個數，用線段樹得套一堆離線技巧，莫隊三行 add/remove 就收工。反過來，只要查詢得在線回答，莫隊直接出局，乖乖回去用線段樹。
🎬 互動視覺化：莫隊排序與指標移動 — 看查詢被重新排序後，L / R 兩根指標如何小步挪移、少走多少冤枉路，「調度省功」的直覺用動畫最清楚。
莫隊的本質是一個調度策略——它不讓你更快地計算每個查詢，而是讓你少做不必要的重複計算。
接下來往哪走
- Aho-Corasick 自動機：同時搜尋所有關鍵字 — 下一篇：從區間查詢切到多模式字串匹配
- Segment Tree 線段樹 — 支援修改的在線區間查詢，莫隊兩個硬限制的解法
- Fenwick Tree (BIT) 樹狀陣列 — 區間查詢家族更輕量的成員，能用它就不用線段樹