mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

Mo's Algorithm
(data_structure/mo.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "data_structure/mo.hpp"

Mo’s Algorithm

使い方

• $N$ を要素数
• $B$ をクエリ中の $L$ を分割するブロックの幅とする

とする（実装の詳細は具体的な実装例を見た方が早い）。

• Mo(pair<int, int> query) : コンストラクタ。クエリの情報を与える（クエリは 0-indexed）。
• void calc(auto &add, auto &erase, &f, int n=-1, int B=-1) : すべてのクエリに対する答えを計算する。
  • add は区間を $1$ 増やす操作を行う関数
  • erase は区間を $1$ 減らす操作を行う関数
  • 操作後に、その区間の解が求まっている状態にする必要がある。
  • f は区間が一致したクエリに対する答えを格納する。答えの情報は外部に保存されるように実装する。
  • 解を求めるための操作は、外の変数や配列を見て行えるようにする必要がある。
  • $N$, $B$ は要素数およびブロック数
• void calc(auto &add_left, &add_right, &erase_left, &erase_right, auto &erase, &f, int n=-1, int B=-1) : すべてのクエリに対する答えを計算する。
  • add_left, add_right は区間を $1$ 増やす操作を行う関数
  • erase_left, erase_right は区間を $1$ 減らす操作を行う関数
  • 操作後に、その区間の解が求まっている状態にする必要がある。
  • f は区間が一致したクエリに対する答えを格納する。答えの情報は外部に保存されるように実装する。
  • 解を求めるための操作は、外の変数や配列を見て行えるようにする必要がある。
  • $N$, $B$ は要素数およびブロック数

計算量は、区間を $1$ 変更する操作を $O(1)$ としたとき、 $O(QB+\frac{N^2}{B})$

特に $B = \frac{N}{\sqrt{Q}}$ の時、 $O(N\sqrt{Q})$

Verified with

• verify/yosupo/static_range_frequency.test.cpp

Code

#pragma once

#include<algorithm>
#include<cmath>
#include<numeric>
#include<ranges>
#include<utility>
#include<vector>

class Mo {
	std::vector<std::pair<int, int>> lr;
public:
	Mo() = default;
	Mo(const std::vector<std::pair<int, int>> &_lr) : lr(_lr) {}

	template<typename AL, typename AR, typename EL, typename ER, typename F>
	void calc(const AL &add_left, const AR &add_right, const EL &erase_left, const ER& erase_right, const F &f, int _n = -1, int _B = -1){
		int n = (_n == -1 ? std::ranges::max(lr, {}, &std::pair<int, int>::second).second : _n);
		int q = (int)lr.size();
		int B = (_B == -1 ? std::max(1, n/int(sqrt(q))) : _B);

		std::vector<int> index(q);
		std::iota(index.begin(), index.end(), 0);
		std::sort(index.begin(), index.end(), [&](int i, int j){
			const auto &[l_i, r_i] = lr[i];
			const auto &[l_j, r_j] = lr[j];
			const int B_i = l_i / B, B_j = l_j / B;
			if(B_i != B_j){
				return B_i < B_j;
			}
			if(B_i & 1){
				return r_j < r_i;
			}else{
				return r_i < r_j;
			}
		});

		int l = 0, r = 0;
		for(int idx : index){
			const auto &[L, R] = lr[idx];

			while(L < l)add_left(--l);
			while(r < R)add_right(r++);
			
			while(l < L)erase_left(l++);
			while(R < r)erase_right(--r);

			f(idx);
		}
	}

	template<typename A, typename E, typename F>
	void calc(const A &add, const E &erase, const F &f){
		calc(add, add, erase, erase, f);
	}
};

#line 2 "data_structure/mo.hpp"

#include<algorithm>
#include<cmath>
#include<numeric>
#include<ranges>
#include<utility>
#include<vector>

class Mo {
	std::vector<std::pair<int, int>> lr;
public:
	Mo() = default;
	Mo(const std::vector<std::pair<int, int>> &_lr) : lr(_lr) {}

	template<typename AL, typename AR, typename EL, typename ER, typename F>
	void calc(const AL &add_left, const AR &add_right, const EL &erase_left, const ER& erase_right, const F &f, int _n = -1, int _B = -1){
		int n = (_n == -1 ? std::ranges::max(lr, {}, &std::pair<int, int>::second).second : _n);
		int q = (int)lr.size();
		int B = (_B == -1 ? std::max(1, n/int(sqrt(q))) : _B);

		std::vector<int> index(q);
		std::iota(index.begin(), index.end(), 0);
		std::sort(index.begin(), index.end(), [&](int i, int j){
			const auto &[l_i, r_i] = lr[i];
			const auto &[l_j, r_j] = lr[j];
			const int B_i = l_i / B, B_j = l_j / B;
			if(B_i != B_j){
				return B_i < B_j;
			}
			if(B_i & 1){
				return r_j < r_i;
			}else{
				return r_i < r_j;
			}
		});

		int l = 0, r = 0;
		for(int idx : index){
			const auto &[L, R] = lr[idx];

			while(L < l)add_left(--l);
			while(r < R)add_right(r++);
			
			while(l < L)erase_left(l++);
			while(R < r)erase_right(--r);

			f(idx);
		}
	}

	template<typename A, typename E, typename F>
	void calc(const A &add, const E &erase, const F &f){
		calc(add, add, erase, erase, f);
	}
};

Back to top page