Mo’s algorithm is a generic idea. It applies to the following class of problems:
Mo的算法是一个通用的想法。它适用于以下类别的问题:
You are given array Arr of length N and Q queries. Each query is represented by two numbers L and R, and it asks you to compute some function Func with subarray Arr[L..R] as its argument.
给定长度为N的数组Arr和Q 个查询。每个查询由两个数字 L 和 R 表示,它要求您计算某个以子数组 Arr[L..R] 作为参数的函数Func 。
For the sake of brevity we will denote Func([L, R]) as the value of Func on subarray Arr[L..R].
为了简洁起见,我们将 Func([L, R]) 表示为子数组 Arr[L..R] 上 Func 的值。
If this sounds too abstract, let’s look at specific example:
如果这听起来太抽象,让我们看一下具体的例子:
There is an integer array Arr of length N and Q queries. For each i, query #i asks you to output the sum of numbers on subarray [Li, Ri], i.e. Arr[Li] + Arr[Li + 1] + … + Arr[Ri].
有一个长度为 N 的整数数组 Arr 和 Q 个查询。对于每个 i,查询 #i 要求您输出子数组 [L, R] 上的数字之和,即 Arr[L] + Arr[L + 1] + … + Arr[R]。
Here we have Func([L, R]) = Arr[L] + Arr[L + 1] + ... + Arr[R].
这里我们有 Func([L, R]) = Arr[L] + Arr[L + 1] + ... + Arr[R]。
This does not sound so scary, does it? You’ve probably heard of solutions to this problem using Segment Trees or Binary Indexed Trees, or even prefix sums.
这听起来并不那么可怕,不是吗?您可能听说过使用线段树或二叉索引树,甚至前缀和来解决此问题。
Mo’s algorithm provides a way to answer all queries in O((N + Q) * sqrt(N) * F) time with at least O(Q) additional memory. Meaning of F is explained below.
Mo 的算法提供了一种在 O((N + Q) * sqrt(N) * F) 时间内回答所有查询的方法,并且至少需要 O(Q) 额外内存。 F的含义解释如下。
The algorithm is applicable if all following conditions are met:
如果满足以下所有条件,则该算法适用:
Due to constraints on array immutability and queries being known, Mo’s algorithm is inapplicable most of the time. Thus, knowing the method can help you on rare occasions. But. Due to property #3, the algorithm can solve problems that are unsolvable otherwise. If the problem was meant to be solved using Mo’s algorithm, then you can be 90% sure that it can not be accepted without knowing it. Since the approach is not well-known, in situations where technique is appropriate, you will easily overcome majority of competitors.
由于数组不变性和查询已知的限制,Mo 的算法大多数时候不适用。因此,了解该方法在极少数情况下可以为您提供帮助。但。由于属性#3,该算法可以解决其他方式无法解决的问题。如果问题是要使用Mo的算法来解决,那么你可以90%确定它在不知情的情况下无法被接受。由于该方法并不为人所知,因此在技术合适的情况下,您将轻松克服大多数竞争对手。
We have Q queries to answer. Suppose we answer them in order they are asked in the following manner:
我们有 Q 个问题需要解答。假设我们按照以下方式回答问题:
for i = 0..Q-1:
L, R = query #i
for j = L..R:
do some work to compute Func([L, R])
This can take Ω(N * Q) time. If N and Q are of order 105, then this would lead to time limit exceeded.
这可能需要 Ω(N * Q) 时间。如果N和Q的数量级为10 5 ,那么这将导致超出时间限制。
But what if we answer queries in different order? Can we do better then?
但是如果我们以不同的顺序回答查询怎么办?那我们能做得更好吗?
Definition #1: 定义#1:
Segment [L, R] is a continuous subarray Arr[L..R], i.e. array formed by elements Arr[L], Arr[L + 1], …, Arr[R]. We call L left endpoint and R right endpoint of segment [L, R]. We say that index i belongs to segment [L, R] if L ≤ i ≤ R.
段[L, R]是一个连续子数组Arr[L..R],即由元素Arr[L]、Arr[L + 1]、…、Arr[R]组成的数组。我们称线段[L,R]的L为左端点,R为右端点。如果 L ≤ i ≤ R,则我们说索引 i 属于段 [L, R]。
Notation 符号
We will describe Mo’s algorithm, and then prove its running time.
我们将描述Mo的算法,然后证明其运行时间。
The approach works as follows:
该方法的工作原理如下:
Let’s view Arr as a union of disjoint segments of size BLOCK_SIZE, which we will call “blocks”. Take a look at the picture for better understanding:
让我们将 Arr 视为大小为 BLOCK_SIZE 的不相交段的并集,我们将其称为“块”。看一下图片以便更好地理解:
Let K be the index of last block. Then there are K + 1 blocks, because we number them from zero. Notice than K’th block can have less than BLOCK_SIZE elements.
令 K 为最后一个块的索引。然后有 K + 1 个块,因为我们从零开始编号。请注意,第 K 个块的元素可以少于 BLOCK_SIZE。
Proposition #1: 提案#1:
K = O(sqrt(N)). K = O(sqrt(N))。
Proof: 证明:
If sqrt(N) * sqrt(N) = N (which may be false due to our definition of sqrt(N)), then K = sqrt(N) - 1, because we have K + 1 blocks, each of size sqrt(N). Otherwise, K = sqrt(N), because we need one additional block to store N - sqrt(N) * sqrt(N) elements.
如果 sqrt(N) * sqrt(N) = N(由于我们对 sqrt(N) 的定义,这可能是错误的),则 K = sqrt(N) - 1,因为我们有 K + 1 个块,每个块的大小为 sqrt (N)。否则,K = sqrt(N),因为我们需要一个额外的块来存储 N - sqrt(N) * sqrt(N) 个元素。
UPD 19 june 2017: As pointed out in the comments, this does not hold for small values of N. Alternative proof (less intuitive, more formal): we need the smallest K such that K * sqrt(N) ≥ N - when this is true, our space is sufficient to hold all N elements. If we divide by sqrt(N), we get K ≥ N / sqrt(N). sqrt(N) is either real_sqrt(N) (the one without truncating value after decimal point) or real_sqrt(N) - 1. So K ≥ N / (real_sqrt(N) - 1).
UPD 2017 年 6 月 19 日:正如评论中所指出的,这不适用于 N 的小值。替代证明(不太直观,更正式):我们需要最小的 K 使得 K * sqrt(N) ≥ N - 当这个是的,我们的空间足以容纳所有 N 个元素。如果除以 sqrt(N),我们会得到 K ≥ N / sqrt(N)。 sqrt(N) 是 real_sqrt(N) (小数点后不截断值的那个)或 real_sqrt(N) - 1。因此 K ≥ N / (real_sqrt(N) - 1)。
So, K = N / (real_sqrt(N) - 1) + 1 suffices. Let's look at the difference between this value and real_sqrt(N). Denote this difference as x: N / (real_sqrt(N) - 1) + 1 - real_sqrt(N) ≥ x. Put everything under common denominator: (N + real_sqrt(N) - 1 - N + real_sqrt(N)) / (real_sqrt(N) - 1) ≥ x. This means that (2 * real_sqrt(N) - 1) / (real_sqrt(N) - 1) ≥ x. As N approaches infinity, the bound on the right approaches 2. So, for very large N, x ≤ 2. Otherwise, it is bounded by a constant (you can find it, for example, by taking the first 1000 values of N and taking maximum value of the bound). So K - real_sqrt(N) ≤ constant, which implies K = O(sqrt(N)).
因此,K = N / (real_sqrt(N) - 1) + 1 就足够了。我们来看看这个值和real_sqrt(N)的区别。将此差异表示为 x:N / (real_sqrt(N) - 1) + 1 - real_sqrt(N) ≥ x。将所有内容放在公分母下:(N + real_sqrt(N) - 1 - N + real_sqrt(N)) / (real_sqrt(N) - 1) ≥ x。这意味着 (2 * real_sqrt(N) - 1) / (real_sqrt(N) - 1) ≥ x。当 N 接近无穷大时,右侧的界限接近 2。因此,对于非常大的 N,x ≤ 2。否则,它的界限是一个常数(例如,您可以通过取 N 的前 1000 个值和取边界的最大值)。所以 K - real_sqrt(N) ≤ 常量,这意味着 K = O(sqrt(N))。
Proposition #2: 提案#2:
Block #r is a segment [r * BLOCK_SIZE, min(N - 1, (r + 1) * BLOCK_SIZE - 1)].
块 #r 是一个段 [r * BLOCK_SIZE, min(N - 1, (r + 1) * BLOCK_SIZE - 1)]。
Proof (by induction): 证明(通过归纳法):
For block #0 statement is true — it is a segment [0, BLOCK_SIZE - 1], containing BLOCK_SIZE elements.
For block #0 语句为 true — 它是一个段 [0, BLOCK_SIZE - 1],包含 BLOCK_SIZE 元素。
Suppose first T ≤ K blocks satisfy the above statement. Then the last of those blocks is a segment [(T - 1) * BLOCK_SIZE, T * BLOCK_SIZE - 1].
假设前 T ≤ K 块满足上述语句。那么最后一个块是一个段 [(T - 1) * BLOCK_SIZE, T * BLOCK_SIZE - 1]。
Then we form the next, T+1’th block. First element of this block will have array index T * BLOCK_SIZE. We have at most BLOCK_SIZE elements to add to block (there may be less if T + 1 = K + 1). So the last index in T+1’th block will be min(N - 1, (T + 1) * BLOCK_SIZE - 1).
然后我们形成下一个,第 T+1 个区块。该块的第一个元素将具有数组索引 T * BLOCK_SIZE。我们最多有 BLOCK_SIZE 个元素要添加到块中(如果 T + 1 = K + 1,则可能会更少)。因此第 T+1 个块中的最后一个索引将为 min(N - 1, (T + 1) * BLOCK_SIZE - 1)。
Corollary #1:
Two indices i and j belong to same block #r if and only if i⁄BLOCK_SIZE = j⁄BLOCK_SIZE = r.
推论 #1:当且仅当 ⁄ BLOCK_SIZE = ⁄ BLOCK_SIZE = r 时,两个索引 i 和 j 属于同一块 #r。
Definition #2: 定义#2:
Qr = { query [L, R] | L⁄BLOCK_SIZE = r }. Informally, Qr is a set of queries from input, whose left endpoints belong to block #r. Notice that this set may be empty. We denote the size of Qr as |Qr|.
Q r = { 查询 [L, R] | L ⁄ BLOCK_SIZE = r }。非正式地,Q r是来自输入的一组查询,其左端点属于块#r。请注意,该集合可能是空的。我们将 Q r的大小表示为 |Q r |。
Proposition #3: 提案#3:
For each r, queries from Qr lie continuously in Mo’s order and they appear in it in non-decreasing order of right endpoints.
对于每个 r,来自 Q r的查询连续地位于 Mo 的顺序中,并且它们以右端点的非递减顺序出现在其中。
Queries from Qr come earlier than queries from Qr + 1 for every r = 0..K-1.
对于每个 r = 0..K-1,来自 Q r的查询早于来自 Q r + 1的查询。
Proof follows from definition of Mo’s order.
证明来自莫阶的定义。
Corollary #2:
When we are processing queries following Mo’s order, we firstly process all queries from Q0, then all queries from Q1, and so on, up to QK.
推论 #2:当我们按照 Mo 的顺序处理查询时,我们首先处理来自 Q 0的所有查询,然后处理来自 Q 1 的所有查询,依此类推,直到 Q K 。
Mo_right changes its value O(N * sqrt(N)) times throughout the run of Mo’s algorithm.
Mo_right 在 Mo 算法的运行过程中更改其值 O(N * sqrt(N)) 次。
Proof: 证明:
There are no more cases when mo_right changes. Overall, we have O(N * sqrt(N)) + O(N * sqrt(N)) = O(N * sqrt(N)) changes of mo_right.
mo_right 发生变化的情况不再发生。总的来说,我们对 mo_right 进行了 O(N * sqrt(N)) + O(N * sqrt(N)) = O(N * sqrt(N)) 更改。
Corollary #3:
All mo_right changes combined take O(N * sqrt(N) * F) time (because each change is done in O(F) time).
推论 #3:所有 mo_right 更改组合起来需要 O(N * sqrt(N) * F) 时间(因为每个更改都是在 O(F) 时间内完成的)。
Mo_left changes its value O(Q * sqrt(N)) times throughout the run of Mo’s algorithm.
Mo_left 在 Mo 算法的运行过程中改变其值 O(Q * sqrt(N)) 次。
Proof: 证明:
There are no more cases when mo_left changes. Overall, we have
O(sqrt(N) * Q) + O(N) = O(sqrt(N) * Q) changes of mo_left.
mo_left 发生变化的情况不再发生。总的来说,我们有 O(sqrt(N) * Q) + O(N) = O(sqrt(N) * Q) 的 mo_left 变化。
Corollary #4:
All mo_left changes combined take O(Q * sqrt(N) * F) time (because each change is done in O(F) time).
推论 #4:所有 mo_left 更改组合起来需要 O(Q * sqrt(N) * F) 时间(因为每个更改都是在 O(F) 时间内完成的)。
Corollary #5:
Time complexity of Mo’s algorithm is O((N + Q) * sqrt(N) * F).
推论 #5: Mo 算法的时间复杂度为 O((N + Q) * sqrt(N) * F)。
Let’s look at an example problem (idea taken from here):
让我们看一个示例问题(想法取自此处):
You have an array Arr of N numbers ranging from 0 to 99. Also you have Q queries [L, R]. For each such query you must print
您有一个由 N 个数字组成的数组 Arr,范围从 0 到 99。此外您还有 Q 查询 [L, R]。对于每个此类查询,您必须打印
V([L, R]) = ∑i=0..99 count(i)2 * i
V([L, R]) = Σ i=0..99计数(i) 2 * i
where count(i) is the number of times i occurs in Arr[L..R].
其中 count(i) 是 i 出现的次数 到达[L..R]。
Constraints are N ≤ 105, Q ≤ 105.
约束条件为 N ≤ 10 5 、Q ≤ 10 5 。
To apply Mo’s algorithm, you must ensure of three properties:
要应用 Mo 算法,必须确保三个属性:
First two properties obviously hold. The third property depends on the time bound — O(F).
Surely, we can compute V([L + 1, R]) from scratch in Ω(R - L) = Ω(N) in the worst case. But looking at complexity of Mo’s algorithm, you can deduce that this will surely time out, because we multiply O(F) with O((Q + N) * sqrt(N)).
Typically, you want O(F) to be O(1) or O(log(n)). Choosing a way to achieve appropriate time bound O(F) is programmer’s main concern when solving problems using Mo’s algorithm.
I will describe a way to achieve O(F) = O(1) for this problem.
Let’s maintain variable current_answer (initialized by zero) to store V([mo_left, mo_right]) and integer array cnt of size 100, where cnt[x] will be the number of times x occurs in [mo_left, mo_right].
From the definition of current_answer we can see that
current answer = V([mo_left, mo_right]) =∑i=0..99 count'(i)2 * i
where count’(x) is the number of times x occurs in [mo_left, mo_right].
By the definition of cnt we see that count’(x) = cnt[x], so
current answer = ∑i=0..99 cnt[i]2 * i.
Suppose we want to change mo_right to mo_right + 1. It means we want to add number p = Arr[mo_right + 1] into consideration. But we also want to retain current_answer and cnt’s properties.
Maintaining cnt is easy: just increase cnt[p] by 1. It is a bit trickier to deal with current_answer.
We know (from the definitions) that current_answer contains summand cnt[p]2 * p before addition. Let’s subtract this value from the answer. Then, after we perform addition to cnt, add again cnt[p]2 * p to the answer (make no mistake: this time it will contain updated value of cnt[p]). Both updates take O(1) time.
All other transitions (mo_left to mo_left + 1, mo_left to mo_left - 1 and mo_right to mo_right - 1) can be done in the same way, so we have O(F) = O(1). You can refer to the code below for clarity.
Now let’s look into detail on one sample test case:
Input:
Arr = [0, 1, 1, 0, 2, 3, 4, 1, 3, 5, 1, 5, 3, 5, 4, 0, 2, 2] of 18 elements
Queries (0-indexed): [0, 8], [2, 5], [2, 11], [16, 17], [13, 14], [1, 17], [17, 17]
The algorithm works as follows:
Firstly, set BLOCK_SIZE = sqrt(18) = 4. Notice that we have 5 blocks: [0, 3], [4, 7], [8, 11], [12, 15], [16, 17]. The last block contains less than BLOCK_SIZE elements.
Then, set mo_left = 0, mo_right = -1, current_answer = 0, cnt = [0, 0, 0, 0, 0, 0] (I will use only first 6 elements out of 100 for the sake of simplicity).
Then sort queries. The Mo’s order will be:
[2,5], [0, 8], [2, 11], [1, 17] (here ends Q0) [13, 14] (here ends Q3) [16, 17], [17, 17] (here ends Q4).
Now, when everything is set up, we can answer queries:
Now the important part comes: we must output answers not in order we’ve achieved them, but in order they were asked.
Output:
27
6
47
8
9
122
2
Here is the C++ implementation for the above problem:
#include <bits/stdc++.h>
using namespace std;
int N, Q;
// Variables, that hold current "state" of computation
long long current_answer;
long long cnt[100];
// Array to store answers (because the order we achieve them is messed up)
long long answers[100500];
int BLOCK_SIZE;
int arr[100500];
// We will represent each query as three numbers: L, R, idx. Idx is
// the position (in original order) of this query.
pair< pair<int, int>, int> queries[100500];
// Essential part of Mo's algorithm: comparator, which we will
// use with std::sort. It is a function, which must return True
// if query x must come earlier than query y, and False otherwise.
inline bool mo_cmp(const pair< pair<int, int>, int> &x,
const pair< pair<int, int>, int> &y)
{
int block_x = x.first.first / BLOCK_SIZE;
int block_y = y.first.first / BLOCK_SIZE;
if(block_x != block_y)
return block_x < block_y;
return x.first.second < y.first.second;
}
// When adding a number, we first nullify it's effect on current
// answer, then update cnt array, then account for it's effect again.
inline void add(int x)
{
current_answer -= cnt[x] * cnt[x] * x;
cnt[x]++;
current_answer += cnt[x] * cnt[x] * x;
}
// Removing is much like adding.
inline void remove(int x)
{
current_answer -= cnt[x] * cnt[x] * x;
cnt[x]--;
current_answer += cnt[x] * cnt[x] * x;
}
int main()
{
cin.sync_with_stdio(false);
cin >> N >> Q;
BLOCK_SIZE = static_cast<int>(sqrt(N));
// Read input array
for(int i = 0; i < N; i++)
cin >> arr[i];
// Read input queries, which are 0-indexed. Store each query's
// original position. We will use it when printing answer.
for(int i = 0; i < Q; i++) {
cin >> queries[i].first.first >> queries[i].first.second;
queries[i].second = i;
}
// Sort queries using Mo's special comparator we defined.
sort(queries, queries + Q, mo_cmp);
// Set up current segment [mo_left, mo_right].
int mo_left = 0, mo_right = -1;
for(int i = 0; i < Q; i++) {
// [left, right] is what query we must answer now.
int left = queries[i].first.first;
int right = queries[i].first.second;
// Usual part of applying Mo's algorithm: moving mo_left
// and mo_right.
while(mo_right < right) {
mo_right++;
add(arr[mo_right]);
}
while(mo_right > right) {
remove(arr[mo_right]);
mo_right--;
}
while(mo_left < left) {
remove(arr[mo_left]);
mo_left++;
}
while(mo_left > left) {
mo_left--;
add(arr[mo_left]);
}
// Store the answer into required position.
answers[queries[i].second] = current_answer;
}
// We output answers *after* we process all queries.
for(int i = 0; i < Q; i++)
cout << answers[i] << "\n";
return 0;
}
Same solution without global variables (the way I like to implement it):
#include <bits/stdc++.h>
using std::vector;
using std::tuple;
/*
* Take out adding\removing logic into separate class.
* It provides functions to add and remove numbers from
* our structure, while maintaining cnt[] and current_answer.
*
*/
struct Mo
{
static constexpr int MAX_VALUE = 1005000;
vector<long long> cnt;
long long current_answer;
void process(int number, int delta)
{
current_answer -= cnt[number] * cnt[number] * number;
cnt[number] += delta;
current_answer += cnt[number] * cnt[number] * number;
}
public:
Mo()
{
cnt = vector<long long>(MAX_VALUE, 0);
current_answer = 0;
}
long long get_answer() const
{
return current_answer;
}
void add(int number)
{
process(number, 1);
}
void remove(int number)
{
process(number, -1);
}
};
int main()
{
int N, Q, BLOCK_SIZE;
std::cin.sync_with_stdio(false);
std::cin >> N >> Q;
BLOCK_SIZE = static_cast<int>(sqrt(N));
// No global variables, everything inside.
vector<int> arr(N);
vector<long long> answers(Q);
vector< tuple<int, int, int> > queries;
queries.reserve(Q);
for(int i = 0; i < N; i++)
std::cin >> arr[i];
for(int i = 0; i < Q; i++) {
int le, rg;
std::cin >> le >> rg;
queries.emplace_back(le, rg, i);
}
// Comparator as a lambda-function, which catches BLOCK_SIZE
// from the above definition.
auto mo_cmp = [BLOCK_SIZE](const tuple<int, int, int> &x,
const tuple<int, int, int> &y) -> bool {
int block_x = std::get<0>(x) / BLOCK_SIZE;
int block_y = std::get<0>(y) / BLOCK_SIZE;
if(block_x != block_y)
return block_x < block_y;
return std::get<1>(x) < std::get<1>(y);
};
std::sort(queries.begin(), queries.end(), mo_cmp);
Mo solver;
int mo_left = 0, mo_right = -1;
// Usual Mo's algorithm stuff.
for(const auto &q: queries) {
int left, right, answer_idx;
std::tie(left, right, answer_idx) = q;
while(mo_right < right) {
mo_right++;
solver.add(arr[mo_right]);
}
while(mo_right > right) {
solver.remove(arr[mo_right]);
mo_right--;
}
while(mo_left < left) {
solver.remove(arr[mo_left]);
mo_left++;
}
while(mo_left > left) {
mo_left--;
solver.add(arr[mo_left]);
}
answers[answer_idx] = solver.get_answer();
}
for(int i = 0; i < Q; i++)
std::cout << answers[i] << "\n";
return 0;
}
In case you want to try out implementing Mo’s technique for yourself, check out these problems: