Implémentation de base

Voici une implémentation typique de l'algorithme de Mo standard. Notez que le tableau des requêtes est trié selon un ordre qui optimise les déplacements successifs.

#include #include #include #include

const int MAX_N = 200000;

int main() { int n, m, blockSize; std::cin >> n; blockSize = static_cast(std::sqrt(n)); std::vector data(n); for (int i = 0; i < n; ++i) std::cin >> data[i]; std::cin >> m; struct Query { int left, right, id; }; std::vector<Query> queries(m); for (int i = 0; i < m; ++i) { std::cin >> queries[i].left >> queries[i].right; queries[i].id = i; queries[i].left--; // Conversion en indexation 0 queries[i].right--; } std::sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) { if (a.left / blockSize != b.left / blockSize) return a.left < b.left; return (a.left / blockSize % 2) ? (a.right < b.right) : (a.right > b.right); });

std::vector<int> frequency(MAX_N, 0);
std::vector<int> answers(m);
int currentLeft = 0, currentRight = -1, distinctCount = 0;

auto add = [&](int pos) {
    if (frequency[data[pos]] == 0) distinctCount++;
    frequency[data[pos]]++;
};
auto remove = [&](int pos) {
    frequency[data[pos]]--;
    if (frequency[data[pos]] == 0) distinctCount--;
};

for (const auto& q : queries) {
    while (currentLeft > q.left) add(--currentLeft);
    while (currentRight < q.right) add(++currentRight);
    while (currentLeft < q.left) remove(currentLeft++);
    while (currentRight > q.right) remove(currentRight--);
    answers[q.id] = distinctCount;
}
for (int ans : answers) std::cout << ans << '\n';
return 0;

}

</details>Problèmes d'application
-----------------------

### Nombres distincts dans un intervalle

Pour compter les valeurs distinctes, on maintient un tableau de fréquences. Lors de l'ajout d'un élément, si sa fréquence passe de 0 à 1, on incrémente le compteur ; lors de la suppression, si elle passe de 1 à 0, on le décrémente.

### Probabilité d'égalité dans un intervalle

Dans le problème des chaussettes, on calcule la probabilité que deux éléments tirés au hasard soeint identiques. On utilise un tableau de fréquences pour accumuler les contributions lors des ajouts et suppressions.

### Nombre de sous-intervalles avec une somme XOR égale à k

En utilisant un tableau de préfixes XOR, on transforme le problème en compter les paires (x,y) tels que s\_x ⊕ s\_y = k. Un tableau de fréquences enregistre les occurrences des valeurs de préfixe, et les mises à jour modifient la réponse en fonction de cnt\[x ⊕ k\].

### Mode d'un intervalle

Pour trouver la fréquence maximale d'un élément dans un intervalle, on maintient deux tableaux : cnt pour les occurrences de chaque valeur, et t pour le nombre de valeurs ayant une occurrence donnée. Les mises à jour de l'ordre maximal sont gérées lors des ajouts et suppressions.

Algorithme de Mo avec modifications
-----------------------------------

Pour les problèmes avec des modifications ponctuelles, on introduit une dimension temporelle. Les requêtes sont triées en incluant le temps de modification, avec une taille de bloc optimlae de n^(2/3), donnant une complexité de O(n^(5/3)).

<details><summary>Afficher le code pour Mo avec modifications</summary>```

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

const int MAX_N = 200000;

int main() {
    int n, m, blockSize;
    std::cin >> n >> m;
    blockSize = static_cast<int>(std::pow(n, 2.0/3));
    std::vector<int> array(n);
    for (int i = 0; i < n; ++i) std::cin >> array[i];

    struct Query { int left, right, time, id; };
    std::vector<Query> queries;
    struct Update { int pos, newValue; };
    std::vector<Update> updates;
    int currentTime = 0;

    for (int i = 0; i < m; ++i) {
        char type;
        std::cin >> type;
        if (type == 'Q') {
            int l, r;
            std::cin >> l >> r;
            queries.push_back({l-1, r-1, currentTime, static_cast<int>(queries.size())});
        } else {
            int pos, val;
            std::cin >> pos >> val;
            updates.push_back({pos-1, val});
            currentTime++;
        }
    }

    std::sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
        if (a.left / blockSize != b.left / blockSize) return a.left < b.left;
        if (a.right / blockSize != b.right / blockSize) return a.right < b.right;
        return (a.right / blockSize % 2) ? (a.time < b.time) : (a.time > b.time);
    });

    std::vector<int> freq(MAX_N, 0);
    std::vector<int> answers(queries.size());
    int curL = 0, curR = -1, curT = 0, distinct = 0;

    auto add = [&](int pos) {
        if (freq[array[pos]] == 0) distinct++;
        freq[array[pos]]++;
    };
    auto remove = [&](int pos) {
        freq[array[pos]]--;
        if (freq[array[pos]] == 0) distinct--;
    };
    auto applyUpdate = [&](int time, const Query& q, bool forward) {
        auto& upd = updates[time];
        if (upd.pos >= q.left && upd.pos <= q.right) {
            remove(upd.pos);
            add(upd.pos); // Appliquer la nouvelle valeur
        }
        std::swap(array[upd.pos], upd.newValue);
    };

    for (const auto& q : queries) {
        while (curT > q.time) applyUpdate(--curT, q, false);
        while (curT < q.time) applyUpdate(curT++, q, true);
        while (curL > q.left) add(--curL);
        while (curR < q.right) add(++curR);
        while (curL < q.left) remove(curL++);
        while (curR > q.right) remove(curR--);
        answers[q.id] = distinct;
    }
    for (int ans : answers) std::cout << ans << '\n';
    return 0;
}

Dans certains problèmes comme la recherche du mex des fréquences, on combine Mo avec modifications en utilisant des structures de données adaptatives. Les solutions imppliquent souvent un tri complexe et des mises à jour soigneuses pour maintenir la complexité.