Mo’s algorithm を使う問題はそんなに頻繁に出てくるわけではないので， 書こうとして，あれ，なんだっけ，となりがちです． ライブラリにするほどではないと思うので， コンテストの時に貼れるようにメモをしておきます．

適用できる問題

  • $Q$個のクエリ $\text{query}(l, r)$ を処理せよという形． ($0 \leq l \leq r \leq N$)
  • $\text{query}(l - 1, r)$ $\text{query}(l + 1, r)$ $\text{query}(l, r - 1)$ $\text{query}(l, r + 1)$ は， $\text{query}(l, r)$ から $O(1)$ で計算できる．
  • クエリは先読み可能である．
  • 計算量は $O(N\sqrt{Q})$ で，定数倍は結構大きいので， $Q$ や $N$ の大きさは，$10^5$ とか せいぜい $10^6$ とかいったところ

アルゴリズム

  • $[0, N]$ を $\sqrt{Q}$ 個のブロックに (だいたい) 等分割する
  • 次の順序でクエリをソートする: $(l, r)$ と $(l’, r’)$ との比較で:
    • $l$ と $l’$ が入るブロックが違う時には，左のブロックに入っている方が先
    • 同じブロックに入る時には，$r$ と $r’$ で小さい方が先
  • この順序でクエリを処理する．前回の値から $l$ と $r$ を1つずつ増減させて 今回の値を求める．

計算量

ブロックの個数を $K$，ブロックのサイズを $B$ とする． $l$ の増減による計算はたいてい $B$ 以下で，ブロックをまたぐときも $2B$ 以下だから，全体で $O(BQ)$回． $r$ の増減による計算はあるブロックを処理している間の合計で $N$ 以下だから， 全体で $O(KN)回$．ここでだいたい $K = \sqrt{Q}$, $B = N / K$ だから， 両者合わせて $O(BQ + KN)$ = $O(N\sqrt{Q})$ である．

コード例

$\text{query}(l, r)$ が， 「$\bigoplus\{ a_i \mid i \in [l, r) \}$ を求めよ」という問題だと した場合，次のようなコードで計算できる．

    // ブロックサイズ
    ll B = max(1LL, llround(1.3 * N / sqrt(Q)));  // 1.3 は適当に調整...

    // クエリの先読み
    using tup_t = tuple<int, int, int, int>; // ブロックID, r, l, クエリID
    vector<tup_t> qs;
    for (int query_id = 0; query_id < Q; query_id++) {
      int l, r; cin >> l >> r; l--;       // 添字0開始，半開区間
      int block_id = l / B;
      qs.emplace_back(block_id, r, l, query_id);
    }

    // 重要: ソートを忘れない!
    sort(qs.begin(), qs.end(),
         // 比較関数は無くても良いが，あった方が速い．「補足」参照
         [](const tup_t& t1, const tup_t& t2) -> bool {
           auto [block_id1, r1, _a, _b] = t1;
           auto [block_id2, r2, _c, _d] = t2;
           if (block_id1 != block_id2) return block_id1 < block_id2;
           if ((block_id1 & 1) == 0) return r1 < r2;
           else                      return r1 > r2;
         });

    // メイン
    vector<T> ans(Q);
    state_t state = state_t();  // 現在のクエリの状態を初期化
    int cl = 0, cr = 0;         // 現在の l, r の値
    for (auto [_not_used, r, l, query_id] : qs) {
      while (l < cl) {      // 左側が拡張
        cl--;
        state.add(A[cl]);
      }
      while (cr < r) {      // 右側が拡張
        state.add(A[cr]);
        cr++;
      }
      while (cl < l) {      // 左側が縮小
        state.subtract(A[cl]);
        cl++;
      }
      while (r < cr) {      // 右側が縮小
        cr--;
        state.subtract(A[cr]);
      }
      ans[query_id] = state.value();
    }

    for (T a : ans) cout << a << "\n";   // 答の出力

補足1

Codeforces の記事 に， Hilbert curve を使うと性能があがるという報告があります． 追試をしてみましたが，あまり速くなりませんでした． 左右端の拡張と縮小の回数を減らそうという趣旨とみましたが， もとの Mo’s algorithm のブロックサイズを適切に設定することによって， ほぼ同等の回数にすることができます． Hilbert curve order を計算する時間が馬鹿にならないので， トータルの性能としては，改善されないようです．

補足2

姑息な定数倍高速化ですが， クエリをソートする際に， $r$ の側は左→右と右→左を交互に行うのが得策のようです． データにもよるでしょうが， 実験してみたところ，拡張・縮小回数を30%ほど削減できました (実行時間も20%ほど減りました)．