L'objectif de ce problème est de partitionner un tableau d'entiers donné en le nombre maximal de sous-tableaux contigus. Pour chaque sous-tableau résultant, nous calculons sa valeur MEX (Minimum Excluded value), qui est le plus petit entier non négatif absent de cet ensemble. Le but est de construire un nouveau tableau contenant ces valeurs MEX, et de maximiser sa longueur.

La stratégie principale consiste à identifier le MEX du tableau entier initial. Ce MEX (appelons-le mex\_cible\_global) sera la valeur que nous essayerons d'atteindre pour le premier sous-tableau. Nous parcourons le tableau, accumulant des éléments dans un sous-tableau temporaire. Au fur et à mesure que nous ajoutons des éléments, nous mettons à jour le MEX du sous-tableau courant (mex\_prefixe\_actuel) et surveillons également un candidat pour le prochain mex\_cible\_global.

Le candidat pour le prochain mex\_cible\_global (prochain\_mex\_possible) est mis à jour chaque fois que nous traitons un élément arr\[i\]. Si arr\[i\] est inférieur à l'actuel mex\_cible\_global et qu'il s'agit de sa dernière occurrence dans la partie restante du tableau, alors arr\[i\] devient un candidat potentiel pour le mex\_cible\_global du prochain segment. Cela est dû au fait que la consommation de arr\[i\] rendra ce nombre absent du reste du tableau, faisant potentiellement de lui le plus petit entier manquant.

Lorsqu'un sous-tableau temporaire atteint un mex\_prefixe\_actuel égal au mex\_cible\_global, nous avons trouvé un segment valide. Nous ajoutons alors ce mex\_cible\_global à notre liste de résultats, réinitialisons les compteurs pour le sous-tableau temporaire, et mettons à jour le mex\_cible\_global pour le segment suivant en utilisant notre prochain\_mex\_possible accumulé. Le prochain\_mex\_possible est ensuite réinitialisé à cette nouvelle valeur de mex\_cible\_global.

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

const int VALEUR_MAXIMALE_POSSIBLE = 300005; // Maximum value for elements + 1

