Mo's Algorithm

Mo’s algorithm answers offline interval queries by reordering them so a maintained active interval moves only a controlled total distance. It is useful when adding or removing one endpoint is easy but merging two precomputed range summaries is awkward. This lesson counts distinct values in static array ranges. The result for a range does not depend on query order, so sorting queries is safe; output IDs restore the user’s original order.

Prerequisites: Arrays; sorting; frequency arrays; offline processing. Difficulty: Advanced.

Build the idea

1. 1. Design add and remove first

   frequency[x] counts occurrences of compressed value x inside the active interval. distinct counts values with positive frequency. Adding an occurrence increases distinct only when its old count was zero. Removing decreases distinct only when the new count becomes zero. These symmetric operations support moving either endpoint. Without efficient reversible updates, Mo’s ordering alone does not help.

2. 2. Compress arbitrary values

   Sort a copy of array values, remove duplicates, and replace each value by its index in that unique list. Equality is preserved, which is all distinct-count queries need. Compression allows frequency to be a dense O(n) array even when original values are negative or near 10^9. It does not preserve arithmetic differences, so other statistics may require retaining original values too.

3. 3. Order queries by blocks

   Split possible left endpoints into blocks of B≈√n. Sort first by left block and then by right endpoint, reversing right order in odd blocks to reduce backtracking. Within a block, right moves monotonically over at most n positions. Left moves at most O(B) per query within its block; movements between blocks add manageable linear work. This is an ordering of queries, not a change to the array.

4. 4. Trace moving intervals

   For [1,2,1,3,2], queries [1,3], [2,5], [4,5] have answers 2,3,2. Moving from [1,3] to [2,5], first add positions 4 and 5: frequencies become {1:2,2:2,3:1}. Remove position 1: value 1 still occurs once, so distinct remains 3. Moving to [4,5] removes positions 2 and 3; value 1 disappears and the remaining values are {3,2}. Expand before shrinking so remove never touches a position outside the active interval.

5. 5. Know the supported query model

   This version assumes a static array, all queries known in advance, and O(1) endpoint add/remove. It does not support arbitrary online queries, point updates interleaved in time, or statistics depending on the order queries arrive. Mo with modifications is a different extension. For ordinary sums or minima, prefix sums or segment trees are simpler and generally faster; the distinctive benefit here is maintaining nontrivially mergeable frequency information.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
struct Query{
    int l,r,id;
};
int main(){
    int n,q;
    if(!(cin>>n>>q)){
        return 0;
    }
    vector<int>a(n+1),values;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        values.push_back(a[i]);
    }
    sort(values.begin(),values.end());
    values.erase(unique(values.begin(),values.end()),values.end());
    for(int i=1;i<=n;++i){
        a[i]=lower_bound(values.begin(),values.end(),a[i])-values.begin();
    }
    vector<Query>queries(q);
    for(int i=0;i<q;++i){
        cin>>queries[i].l>>queries[i].r;
        queries[i].id=i;
    }
    int B=max(1,(int)sqrt(n));
    sort(queries.begin(),queries.end(),[&](const Query&a,const Query&b){
        int x=(a.l-1)/B,y=(b.l-1)/B;
        if(x!=y){
            return x<y;
        }
        return x&1?a.r>b.r:a.r<b.r; // Alternate right-end direction.
    });
    vector<int>frequency(values.size(),0),answer(q);
    int left=1,right=0,distinct=0; // Empty active interval.
    auto add=[&](int i){
        if(frequency[a[i]]++==0){
            ++distinct;
        }
    };
    auto remove=[&](int i){
        if(--frequency[a[i]]==0){
            --distinct;
        }
    };
    for(const auto&query:queries){
        while(left>query.l){
            add(--left);
        }
        while(right<query.r){
            add(++right);
        }
        while(left<query.l){
            remove(left++);
        }
        while(right>query.r){
            remove(right--);
        }
        answer[query.id]=distinct;
    }
    for(int x:answer){
        cout<<x<<'\n';
    }
}

Complexity analysis

Compression costs O(n log n), query sorting O(q log q), and pointer movement O(n²/B + qB + n) for O(1) add/remove. B≈√n gives O((n+q)√n) movement, a standard convenient choice when n and q are comparable; a different B can balance highly unequal sizes. O(n+q) memory stores compressed values, frequencies, queries and answers.

Example input and output

Read n q (n≥1), n signed int values, then q intervals l r with 1≤l≤r≤n. Print each distinct-count answer in original query order.

Input

5 3
1 2 1 3 2
1 3
2 5
4 5

Output

2
3
2

The queried sets of values are {1,2}, {1,2,3} and {2,3}. Repeated occurrences count only once.

Practical applications

Use for static range distinct counts, equal-pair counts and frequency-based scores with cheap endpoint changes. A Fenwick last-occurrence sweep also solves static distinct counts in O((n+q) log n) and is preferable for that specific task; Mo illustrates a reusable mechanism for statistics that lack such a sweep. Choose an online range structure if queries depend on prior answers.

Check your understanding

What makes this version of Mo’s algorithm applicable?

Put it into practice

Change the statistic to the number of equal unordered index pairs inside a range.