Présentation de l'algorithme

L'algorithme de Mo est une technique offline utilisée pour résoudre efficacement des requêtes sur des intervalles. Il s'appuie souvent sur une décomposition en blocs (ou sqrt decomposition) afin d'optimiser les transitions entre intervalles.

Problèmes typiques

• Nombre de paires d'éléments égaux dans un intervalle
• Valeur majoritaire (mode) dans un intervalle

Exemple 1 : Paires de chaussettes identiques

Énoncé simplifié

On dispose d'une séquence de N chaussettes, chacune ayant une couleur donnée par un entier. Pour M requêtes de la forme [L, R], on doit calculer la probabilité que deux chaussettes tirées au hasard dans cet intervalle soient de même couleur. Le résultat doit être affiché sous forme de fraction irréductible A/B. Si L = R, la réponse est 0/1.

Analyse

Dans un intervalle de taille len = R - L + 1, le nombre total de paires possibles est len * (len - 1) / 2. Le numérateur est le nombre de paires d'indices (i, j) tels que a[i] = a[j] et L ≤ i < j ≤ R.

Ce comptage peut être mis à jour dynamiquement lorsqu'on ajoute ou retire un élément à l'intervalle courant. En effet, si une couleur c apparaît cnt fois, alors elle contribue cnt * (cnt - 1) / 2 paires. Lorsqu’on insère une nouvelle occurrence de c, la conrtibution devient (cnt + 1) * cnt / 2, soit une augmentation de cnt.

Implémentation avec l’algorithme de Mo

Les requêtes sont triées selon une stratégie en blocs : - Diviser l’axe des indices en blocs de taille B ≈ N / √M. - Trier les requêtes d’abord par indice de bloc de L, puis par R (croissant si même bloc, décroissant sinon pour certaines variantes).

On maintient un intervalle courant [l, r] et on le déplace progressivement vers chaque requête tout en mettant à jour un tableau de fréquences freq[] et la valeur actuelle du numérateur.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 50010;

struct Query {
    int l, r, id;
};

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> color(n + 1);
    for (int i = 1; i <= n; ++i) cin >> color[i];

    vector<Query> queries(m);
    vector<ll> total_pairs(m), ans_num(m);

    for (int i = 0; i < m; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
        ll len = queries[i].r - queries[i].l + 1;
        total_pairs[i] = len * (len - 1) / 2;
    }

    int block_size = max(1, (int)(n / sqrt(m)));
    sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        if (a.l / block_size != b.l / block_size)
            return a.l < b.l;
        return (a.l / block_size & 1) ? (a.r < b.r) : (a.r > b.r);
    });

    vector<int> freq(n + 1, 0);
    ll current_pairs = 0;
    int cur_l = 1, cur_r = 0;

    auto add = [&](int idx) {
        current_pairs += freq[color[idx]];
        freq[color[idx]]++;
    };
    auto remove = [&](int idx) {
        freq[color[idx]]--;
        current_pairs -= freq[color[idx]];
    };

    for (const auto& q : queries) {
        while (cur_l > q.l) add(--cur_l);
        while (cur_r < q.r) add(++cur_r);
        while (cur_l < q.l) remove(cur_l++);
        while (cur_r > q.r) remove(cur_r--);
        ans_num[q.id] = current_pairs;
    }

    for (int i = 0; i < m; ++i) {
        if (ans_num[i] == 0 || total_pairs[i] == 0) {
            cout << "0/1\n";
        } else {
            ll g = gcd(ans_num[i], total_pairs[i]);
            cout << ans_num[i] / g << '/' << total_pairs[i] / g << '\n';
        }
    }
    return 0;
}

Exemple 2 : Somme des carrés des fréquences

Énoncé

Donnée une séquence de n entiers dans [1, k], répondre à m requêtes : pour chaque intervalle [l, r], calculer Σ (fréquence(i))² pour toutes les valeurs i.

Solution

Ici, la mise à jour est encore plus simple. Si on ajoute un élément de valeur x, la contribution change de freq[x]² à (freq[x] + 1)², soit une augmentation de 2 * freq[x] + 1. De même, la suppression diminue la somme de 2 * freq[x] - 1.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 50010;

struct Query {
    int l, r, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<Query> queries(m);
    for (int i = 0; i < m; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    int block_size = max(1, (int)(n / sqrt(m)));
    sort(queries.begin(), queries.end(), [&](const Query& x, const Query& y) {
        int bx = x.l / block_size, by = y.l / block_size;
        if (bx != by) return bx < by;
        return (bx & 1) ? (x.r < y.r) : (x.r > y.r);
    });

    vector<int> cnt(k + 1, 0);
    ll current = 0;
    int l = 1, r = 0;
    vector<ll> ans(m);

    auto expand = [&](int idx) {
        current -= (ll)cnt[a[idx]] * cnt[a[idx]];
        cnt[a[idx]]++;
        current += (ll)cnt[a[idx]] * cnt[a[idx]];
    };
    auto shrink = [&](int idx) {
        current -= (ll)cnt[a[idx]] * cnt[a[idx]];
        cnt[a[idx]]--;
        current += (ll)cnt[a[idx]] * cnt[a[idx]];
    };

    for (const auto& q : queries) {
        while (l > q.l) expand(--l);
        while (r < q.r) expand(++r);
        while (l < q.l) shrink(l++);
        while (r > q.r) shrink(r--);
        ans[q.id] = current;
    }

    for (ll x : ans) cout << x << '\n';
    return 0;
}