void resoudreProblemeMEX() {
    int n;
    std::cin >> n;
    std::vector<int> tableau_entree(n);
    std::vector<int> compteurs_valeurs_restantes(VALEUR_MAXIMALE_POSSIBLE, 0); // Compteurs pour les valeurs dans la partie restante du tableau

    for (int i = 0; i < n; ++i) {
        std::cin >> tableau_entree[i];
        compteurs_valeurs_restantes[tableau_entree[i]]++;
    }

    // Déterminer le MEX initial global de l'ensemble du tableau
    int mex_cible_global = 0;
    while (mex_cible_global < VALEUR_MAXIMALE_POSSIBLE && compteurs_valeurs_restantes[mex_cible_global] > 0) {
        mex_cible_global++;
    }

    int mex_prefixe_actuel = 0; // MEX du segment actuellement accumulé
    int prochain_mex_possible_cible = mex_cible_global; // Candidat pour le MEX cible du *prochain* segment
    std::vector<int> compteurs_segment_actuel(VALEUR_MAXIMALE_POSSIBLE, 0); // Compteurs pour les valeurs dans le segment actuel
    std::vector<int> liste_resultats_mex;

    for (int i = 0; i < n; ++i) {
        compteurs_segment_actuel[tableau_entree[i]]++;
        compteurs_valeurs_restantes[tableau_entree[i]]--; // Cet élément fait maintenant partie du segment actuel

        // Mettre à jour le mex_prefixe_actuel basé sur les compteurs_segment_actuel
        while (mex_prefixe_actuel < VALEUR_MAXIMALE_POSSIBLE && compteurs_segment_actuel[mex_prefixe_actuel] > 0) {
            mex_prefixe_actuel++;
        }

        // Si tableau_entree[i] est un élément critique pour le mex_cible_global (c'est-à-dire sa dernière occurrence)
        // et il est plus petit que le mex_cible_global actuel, il devient un candidat pour le prochain MEX cible.
        if (tableau_entree[i] < mex_cible_global && compteurs_valeurs_restantes[tableau_entree[i]] == 0) {
            prochain_mex_possible_cible = std::min(prochain_mex_possible_cible, tableau_entree[i]);
        }

        // Si le MEX du segment actuel correspond au mex_cible_global, nous avons trouvé un segment valide
        if (mex_prefixe_actuel == mex_cible_global) {
            liste_resultats_mex.push_back(mex_cible_global);

            // Réinitialiser les compteurs pour le segment suivant
            std::fill(compteurs_segment_actuel.begin(), compteurs_segment_actuel.end(), 0); // Effacer efficacement
            mex_prefixe_actuel = 0; // Réinitialiser le MEX du préfixe

            // Le MEX cible pour le *prochain* segment est déterminé
            mex_cible_global = prochain_mex_possible_cible;
            // Et réinitialiser le candidat pour le segment d'après
            prochain_mex_possible_cible = mex_cible_global;
        }
    }

    std::cout << liste_resultats_mex.size() << std::endl;
    for (size_t i = 0; i < liste_resultats_mex.size(); ++i) {
        std::cout << liste_resultats_mex[i] << (i == liste_resultats_mex.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        resoudreProblemeMEX();
    }
    return 0;
}

Minimisation des Exposants pour Séquences Croissantes

Ce problème nous demande de trouver une séquence d'exposants non négatifs, k\_1, k\_2, ..., k\_n, pour un tableau a donné, de sorte que la nouvelle séquence b\_i = a\_i \* 2^{k\_i} soit non décroissante (c'est-à-dire b\_1 ≤ b\_2 ≤ ... ≤ b\_n). La condition initiale est k\_1 = 0. Notre objectif est de minimiser la somme totale des exposants, ∑ k\_i.

Pour chaque élément a\_i (à partir de i=2), nous devons choisir k\_i de manière à ce que a\_i \* 2^{k\_i} ≥ a\_{i-1} \* 2^{k\_{i-1}}. Nous voulons minimiser k\_i tout en satisfaisant cette condition. La variable exposant\_courant\_necessaire maintient la valeur de k\_{i-1} (l'exposant choisi pour l'élément précédent).

• Si a\_{i-1} > a\_i : L'élément précédent (brut) est plus grand que l'élément actuel (brut). Pour maintenir la conditino non décroissante, nous devons augmenter k\_i. Nous calculons combien de fois a\_i doit être doublé pour être au moins aussi grand que a\_{i-1}. Ce nombre de doublages est ajouté à exposant\_courant\_necessaire. La nouvelle valeur de exposant\_courant\_necessaire sera k\_i.
• Si a\_{i-1} ≤ a\_i : L'élément actuel (brut) est déjà plus grand ou égal à l'élément précédent (brut). Cela signifie que nous pouvons potentiellement réduire k\_i. Nous calculons combien de fois a\_{i-1} peut être doublé et rester inférieur ou égal à a\_i. Ce nombre de doublages est soustrait de exposant\_courant\_necessaire. Nous nous assurons que exposant\_courant\_necessaire ne devienne jamais négatif, car les exposants doivent être non négatifs. La nouvelle valeur de exposant\_courant\_necessaire sera k\_i.

