An alternative comparator for Mo's algorithm

Правка en1, от gepardo, 2018-08-14 12:23:55

Hello, Codeforces!

I think many of Codeforces users know about Mo's algorithm. For those, who don't know, please read this blog.

Canonical version of the algorithm

The canonical implementation of this algorithm gives time complexity if insertions and deletions work in O(1).

Usually, the two comparators for query sorting are used. The slowest one:

struct Query {
	int l, r, idx;
	
	inline pair<int, int> toPair() const {
		return make_pair(l / block, r);
	}
};

inline bool operator<(const Query &a, const Query &b) {
	return a.toPair() < b.toPair();
}

We know it can be optimized a little if for even blocks we use the reverse order for the right boundary:

struct Query {
	int l, r, idx;
	
	inline pair<int, int> toPair() const {
		return make_pair(l / block, ((l / block) & 1) ? -r : +r);
	}
};

inline bool operator<(const Query &a, const Query &b) {
	return a.toPair() < b.toPair();
}

Achieving a better time complexity

We can achieve complexity for Mo's algorithm (still assuming that insertions and deletions are O(1). Note that is always better than . We can prove it as follows:

The last statement is always true, so the statement above is proved.

But how this complexity can be achieved?

Relation to TSP

At first, notice that number of operations to change the segment (l1;r1) to (l2;r2) will take |l1 - l2| + |r1 - r2| insertions and deletions.

Denote the queries as (l1;r1), (l2;r2), ..., (lq;rq). We need to permute them to minimize the number of operations, i. e. to find a permutation p1, p2, ... pq such that total number of operations

is minimal possible.

Now we can see the relationship between Mo's algorithm and TSP on Manhattan metrics. Boundaries of queries can be represented as points on 2D plane. And we need to find an optimal route to visit all these points (process all the queries).

But TSP is NP-complete, so it cannot help us to find the optimal query sorting order. Instead, we should use a fast heuristic approach. A good approach would be the use of recursive curves. Wikipedia says about using Sierpiński curve as a basis to find a good TSP solution.

But Sierpiński curve is not very convenient in implementation for integer point coordinates, so we will use another recursive curve: Hilbert curve.

Hilbert curve

Let's build a Hilbert curve on a 2n × 2n matrix and pass all the cells on matrix according to this curve. Denote ord(i, j) as the number of cells visited before the cell (i;j) in order of Hilbert curve. The following picture shows ord(i, j) for each cell on 8 × 8 matrix:

![](https://i.imgur.com/Cuw8guP.png)

Теги mo, mos algorithm, sqrt, sqrt decomposition, hilbert, recursion, recursive curves

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en14 Английский gepardo 2020-11-19 20:39:38 1 Tiny change: 'q)\sqrt{n}$. We can ' -> 'q)\sqrt{n})$. We can '
en13 Английский gepardo 2018-09-20 18:30:53 77 Fix proof
en12 Английский gepardo 2018-08-29 06:22:05 22 Bugfix in codes (use [L-1; R] segements instead of [L; R], as required in the problem)
en11 Английский gepardo 2018-08-14 17:49:49 63 Added [cut]
en10 Английский gepardo 2018-08-14 15:52:52 4 Fixed bugs, thanks Vovuh
en9 Английский gepardo 2018-08-14 14:51:38 98 Adding notice about comments
en8 Английский gepardo 2018-08-14 14:46:41 25 Release to the world! (published)
en7 Английский gepardo 2018-08-14 14:44:03 140 Many-many-fixes
en6 Английский gepardo 2018-08-14 14:27:08 90 Fix the proof
en5 Английский gepardo 2018-08-14 14:24:32 2 Tiny change: ' $n = 10^6 and q = 10^4$.' -> ' $n = 10^6$ and $q = 10^4$.'
en4 Английский gepardo 2018-08-14 14:22:57 690 More benchmarks added
en3 Английский gepardo 2018-08-14 14:00:05 457 Added table of contents
en2 Английский gepardo 2018-08-14 13:49:27 5448 The second part of the text is written
en1 Английский gepardo 2018-08-14 12:23:55 3242 Initial revision (saved to drafts)