mo (Mo's Algorithm)
(src/algorithm/mo.hpp)

• View this file on GitHub
• Last update: 2023-03-30 00:09:49+09:00
• Include: #include "src/algorithm/mo.hpp"

概要

静的な列 $A$ 上で区間 $[l, r)$ 上のなにかを聞くクエリが沢山飛んでくる状況で、クエリの順番をいい感じに並び替えることで愚直より計算量を改善するテクニック

区間 $[a, b)$ でのクエリの解がわかっている状況で $[a - 1, b)$ $[a + 1, b)$ $[a, b - 1)$ $[a, b + 1)$ のクエリの解が $O(f)$ で求まる時、 $Q$ 個のクエリを全体で $O(fN\sqrt{Q})$ で処理できるようになる。

機能

mo

std::vector<std::tuple<int, int, int>> mo(int N, const std::vector<std::pair<int, int>>& Q)

クエリの順番を並び替えて、元のindexを記憶した状態で提供する

N は数列の長さ。

引数の Q はfirstに $l$ 、 second に $r$ を保管した std::pair<int, int>のstd::vectorである。0-indexedの半開区間で取り扱うことに注意

返り値は l, r, indexの順番に保管された std::vector<std::tuple<int, int, int>>である。この順番にクエリを処理すれば良い。

メモ

例えば以下の疑似コードの様に利用する

L = 0, R = 0
ans = [0, 0)でのクエリの解
for ([l, r, index] : zawa::mo(Query)):
	while (R < r) (1)
		ansを[L, R)解から[L, R + 1)解に変更する
		R <- R + 1
	while (L > l) (2)
		ansを[L, R)解から[L - 1, R)解に変更する
		L <- L - 1
	while (R > r) (3)
		ansを[L, R)解から[L, R - 1)解に変更する
		R <- R - 1
	while (L < l) (4)
		ansを[L, R)解から[L + 1, R)解に変更する
		L <- L + 1
	index番目のクエリの解答がansに格納されている

詳しい実装例はverifyのコードを見ること。mo.test.cppはRSQを処理しているため、例にちょうどよい

参考

• Mo’s Algorithmを理解する
• Mo’s algorithm

Verified with

• test/ABC174-F.test.cpp
• test/ABC242-G.test.cpp
• test/mo.test.cpp

Code

#pragma once

#include <vector>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cmath>

namespace zawa {

std::vector<std::tuple<int, int, int>> mo(int N, const std::vector<std::pair<int, int>>& Q) {
	int sq = std::sqrt(Q.size() + 1);
	std::vector tmp((N + sq - 1) / sq, std::vector(0, std::tuple(0, 0, 0)));
	for (int i = 0 ; i < (int)Q.size() ; i++)
		tmp[Q[i].first / sq].emplace_back(Q[i].second, Q[i].first, i);
	std::vector res(0, std::tuple(0, 0, 0));
	for (int i = 0 ; i < (int)tmp.size() ; i++) {
		std::sort(tmp[i].begin(), tmp[i].end());
		if (i & 1) std::reverse(tmp[i].begin(), tmp[i].end());
		for (const auto& [r, l, index] : tmp[i]) res.emplace_back(l, r, index);
	}
	return res;
}

}// namespace zawa

#line 2 "src/algorithm/mo.hpp"

#include <vector>
#include <utility>
#include <tuple>
#include <algorithm>
#include <cmath>

namespace zawa {

std::vector<std::tuple<int, int, int>> mo(int N, const std::vector<std::pair<int, int>>& Q) {
	int sq = std::sqrt(Q.size() + 1);
	std::vector tmp((N + sq - 1) / sq, std::vector(0, std::tuple(0, 0, 0)));
	for (int i = 0 ; i < (int)Q.size() ; i++)
		tmp[Q[i].first / sq].emplace_back(Q[i].second, Q[i].first, i);
	std::vector res(0, std::tuple(0, 0, 0));
	for (int i = 0 ; i < (int)tmp.size() ; i++) {
		std::sort(tmp[i].begin(), tmp[i].end());
		if (i & 1) std::reverse(tmp[i].begin(), tmp[i].end());
		for (const auto& [r, l, index] : tmp[i]) res.emplace_back(l, r, index);
	}
	return res;
}

}// namespace zawa

Back to top page