Considérons un problème classique de programmation dynamique (DP) dont la transition suit la forme suivante :

\[f(i) = \min_{i-k \le j < i} \{f(j) + \max(a_{j+1}, \dots, a_i)\}\]

L'objectif est d'optimiser cette transition pour passer d'une complexité naïve de \(O(n \cdot k)\) à une complexité linéaire ou quasi-linéaire.

Approche en \(O(n \log n)\) avec Arbre de Segments

Une première optimisation consiste à utiliser un arbre de segments combiné à une pile monotone. La pile monotone maintient les valeurs de \(a\) de manière décroissante. Lorsqu'un nouvel élément \(a_i\) arrive, il peut invalider plusieurs maxima précédents. Si l'on dépile un indice \(p\), le maximum sur l'intervalle \([p+1, i]\) devient \(a_i\). Cela se traduit par une mise à jour par plage (range update) sur l'arbre de segments, tandis que la valeur de DP est obtenue par une requête de minimum sur un intervalle.

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

using namespace std;

typedef long long ll;

const ll INF = 1e18;
const int MAXN = 500005;

struct SegmentTree {
    ll tree[MAXN * 4], lazy[MAXN * 4];

    void push_down(int node) {
        if (lazy[node] != 0) {
            tree[node * 2] += lazy[node];
            lazy[node * 2] += lazy[node];
            tree[node * 2 + 1] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
            lazy[node] = 0;
        }
    }

    void update(int node, int start, int end, int l, int r, ll val) {
        if (start > end || start > r || end < l) return;
        if (start >= l && end <= r) {
            tree[node] += val;
            lazy[node] += val;
            return;
        }
        push_down(node);
        int mid = (start + end) / 2;
        update(node * 2, start, mid, l, r, val);
        update(node * 2 + 1, mid + 1, end, l, r, val);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    ll query(int node, int start, int end, int l, int r) {
        if (start > end || start > r || end < l) return INF;
        if (start >= l && end <= r) return tree[node];
        push_down(node);
        int mid = (start + end) / 2;
        return min(query(node * 2, start, mid, l, r), query(node * 2 + 1, mid + 1, end, l, r));
    }
} st;

Optimisation Linéaire : Le Baka's Trick

Pour atteindre une complexité de \(O(n)\), nous pouvons exploiter une structure de données plus efficace qu'un arbre de segments. Le "Baka's trick" repose sur l'idée de maintenir une fenêtre glissante à l'aide de deux piles ou d'une reconstruction périodique des minima préfixés et suffixés.

Lorsque la fenêtre se déplace, nous maintenons des blocs de valeurs constantes pour le maximum actuel. Si le début de la fenêtre dépasse le point de pivot (milieu), nous reconstruisons les minima pour garantir un accès en temps constant. Cette technique est similaire à la file d'attente implémentée par deux piles, mais adaptée ici pour gérer les mises à jour de maxima imposées par la pile monotone.

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7;
const int N = 1e7 + 5;

struct Bloc {
    int gauche, droite;
    ll valeur_max;
};

ll dp_table[N], min_prefix[N], puissances[N];
Bloc pile_blocs[N];
int tete = 1, queue = 0, pivot = 1;

ll calculer_valeur(int i) {
    return pile_blocs[i].valeur_max + dp_table[pile_blocs[i].gauche - 1];
}

void reconstruire() {
    if (tete > queue) {
        pivot = tete;
        return;
    }
    pivot = (tete + queue) / 2;
    for (int i = tete; i <= queue; i++) min_prefix[i] = calculer_valeur(i);
    for (int i = pivot - 1; i >= tete; i--) min_prefix[i] = min(min_prefix[i], min_prefix[i + 1]);
    for (int i = pivot + 2; i <= queue; i++) min_prefix[i] = min(min_prefix[i], min_prefix[i - 1]);
}

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

    int n, k;
    cin >> n >> k;

    puissances[0] = 1;
    for (int i = 1; i <= n; i++) puissances[i] = puissances[i - 1] * 23 % MOD;

    ll score_total = 0;
    for (int i = 1; i <= n; i++) {
        int a_i;
        cin >> a_i;

        // Gestion de la sortie de fenêtre (k)
        while (tete <= queue && pile_blocs[tete].gauche < i - k + 1) {
            if (pile_blocs[tete].droite < i - k + 1) {
                if (++tete > pivot) reconstruire();
            } else {
                pile_blocs[tete].gauche = i - k + 1;
                min_prefix[tete] = calculer_valeur(tete);
                if (tete < pivot) min_prefix[tete] = min(min_prefix[tete], min_prefix[tete + 1]);
            }
        }

        // Mise à jour monotone du maximum
        while (tete <= queue && pile_blocs[queue].valeur_max <= a_i) {
            if (--queue < pivot) reconstruire();
        }

        if (tete > queue) {
            pile_blocs[++queue] = {max(1, i - k + 1), i, (ll)a_i};
        } else {
            pile_blocs[queue + 1] = {pile_blocs[queue].droite + 1, i, (ll)a_i};
            queue++;
        }

        min_prefix[queue] = calculer_valeur(queue);
        if (queue - 1 > pivot) min_prefix[queue] = min(min_prefix[queue], min_prefix[queue - 1]);

        dp_table[i] = min(min_prefix[queue], min_prefix[tete]);
        score_total = (score_total + puissances[n - i] * (dp_table[i] % MOD)) % MOD;
    }

    cout << score_total << endl;

    return 0;
}

Dans cette implémentation, la fonction reconstruire assure que nous pouvons toujours obtenir le minimum de la DP sur la fenêtre active en \(O(1)\) après une phase de réorganisation amortie. La complexité globale est \(O(n)\) car chaque élément est ajouté et retiré de la structure un nombre constant de fois, et les reconstructions sont déclenchées proportionnellement aux éléments traités.