Mo's Algorithm

function moAlgorithm(n, queries, add, remove, getAnswer) {
    // queries: [{l, r, idx}]
    const block = Math.ceil(Math.sqrt(n));

    // Sort: by block of l, then by r (alternating for cache efficiency)
    queries.sort((a, b) => {
        const ba = Math.floor(a.l / block), bb = Math.floor(b.l / block);
        if (ba !== bb) return ba - bb;
        return ba % 2 === 0 ? a.r - b.r : b.r - a.r; // alternating
    });

    const answers = new Array(queries.length);
    let curL = 0, curR = -1;

    for (const {l, r, idx} of queries) {
        // Expand/contract to [l, r]
        while (curR < r) add(++curR);
        while (curL > l) add(--curL);
        while (curR > r) remove(curR--);
        while (curL < l) remove(curL++);
        answers[idx] = getAnswer();
    }
    return answers;
}

// Example: count distinct elements in range [l, r]
// add(i): freq[arr[i]]++; if freq[arr[i]] === 1: distinctCount++
// remove(i): freq[arr[i]]--; if freq[arr[i]] === 0: distinctCount--
// getAnswer(): return distinctCount