莫隊演算法：把亂序查詢變成有序移動

查詢的順序不影響答案的正確性，但影響計算的效率——莫隊把這個自由度榨乾。

問題設定

靜態陣列，q 個區間查詢（例如「[L, R] 內有幾個不同的數字」）。

暴力：每個查詢從頭計算，O(n) per query，總 O(nq)。

更聰明的做法：如果上一個查詢是 [3, 7]，下一個是 [4, 9]，只需要移動兩步（左邊縮一個、右邊擴兩個），而不是重新計算。

莫隊的核心洞察：查詢的順序可以自由排列（答案不依賴查詢的先後）。選一個讓總移動步數最小的順序。

分塊排序

把陣列分成 √n 個塊（每塊大小 √n），查詢排序規則：

1. 先按左端點所在的塊號排序
2. 同一塊內，按右端點排序（奇數塊升序，偶數塊降序——奇偶優化）

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--;
}

限制

莫隊的兩個硬性限制：

1. 離線：必須提前知道所有查詢（不支援在線查詢）
2. 靜態：陣列不能被修改（有支援修改的「帶修莫隊」，但複雜度降到 O(n^(5/3))）

如果問題是離線且靜態的，莫隊幾乎是最簡單的 O(n^1.5) 解法。

---

莫隊的本質是一個調度策略——它不讓你更快地計算每個查詢，而是讓你少做不必要的重複計算。