Cet algorithme, connu sous le nom de "Mo's algorithm with updates" ou "Mo's algorithm on trees" (bien que cette implémentation ne soit pas spécifique aux arbres), permet de gérer efficacement des requêtes sur un tableau qui subit également des modifications. La complexité temporelle typique est de O(n^(5/3)), en supposant que le nombre d'éléments du tableau, le nombre de requêtes et le nombre de modifications sont tous égaux à n.

Structure de Données et Préparation

L'approche repose sur la pré-computation et la gestion hors ligne des requêtes. Les modifications sont également traitées hors ligne et associées à un "temps" d'exécution.

Structure de Requête :

Chaque requête est définie par son intervalle [l, r] et le moment t auquel elle doit être évaluée. Le critère de tri des requêtes est crucial pour l'efficacité de l'algorithme. Il est basé sur des blocs de taille B :

• Clé primaire : Le bloc contenant l'extrémité gauche l (l / B), trié par ordre croissant.
• Clé secondaire : Le bloc contenant l'extrémité droite r (r / B), trié par ordre croissant.
• Clé tertiaire : Le temps t auquel la requête doit être appliquée, trié par ordre croissant.

Ce tri permet de mniimiser les déplacements du curseur de fenêtre (l et r) et du pointeur temporel (t).

Structure de Modification :

Une modification est enregistrée par la position p et la nouvelle valeur x.

Fonctions Clés de Déplacement

Les fonctions add() et del() sont responsables de la mise à jour de la réponse courante res lorsque la fenêtre de requête s'étend ou se contracte d'un élément.

void add(int val) {
   // Logique pour ajouter 'val' à la fenêtre courante et mettre à jour 'res'
   // Par exemple, si 'res' compte les fréquences d'éléments :
   if (count[val] == 0) current_answer++;
   count[val]++;
}

void del(int val) {
   // Logique pour retirer 'val' de la fenêtre courante et mettre à jour 'res'
   // Par exemple, si 'res' compte les fréquences d'éléments :
   count[val]--;
   if (count[val] == 0) current_answer--;
}
   

La fonction changeT(l, r, t) gère le passage d'un état temporel à un autre. Elle prend en compte si la modification à l'instant t se situe dans l'intervalle actuel [l, r].

void changeT(int current_l, int current_r, int target_t) {
   // Récupère la modification à l'instant target_t
   auto& modification = modifications[target_t];
   int pos = modification.p;
   int new_val = modification.x;
   int old_val = original_array[pos]; // Valeur avant modification

   // Si la position modifiée est dans l'intervalle actuel [current_l, current_r]
   if (pos >= current_l && pos <= current_r) {
       // Applique l'effet de l'ajout de la nouvelle valeur
       add(new_val);
       // Applique l'effet de la suppression de l'ancienne valeur
       del(old_val);
   }
   // Met à jour le tableau original avec la nouvelle valeur (ou l'ancienne si on revient en arrière)
   swap(original_array[pos], modifications[target_t].x); // 'x' contient la valeur avant ce swap
}
   

Algorithme Principal (solve())

1. Lecture des entrées : Lire la taille du tableau n et le nombre d'opérations m. Lire le tableau initial a.
2. Enregistrement des opérations : Parcourir les m opérations. Si c'est une requête ('Q'), l'enregistrer avec l'état actuel du temps (rcnt). Si c'est une modification ('M'), l'enregistrer et incrémenter le compteur de temps rcnt.
3. Calcul de la taille de bloc B : B = pow(n, 2.0 / 3.0). Assurer que B n'est pas nul.
4. Tri des requêtes : Trier le tableau des requêtes Q selon le critère défini précédemment.
5. Traitement des requêtes : Initialiser les pointeurs de fenêtre l = 1, r = 0 et le pointeur temporel t = 0. Parcourir les requêtes triées :
   • Ajuster la fenêtre [l, r] pour correspondre à la fenêtre de la requête actuelle [Q[i].l, Q[i].r] en appelant add() et del(). L'ordre est important : d'abord étendre, puis réduire.
   • Ajuster le temps t pour correspondre au temps de la requête actuelle Q[i].t en appelant changeT(). L'ordre est également important ici.
   • Enregistrer la réponse calculée (res) pour la requête courante dans ans[Q[i].id].
6. Affichage des résultats : Afficher les réponses stockées dans le tableau ans dans l'ordre original des requêtes.

Exemple de Mise en Œuvre

L'exemple de code fourni implémente cette logique en C++. Il utilise des structuers pour les requêtes et les modifications, ainsi qu'un tableau auxiliaire num[] pour le suivi des fréquences d'éléments afin de calculer la réponse res.

Notez que les fonctions add() et del() dans l'exemple de code calculent spécifiquement le nombre d'éléments uniques dans l'intervlale. La fonction changeT() gère correctement les mises à jour et les annulations en utilisant swap() pour permuter la valeur actuelle et la valeur enregistrée dans la structure de modification.