参照先
- 英語だが https://blog.anudeep2011.com/mos-algorithm/
- Codeforcesで2400などの難しさなので、早期に学ぶ必要はない
例題
- 数字の配列Aがある(長さN=105など)(値域も 0~N)
- クエリがQ個ある(105など)
- O(N2), 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(N2)のコード
for each query: answer = 0 count[] = 0 for i in {l..r}: count[array[i]]++ if count[array[i]] == 3: answer++
O(N2)のコード(後で参照する)★
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版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る