Ever since I read this blog, I have been curious to see how other space-filling curves other than Hilbert can be used to reduce the run time. In this blog, we will see how Peano curves can help bring down the run time of Mo's algorithm-based solutions.

Prerequisites: https://codeforces.net/blog/entry/81716

Relation to TSP

In Mo's algorithm, we try to come up with a comparator that can help us sort the queries in such a way that minimizes the total movement of L and R pointers. In other words, if we have $$$Q$$$ queries, each of the form $$$l_i$$$, $$$r_i$$$, then we wish to find such an arrangement of the queries that minimizes the following summation:

$$$S = \displaystyle\sum_{i=1}^{Q-1} |l_i - l_{i+1}| + |r_i - r_{i+1}|$$$.

In the canonical version, we sort the queries using the following comparator:

bool comp(const query& a,const query& b) {
    if (a.bn == b.bn)
        return a.R < b.R;
    return a.bn < b.bn;
}

We compare the block number bn corresponding to $$$l_i$$$ ($$$\text{bn} = l_i/\text{block_size}$$$). If the block size is set to