La somme totale des exposants est mise à jour avec la valeur finale de exposant\_courant\_necessaire (qui représente k\_i pour l'élément a\_i) à chaque itération.

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

void resoudreOptimisationSequence() {
    int n;
    std::cin >> n;
    std::vector<long long> valeurs(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> valeurs[i];
    }

    long long somme_exposants_totale = 0;
    int exposant_courant_necessaire = 0; // Représente k_i pour valeurs[i]

    // Le problème exige k_1 = 0. Nous commençons donc le traitement à partir du deuxième élément (index 1).
    // exposant_courant_necessaire contient conceptuellement k_{i-1} lorsque l'on considère valeurs[i].

    for (int i = 1; i < n; ++i) {
        long long valeur_precedente_brute = valeurs[i-1];
        long long valeur_courante_brute = valeurs[i];

        if (valeur_precedente_brute > valeur_courante_brute) {
            // Si la valeur précédente (non modifiée) est supérieure à la valeur actuelle (non modifiée),
            // nous devons augmenter exposant_courant_necessaire pour satisfaire la condition non décroissante :
            // valeur_courante_brute * 2^k_i >= valeur_precedente_brute * 2^k_{i-1}
            // Avec exposant_courant_necessaire actuel comme k_{i-1}.
            // Nous avons besoin de valeur_courante_brute * 2^delta_k >= valeur_precedente_brute.
            int doublages_requis = 0;
            long long temp_valeur_courante = valeur_courante_brute;
            while (temp_valeur_courante < valeur_precedente_brute) {
                temp_valeur_courante *= 2;
                doublages_requis++;
            }
            exposant_courant_necessaire += doublages_requis;
        } else { // valeur_precedente_brute <= valeur_courante_brute
            // Si la valeur actuelle est déjà supérieure ou égale, nous pouvons essayer de diminuer exposant_courant_necessaire.
            // Nous voulons valeur_courante_brute * 2^k_i >= valeur_precedente_brute * 2^k_{i-1}
            // Et minimiser k_i.
            int reductions_possibles = 0;
            long long temp_valeur_precedente = valeur_precedente_brute;
            // Tant que la valeur précédente (potentiellment modifiée par 2) est <= la valeur courante
            // cela signifie que nous avons une marge pour réduire l'exposant actuel.
            while (temp_valeur_precedente * 2 <= valeur_courante_brute) {
                temp_valeur_precedente *= 2;
                reductions_possibles++;
            }
            exposant_courant_necessaire -= reductions_possibles;
            exposant_courant_necessaire = std::max(0, exposant_courant_necessaire); // k_i doit être non négatif
        }
        somme_exposants_totale += exposant_courant_necessaire;
    }
    std::cout << somme_exposants_totale << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        resoudreOptimisationSequence();
    }
    return 0;
}

Découverte des Nœuds Maximaux Atteignables dans un Graphe

Pour un graphe dirigé donné, ce problème demande de trouver, pour chaque nœud u, le nœud v de plus grand identifiant qui peut être atteint depuis u via un chemin dirigé. Un algorithme de parcours en profondeur (DFS) sur le graphe inversé, combiné à un balayage des nœuds par identifiant décroissant, permet de résoudre ce problème efficacement.

Nous construisons un graphe inversé où chaque arête u -> v du graphe original est représentée par une arête v -> u. Cela signifie que la liste d'adjacence inversée adj\_inverse\[v\] contiendra tous les nœuds u pour lesquels il existe une arête u -> v dans le graphe original.

L'algorithme procède comme suit :

