Moのアルゴリズムはクエリの平方分割＆ソート

参照先

• 英語だが https://blog.anudeep2011.com/mos-algorithm/
• Codeforcesで2400などの難しさなので、早期に学ぶ必要はない

例題

• 数字の配列Aがある（長さN=10⁵など）（値域も 0～N）
• クエリがQ個ある（10⁵など）
• O(N²), O(NQ)ではTLE
• クエリ：L Rからなり、部分配列A[L...R]内で3つ以上出現する数字の数を答えよ
  • 例：A = [1 2 3 1 1 2 1 2 3 1]
  • クエリ L=1, R=8の場合、部分配列は[2 3 1 1 2 1 2 3]で、3つ以上出現するのは1, 2なので、答えは2
• AtCoder的にデータを書くと、

10
1 2 3 1 1 2 1 2 3 1
5
0 2
3 7
8 9
4 7
2 9

ナイーブなO(N²)のコード

for each query:
  answer = 0
  count[] = 0
  for i in {l..r}:
    count[array[i]]++
    if count[array[i]] == 3:
      answer++

O(N²)のコード（後で参照する）★

add(position):
  count[array[position]]++
  if count[array[position]] == 3:
    answer++

remove(position):
  count[array[position]]--
  if count[array[position]] == 2:
    answer--

currentL = 0
currentR = 0
answer = 0
count[] = 0
for each query:
  // currentL should go to L, currentR should go to R
  while currentL < L:
    remove(currentL)
    currentL++
  while currentL > L:
    add(currentL)
    currentL--
  while currentR < R:
    add(currentR)
    currentR++
  while currentR > R:
    remove(currentR)
    currentR--
  output answer

Mo

• 例として、N=16とする。sqrt(N)=4なので、Nの範囲を4ブロックに分ける
• 左端の位置を見て、各ブロックに割り当てる（下記画像参考）
• 例として、左端ソートしてから各ブロックに割り当てたとする

• 各ブロック内で、右端の昇順にソートする（下記画像参考）

• その後、上記★のコードを使うと、右端と左端の移動距離が抑えられ、O(N logN)で解くことができる

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?