Proof of Mo's Algo

Problems and Contests
#1

according to this cf blog, you just have to sort the queries using the comparator below.

S = the max integer number which is less than sqrt(N);
bool cmp(Query A, Query B)
{
  if (A.l / S ！= B.l / S) return A.l / S < B.l / S;
  return A.r > B.r
}

then processing queries takes a total of \mathcal O(Q\sqrt N) for distinct value queries.

what’s so significant about the sorting function and why does sorting it result in a \sqrt N complexity?

#2

The important part is that it’s grouping the queries up by [left/S, right/S], where the division is rounding down. Count the number of insertions/deletions required to move between groups/queries. Then there are up to O(sqrt(n)^2) = O(n) groups of queries, each group takes O(sqrt(n)) time to move to the next group and each query takes O(sqrt(n)) time, so you have O((n+q)sqrt(n)).

Sorting with this comparator is more convenient to code than actually grouping them up.

1 Like
#3

Thanks! I understand it now.