はじめての Mo's Algorithm
/icons/hr.icon
はじめに
この記事は以下の条件を$ 1つでも満たしている方に最適です
Mo's アルゴリズムを聞いたことない / 聞いたことはあるが何もわからない
競技プログラミングをしていて Mo's アルゴリズムを学んでみたい
Mo's アルゴリズムの実装・計算量を知りたい方
/icons/hr.icon
発表
アルゴ式の LT で Mo's アルゴリズムを紹介した資料になっています
発表日：2023/06/15(木) 21:00~21:30
発表日：2023/06/17(土) 23:00~0:00
/icons/hr.icon
導入
Mo's Algorithm は区間 $ \left[ l_i, r_i \right] に対するクエリを高速で処理するアルゴリズムです
まずは Mo's を紹介する前に簡単な Step を踏んで解説していきます
/icons/hr.icon
Step 1
想定 diff 50
問題文
長さ $ Nの数列 $ A = (A_1, A_2, ..., A_N)が与えられます。
$ 1 \leq L \leq R \leq Nを満たす区間内の種類数を答えてください。
制約
$ 1 \leq N \leq 10^5
$ 1 \leq A_i \leq 10^5 \quad (1 \leq i \leq N)
$ 1 \leq L \leq R \leq N
入力
入力は以下の形式で標準入力から与えられる。
$ N \quad L \quad R
$ A_1 \quad A_2 \quad \cdots \quad A_N
入力例１
$ 7 \quad 2 \quad 6
$ 3 \quad 8 \quad 2 \quad 5 \quad 19 \quad 8 \quad 4
出力例１
$ 4
$ (A_2, A_3, A_4, A_5, A_6) = (8, 2, 5, 19, 8)で$ 5つの数字がありますが、$ 8が重複しているため、種類数は$ 4になります。
/icons/hr.icon
解説
１つ１つ愚直に見ていっても計算量は高々 $ O(N) なので、前から全探索を行うことで解くことが出来ます。
C++ によるソースコード
code:main.cpp
using namespace std;
int main() {
int N, L, R;
cin >> N >> L >> R;
vector<int> A(N);
for (int i = 0; i < N; i++) {
}
unordered_set<int> num;
for (int i = L; i < R + 1; i++) {
}
cout << num.size() << endl;
return 0;
}
Python によるソースコード
code:main.py
N, L, R = map(int, input().split())
A = list(map(int, input().split()))
num = set()
for i in range(L, R + 1):
print(len(num))
/icons/hr.icon
Step 2
想定 diff 80
問題文
長さ $ Nの数列 $ A = (A_1, A_2, ..., A_N)が与えられます。
クエリが $ Q個与えられます。$ i番目のクエリでは $ l_i番目から$ r_i番目までにある数の種類数を答えてください。
制約
・$ 1 \leq N \leq 10^4
・$ 1 \leq A_i \leq 10^5 \quad (1 \leq i \leq N)
・$ 1 \leq Q \leq 10^4
・$ 1 \leq l_i \leq r_i \leq N \quad (1 \leq i \leq Q)
入力
入力は以下の形式で標準入力から与えられる。
$ N
$ A_1 \quad A_2 \quad \cdots \quad A_N
$ Q
$ l_1 \quad r_1
$ l_2 \quad r_2
$ \vdots
$ l_Q \quad r_Q
入力例１
$ 7
$ 1 \quad 2 \quad 3 \quad 4 \quad 3 \quad 2 \quad 1
$ 3
$ 1 \quad 4
$ 3 \quad 5
$ 6 \quad 6
出力例１
$ 4
$ 2
$ 1
$ 1つ目のクエリでは、$ (A_1, A_2, A_3, A_4) = (1, 2, 3, 4)なので種類数は$ 4です
$ 2つ目のクエリでは、$ (A_3, A_4, A_5) = (3, 4, 3)なので種類数は$ 2です
$ 3つ目のクエリでは、$ (A_6) = (2)なので種類数は$ 1です
/icons/hr.icon
解説
一見するとどうすれば良いかわからないかもしれないが、制約に着目すると、$ N, Qともに$ 10^4以下であることがわかるため、１つ１つのクエリに対して愚直に $ O(N) で処理を行えば、$ O(NQ) でこの問題を解くことが出来る。
C++ によるソースコード
code:main.cpp
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) {
}
int Q;
cin >> Q;
for (int i = 0; i < Q; i++) {
int l, r;
cin >> l >> r;
unordered_set<int> num;
for (int j = l; j < r + 1; j++) {
if (num.find(Aj - 1) == num.end()) { }
}
cout << num.size() << endl;
}
return 0;
}
Python によるソースコード
code:main.py
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
l, r = map(int, input().split())
num = set()
for i in range(l, r + 1):
print(len(num))
/icons/hr.icon
Step 3
想定 diff 500
$ 1つずつループを回しても良いですが、Mo's アルゴリズムは冒頭にも述べたように区間を伸び縮みしてクエリを高速に処理するアルゴリズムです。
なので、次のステップとして区間を伸び縮みさせて問題を解いてみましょう
区間を伸び縮みするということは今まで使用していたunordered_setやsetは使用することができません（クエリ内に複数あるのか$ 1つしかないのかわからないため）
しゃくとり法のイメージが Mo's アルゴリズムには最も近いと思います（個人的に）
したがって、配列を用意してそれぞれの数字が区間内にいくつあるのかわかるようにコードを書いていきます
C++によるソースコード
code:C++
using namespace std;
int len_ = 0; // 要素数をカウントするもの
vector<int> num;
void add(int i) {
len_++;
}
}
void remove(int i) {
len_--;
}
}
int main() {
int N;
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) {
}
int Q;
cin >> Q;
int left = 0, right = 0;
num.resize(2 * (int)1e5 + 10, 0);
for (int k = 0; k < Q; k++) {
int l, r;
cin >> l >> r;
l--;
r--;
// ①
while (right <= r) {
right++;
}
// ②
while (l < left) {
left--;
}
// ③
while (r + 1 < right) {
right--;
}
// ④
while (left < l) {
left++;
}
cout << len_ << "\n";
}
return 0;
}
Python によるソースコード
code:python
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
left, right = 0, 0 # 今いる左端と右端の座標
len_ = 0 # 要素数
def add(i: int) -> None:
global len_, num
len_ += 1
def delete(i: int) -> None:
global len_, num
len_ -= 1
for _ in range(Q):
l, r = map(int, input().split())
l -= 1
r -= 1
# ①
while right <= r:
right += 1
# ②
while l < left:
left -= 1
# ③
while r + 1 < right:
right -= 1
# ④
while left < l:
left += 1
print(len_)
/icons/hr.icon
いきなり変なものが ①〜④ までの変なものが出てきましたね。
これこそが Mo's Algorithm の本質 です！！
何をしているのか下で説明をしていきます。
table:Mo's algorithm
変数 役割
left 1つ前までのクエリの左端
right 1つ前までのクエリの右端
l 今回処理するクエリの左端
r 今回処理するクエリの右端
①について
https://scrapbox.io/files/648bb378cacc0b001b67b69d.png
/icons/hr.icon
②について
https://scrapbox.io/files/648bb37070a87d001b771eec.png
/icons/hr.icon
③について
https://scrapbox.io/files/648bb36aa937a6001ce6873f.png
/icons/hr.icon
④について
https://scrapbox.io/files/648bb36441bc7d001b0c72df.png
/icons/hr.icon
Step 4
想定 diff 1600
Step 2, Step 3 では、$ O(NQ)でも高々$ 10^8だったので愚直に解けた
では、$ 10^{10}程度かかる場合どうだろうか？これは愚直にやっても時間がかかってしまう。
例えば、$ 1 \leq N, Q \leq 10^5のような場面です、愚直に探索すると TLE になります...
ここで登場するのが Mo's Algorithm です
/icons/hr.icon
Mo's アルゴリズムの使える場面
Mo's アルゴリズムを使用するには以下の条件を最低でも満たしている必要があります
クエリがオフラインである
順番を入れ替えたりしても問題がない、独立しているイメージ
区間を伸び縮みしながら解くことができる
以下の問題は区間を伸び縮みすることができないため Mo's が使えません
【追記】使えないと思っていましたがこれは使えるみたいです。
区間幅を$ N、クエリ数を$ Qとした際に、$ O(N\sqrt{Q})が間に合う
Mo's アルゴリズムの計算量が$ O(N\sqrt{Q})なのでこれが制約上間に合わなければ、そもそも不可能です
/icons/hr.icon
Mo's アルゴリズムの可視化
https://scrapbox.io/files/648970c199f81d001b45d738.pnghttps://scrapbox.io/files/6489720499f81d001b45f557.pnghttps://scrapbox.io/files/648971198e96a3001bc81437.pnghttps://scrapbox.io/files/648971276e1ccf001b5d425d.png
左から Step$ 1, 2, 3, 4として以下の解説を進めていきます
今回は $ N = 100, Q = 200 で実験を可視化を行っています
Step 1
ランダムにクエリを$ 200個生成します
Step 2
生成したクエリを左端で昇順にソートします
Step 3
左端が$ \sqrt{Q}分割したブロックのうち、含まれる領域に格納していきます
$ l_i \times \frac{\sqrt{Q}}{N}の結果により、queriesの入るインデックスを計算します
（$ 1 \leq l_i \leq Nより、$ l_iが最小の際は$ 0となり、$ l_iが最大の際には、約分されて$ \sqrt{Q}番目（最後）に格納されます）
Step 4
ブロック内の並びを昇順と降順の交互に並べ替えていきます
このようにすることで、定数倍高速化に繋がります（後述）
/icons/hr.icon
Mo's アルゴリズムの計算量解析
L の計算量について
$ Q 個のクエリを$ \sqrt{Q} 個のブロックに分割しているため、その１つ１つのブロックについて着目する
$ 1つのブロック内で$ Lは$ \dfrac{N}{\sqrt{Q}}だけ動く（縦線は区間幅$ Nを$ \sqrt{Q}分割しているため）
それが全部で クエリの数$ (=Q)個あるため、計算量は$ O(\dfrac{N}{\sqrt{Q}} \times Q) = O(N\sqrt{Q})
R の計算量について
$ Q個のクエリを$ \sqrt{Q}個のブロックに分割しており、$ 1つのブロック内で$ Rは最大で区間幅$ Nしか動かない$ （= １つあたりの R のブロックの計算量は O(N)）
このブロックが$ \sqrt{Q}個あるため、計算量は$ O(N\sqrt{Q})となる
したがって、全体の計算量も$ O(N\sqrt{Q} + N\sqrt{Q}) = O(N\sqrt{Q})となる
/icons/hr.icon
実装
実装は至ってシンプルです
まず初めに入力を受け取りましょう
code:cpp
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for(int i=0; i<n; ++i) {
}
int q;
cin >> q;
int block = (int)(sqrt(n)) + 1 ; // ブロックサイズ
vector<vector<tuple<int, int, int>>> queries((int)(sqrt(q)) + 1); // クエリを受け取る配列
// クエリを受け取る
for (int i=0; i<q; i++) {
int l, r;
cin >> l >> r;
l--; r--;
queriesl / block.push_back(make_tuple(i, l, r)); }
vector<int> ans(q);
int left = 0, right = 0; // スタート地点は left, right ともに 0
vector<int> num(2*1e5 + 10, 0); // numi := 今見ている区間 left, right に存在する i の個数 int len_ = 0; // num に入っている要素数
return 0;
}
code:python
n = int(input())
a = list(map(int, input().split()))
q = int(input())
block = int(n / q ** 0.5) + 1 # ブロックサイズ
queries = [[] for _ in range(int(q**0.5) + 1)] # クエリを受け取る配列
# クエリを受け取る
for i in range(q):
l, r = map(int, input().split())
l -= 1
r -= 1
left, right = 0, 0 # スタート地点は left, right ともに 0
num = 0 * (2*10**5 + 10) # numi := 今見ている区間 left, right に存在する i の個数 len_ = 0 # num に入っている要素数
/icons/hr.icon
次に区間を縮めた際に処理する関数 delete と、区間を広げた際に処理する関数 add を定義します
code:cpp
void add(int i, vector<int>& num, int& len_) {
len_++;
}
}
void delete_(int i, vector<int>& num, int& len_) {
len_--;
}
}
code:python
def add(i: int) -> None:
global num, len_
len_ += 1
def delete(i: int) -> None:
global num, len_
len_ -= 1
add関数
今回の問題では種類数を答える問題なので、それぞれの値が初めて区間内に出現した場合には、要素数を記録するlen_に$ 1を加算します
その後、num[i]に$ 1 を加算することで今見ている区間に要素$ iを$ 1つ追加します
/icons/hr.icon
delete関数
逆に区間を縮めた際にその値の出現回数が$ 1 \Rightarrow 0になった場合には、要素数が減るのでlen_に$ 1を減算します
その後、num[i]に$ 1を減算することで今見ている区間に要素$ iを$ 1つ削除します
/icons/hr.icon
クエリを1つずつ処理していきます
あるクエリの区間$ [l_i, r_i] を処理したい場合に、現在いる$ [l, r] と場所を比較し、$ 1つずつ適宜移動していきます
最後まで終わったら答えを出力しましょう
code:cpp
for (int ind=0; ind<queries.size(); ++ind) {
if (ind % 2 == 0) {
sort(queriesind.rbegin(), queriesind.rend(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {return get<2>(a) < get<2>(b);});
} else {
sort(queriesind.begin(), queriesind.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {return get<2>(a) < get<2>(b);});
}
while(right <= r){
right++;
}
while(l < left){
left--;
}
while(r + 1 < right){
right--;
delete_(aright, num, len_); }
while(left < l){
delete_(aleft, num, len_); left++;
}
}
}
for(int i = 0; i < q; i++) {
}
code:python
for ind, query in enumerate(queries): # ソートしたクエリを1つずつ見ていく
for i, l, r in sorted(query, reverse=ind%2, key=lambda x: x2): # ind(見ている縦のブロックが偶数のときは降順、奇数の時は昇順に並び替える) # ①
while right <= r:
right += 1
# ②
while l < left:
left -= 1
# ③
while r + 1 < right:
right -= 1
# ④
while left < l:
left += 1
ansi = len_ # num の中に入っている要素数を格納する print(*ans, sep='\n')
/icons/hr.icon
コード全体
code:cpp
using namespace std;
void add(int i, vector<int>& num, int& len_) {
len_++;
}
}
void delete_(int i, vector<int>& num, int& len_) {
len_--;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i=0; i<n; ++i) {
}
int q;
cin >> q;
int block = (int)(sqrt(n)) + 1 ;
vector<vector<tuple<int, int, int>>> queries((int)(sqrt(q)) + 1);
for (int i=0; i<q; i++) {
int l, r;
cin >> l >> r;
l--;
r--;
queriesl / block.push_back(make_tuple(i, l, r)); }
vector<int> ans(q);
int left = 0, right = 0;
vector<int> num(2*1e5 + 10, 0);
int len_ = 0;
for (int ind=0; ind<queries.size(); ++ind) {
if (ind % 2 == 0) {
sort(queriesind.rbegin(), queriesind.rend(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {return get<2>(a) < get<2>(b);});
} else {
sort(queriesind.begin(), queriesind.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {return get<2>(a) < get<2>(b);});
}
while(right <= r){
right++;
}
while(l < left){
left--;
}
while(r + 1 < right){
right--;
delete_(aright, num, len_); }
while(left < l){
delete_(aleft, num, len_); left++;
}
}
}
for(int i=0; i<q; ++i) {
}
return 0;
}
code:python
import sys
input = sys.stdin.readline
def add(i: int) -> None:
global num, len_
len_ += 1
def delete(i: int) -> None:
global num, len_
len_ -= 1
n = int(input())
a = list(map(int, input().split()))
q = int(input())
block = int(n / q ** 0.5) + 1 # ブロックサイズ
queries = [[] for _ in range(int(q**0.5) + 1)] # クエリを受け取る配列
# クエリを受け取る
for i in range(q):
l, r = map(int, input().split())
l -= 1
r -= 1
left, right = 0, 0 # スタート地点は left, right ともに 0
num = 0 * (2*10**5 + 10) # numi := 今見ている区間 left, right に存在する i の個数 len_ = 0 # num に入っている要素数
for ind, query in enumerate(queries): # ソートしたクエリを1つずつ見ていく
for i, l, r in sorted(query, reverse=ind%2, key=lambda x: x2): # ind(見ている縦のブロックが偶数のときは降順、奇数の時は昇順に並び替える) while right <= r:
right += 1
while l < left:
left -= 1
while r + 1 < right:
right -= 1
while left < l:
left += 1
ansi = len_ # num の中に入っている要素数を格納する print(*ans, sep='\n')
/icons/hr.icon
実装上での注意・オススメ
クエリを入れ替えるが最終的には入力順のクエリを持っておく必要があるのでqueriesに格納する際にインデックスも同時に持っておきましょう
基本的にはライブラリを作ると良いです、$ [l, r] の区間縮小・拡大はバグりやすいので一度作成して使い回すと良いです
add関数とdelete関数の中身を書き換えるだけで基本的に Mo's algorithm は使い回すことができます
クエリのブロックごとに昇順・降順にするかしないかで定数倍が変わります、このようにした方が高速なので基本的には交互に実装すると良いです
/icons/hr.icon
類題
※ネタバレ注意
以下は Mo's アルゴリズムで解ける問題です
個人的に、上から順に簡単な問題となっています
1828 diff
初めて Mo's を練習したい方は個人的にはこれがオススメです
1753 diff
1495 diff
Mo's で解けますが、Python だとほぼ確実に TLE しちゃいます...
PAST にも出題があります
数学の知識が若干必要です
codeforces の問題です
面白そうな問題です
黄 diffなのでやりがいがあると思います
※自分は Python だと TLE してしまい、C++ で AC しました（ワンクリックネタバレ注意）
/icons/hr.icon
最後に
可視化のコード
実の所、クエリの可視化に結構な時間を消費しました。可視化にはmatplotlibを使用しましたので、需要があるかわかりませんが一応クエリをランダムに作成から描画までする notebook も提供します。
更なる高速化
Mo's アルゴリズムは計算量的にギリギリの場合があり、定数倍で落ちることもあると思います。
そのような場合にはより高速化する必要があり、本記事では紹介しませんでしたが Nyaan さんの記事 がオススメなので興味のある方は読んでみると良いと思います。 難易度に関して
基本的に Mo's アルゴリズムを使用する問題は水上位〜青上位と比較的レベルが高いですが、１度実装するとかなり楽ですし使い回しが効きます。個人的には気づくのが難しいためここまで diff が上がっているのかなと感じます。
UnionFindのように「実装よくわかんないけどとりあえず使える〜」となれば$ 1,2色下がっても全く不思議じゃないのかなと思います。これを機に初めて知った方はぜひ実装してみてください。
Python で解く Mo's に関して
Python だと C++ よりもかなり遅いので定数倍高速化をしても TLE になってしまうことが多々あります。
個人的には$ N, Qの制約が Mo's の場合$ 2 \times 10^5とかが多いですが、これが$ 5 \times 10^5とかになるとかなり厳しいイメージがあるので両方書ける方、これから競プロを始めようと思っている方は C++ で実装してみるのが良いと思います。
本当の最後に
最後までありがとうございました。このページには書き込みができないので、コメント等ございましたら Twitter の DM にてお願いします。 /icons/hr.icon