Mo's algorithm

Mo's algorithm

給 定 一 串 有 $N$ 個 整 數 的 數 列，有 $Q$ 個 查 詢，每 次 查 詢 都 會 有 $L$ 跟 $R$，求 數 列 在 $L$ 與 $R$ 之 間 的 眾 數 出 現 幾 次。

先 將 $N$ 個 元 素 切 成 $K$ 塊，接 著 將 所 有 詢 問 按 照 $L_i$ 所 在 的 區 塊 排 序，如 果 在 同 一 個 區 塊，就 再 對 $R_i$ 做 排 序。
用 app [ x ] 來 記 錄 數 字 x 出 現 的 次 數，再 用 cnt [ y ] 紀 錄 出 現 y 次 數 字 有 幾 個。
每 次 要 加 入 或 刪 除 新 數 字 時，更 新 兩 個 陣 列。

-複 雜 度:

因 為 分 塊 的 特 性，在 同 一 塊 的 左 界 不 會 移 動 超 過 $\frac{N}{K}$ 次，而 左 界 屬 於 不 同 塊 的 操 作，移 動 次 數 最 多 也 不 會 超 過 $N$ 次。所 以 左 界 移 動 複 雜 度 是 $O(\frac{N Q}{K})$。
對 於 右 界 因 為 $R_i$ 是 遞 增，所 以 對 於 同 一 塊 複 雜 度 最 多 $O(N)$，對 不 同 塊 因 為 交 界 最 多 $K$ 次，每 次 最 多 也 $O(N)$，所 以 維 護 右 界 複 雜 度 為 $O(K N)$，取 $K = \sqrt{N}$，得 到 $O(\frac{N Q}{K} + K N)$ = $O(Q\sqrt{N} + N\sqrt{N})$

-優 化:

每 一 塊 的 $R_i$ 都 是 遞 增，再 遇 到 交 界 處 時 會 有 一 個 " 大 斷 層 "，即 是 右 界 必 須 移 動 許 多 次，但 是 如 果 反 過 來 變 成 遞 減 就 不 必 花 費 多 餘 的 時 間。而 遞 減 後 下 一 個 也 必 須 是 遞 增。
實 做 判 斷 區 塊 是 否 為 偶 數 進 行 遞 增 或 遞 減 排 序。

code: