Mo's Algorithm

O((n + q)·√n)

Answers offline range queries by sorting them in block order and moving the [l, r] window one element at a time. Works whenever add(x) and remove(x) are cheap. This version counts distinct values per query; customize add/remove for other statistics.

// use it on

SPOJ: DQUERY ↗

Number of distinct values in each queried range, the textbook Mo's application (and what this template computes as written).

// the code

// offline range queries; example: distinct values in [l, r]
vector<int> mo(vector<int>& a, vector<array<int, 2>>& queries) {
    int n = a.size(), q = queries.size();
    int B = max(1, (int)(n / sqrt(q + 1.0)));
    vector<int> order(q), ans(q);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
        int bi = queries[i][0] / B, bj = queries[j][0] / B;
        if (bi != bj) return bi < bj;
        return (bi & 1) ? queries[i][1] > queries[j][1]
                        : queries[i][1] < queries[j][1];
    });
    vector<int> cnt(*max_element(a.begin(), a.end()) + 1, 0);
    int cur = 0, l = 0, r = -1;
    auto add = [&](int i) { if (cnt[a[i]]++ == 0) cur++; };
    auto rem = [&](int i) { if (--cnt[a[i]] == 0) cur--; };
    for (int qi : order) {
        auto [ql, qr] = queries[qi];
        while (l > ql) add(--l);
        while (r < qr) add(++r);
        while (l < ql) rem(l++);
        while (r > qr) rem(r--);
        ans[qi] = cur;
    }
    return ans;
}