geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

Mo's Algorithm

Mo ABC アルゴリズム

AtCoder Biginner Contestに出題されたので、実装してみました。

解説へのリンク(ネタバレ注意)

解説に書かれている以下のリンクに詳細があるので、アルゴリズムについては要約して書きます。

概要

数列A=\{A_0, A_1,\ \cdots ,\ A_{N-1}\}についてのQ個の閉区間[l_i,\ r_i]のクエリにO((N+Q)\sqrt{N})で答える。
やっていることはクエリの平方分割。

条件

  • Aは不変
  • クエリ先読み可
  • [l_i,\ r_i]から区間を伸縮しても、値を簡単に計算できる

アルゴリズム

  • ブロック番号\lfloor \frac{l_i}{\sqrt{N}} \rfloorの昇順、同ブロック内ではr_iの昇順でクエリをソートする
  • ソート済みのクエリを左から順に区間を伸縮して値を計算していく

計算量

  • 左端はほとんどがブロック内での移動なので、Q\sqrt{N}回
  • 右端は同ブロック内で高々N回の移動なので、N\sqrt{N}回
  • 上記を併せてO((N+Q)\sqrt{N})

例

Aのサイズを9とします。
ブロックサイズb=\sqrt{9}=3

与えられるクエリ
[5,7]
[1,3]
[3,5]
[4,4]
[7,8]
[2,5]
[0,8]
[7,7]

まず、クエリをソートします。
l_iが属するブロックを第一キーに、r_iを第二キーとして昇順にソートします。
l_iが属するブロックは\lfloor \frac{l_i}{b} \rfloorにより求められます。

ソート後(ブロック毎に区切ってあります。)
[1,3]
[2,5]
[0,8]

[4,4]
[3,5]
[5,7]

[7,7]
[7,8]

ソート後に順にクエリを処理します。
例えば、予め[2,5]の値は計算されていると仮定して[2,5] -> [0,8]を計算するときは、

  1. 右端を、[2,5] -> [2,6] -> [2,7] -> [2,8]という風に、+1ずつ区間を右に伸長しながら値を更新する
  2. 左端を、[2,5] -> [1,5] -> [0,5]という風に、-1ずつ区間を左に伸長しながら値を更新する

という感じです。