1. Initialisez un tableau max\_atteignable\[p\] à 0 pour tous les nœuds p, qui stockera le plus grand identifiant de nœud atteignable depuis p.
2. Parcourez les nœuds de N (le plus grand identifiant) jusqu'à 1 (le plus petit identifiant). Soit i le nœud courant de ce parcours.
3. Si max\_atteignable\[i\] est encore 0, cela signifie que le nœud i n'a pas encore été marqué comme atteignable par un nœud d'identifiant supérieur. Dans ce cas, nous lançons un DFS depuis i, avec i comme candidat pour le plus grand identifiant atteignable.
4. La fonction dfs(noeud\_actuel, candidat\_max\_id) fonctionne ainsi :
   • Si max\_atteignable\[noeud\_actuel\] n'est pas 0 (déjà visité et marqué par un ID plus grand ou égal), la fonction se termine.
   • Sinon, max\_atteignable\[noeud\_actuel\] = candidat\_max\_id. Cela signifie que le noeud\_actuel peut atteindre candidat\_max\_id (car candidat\_max\_id est à l'origine du DFS ou un nœud sur le chemin).
   • Pour chaque prédécesseur p de noeud\_actuel (c'est-à-dire chaque voisin de noeud\_actuel dans le graphe inversé), appelez récursivement dfs(p, candidat\_max\_id). L'idée est que si noeud\_actuel peut atteindre candidat\_max\_id, et que p peut atteindre noeud\_actuel dans le graphe original, alors p peut aussi atteinrde candidat\_max\_id.

Grâce au parcours des nœuds de N à 1, la première fois qu'un nœud est visité, il est marqué avec le plus grand identifiant de nœud qu'il peut atteindre. Les visites ultérieures par des identifiants plus petits seront ignorées.

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

const int NOMBRE_MAX_NOEUDS = 200005;

// Liste d'adjacence inversée : adj_inverse[v] contient tous les u tels que u -> v dans le graphe original.
std::vector<std::vector<int>> liste_adj_inverse(NOMBRE_MAX_NOEUDS); 
// Stocke le plus grand identifiant de nœud atteignable depuis chaque nœud.
std::vector<int> valeur_max_atteignable_noeud(NOMBRE_MAX_NOEUDS, 0); 

void explorerNoeudsAtteignablesDFS(int noeud_actuel, int candidat_max_id) {
    if (valeur_max_atteignable_noeud[noeud_actuel] != 0) { // Si déjà visité et marqué par un ID supérieur ou égal
        return;
    }
    valeur_max_atteignable_noeud[noeud_actuel] = candidat_max_id; // Marquer noeud_actuel comme atteignable par candidat_max_id

    // Parcourir les prédécesseurs de noeud_actuel dans le graphe original
    // (qui sont les voisins de noeud_actuel dans le graphe inversé)
    for (int predecesseur : liste_adj_inverse[noeud_actuel]) {
        explorerNoeudsAtteignablesDFS(predecesseur, candidat_max_id);
    }
}

void resoudreAtteignabiliteGraphe() {
    int nb_noeuds, nb_arretes;
    std::cin >> nb_noeuds >> nb_arretes;

    // Réinitialisation des structures pour un cas de test unique (si plusieurs, cela serait dans la boucle principale)
    for(int i = 1; i <= nb_noeuds; ++i) {
        liste_adj_inverse[i].clear();
        valeur_max_atteignable_noeud[i] = 0;
    }

    for (int i = 0; i < nb_arretes; ++i) {
        int u, v;
        std::cin >> u >> v;
        // Arête de u vers v. Dans le graphe inversé, cela signifie que v a une connexion depuis u.
        liste_adj_inverse[v].push_back(u);
    }

    // Parcourir les nœuds de nb_noeuds jusqu'à 1.
    // Cela garantit que lorsqu'un nœud est visité pour la première fois,
    // il est marqué avec l'identifiant de nœud atteignable le plus grand possible.
    for (int i = nb_noeuds; i >= 1; --i) {
        // Si valeur_max_atteignable_noeud[i] est 0, cela signifie que 'i' n'a pas encore été marqué
        // par un nœud plus grand. Donc, 'i' lui-même est le nœud le plus grand atteignable pour
        // certains chemins qui se terminent à 'i'.
        if (valeur_max_atteignable_noeud[i] == 0) {
            explorerNoeudsAtteignablesDFS(i, i);
        }
    }

    for (int i = 1; i <= nb_noeuds; ++i) {
        std::cout << valeur_max_atteignable_noeud[i] << (i == nb_noeuds ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    // Le problème sur Luogu (P3916) implique un seul cas de test.
    resoudreAtteignabiliteGraphe();
    return 0;
}