Princpies Fondamnetaux

Le traitement des intervalles repose sur plusieurs piliers algorithmiques selon la nature de la requête :

• Monotonie et Sommes : Si l'on doit calculer des sommes sur des segments, la somme de préfixes est indispensable.
• Mises à jour de plages : Pour appliquer une opération sur chaque élément d'un intervalle $[L, R]$, on utilise un tableau de différences (difference array).
• Discrétisation : Lorsque les coordonnées sont trop larges (ex: $10^9$) mais le nombre de points est réduit ($10^5$), on mappe les coordonnées réelles vers des indices compacts.
• Intersection d'intervalles : Pour deux intervalles $[a, b]$ et $[c, d]$, la longueur de l'intersection est donnée par $\max(0, \min(b, d) - \max(a, c) + 1)$.

1. Découpage d'un tableau (Prefix Sum & Hash)

L'objectif est de trouver un point de coupure tel que les sommes de segments spécifiques respectent une condition. L'utilisation d'un unordered_set permet de vérifier l'existence d'une somme de préfixe en temps constant.

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long LL;

void resoudre() {
    int n;
    cin >> n;
    vector<LL> p_sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        p_sum[i] = p_sum[i - 1] + val;
    }

    unordered_set<LL> vus;
    vus.insert(p_sum[1]);
    
    for (int i = 2; i < n; i++) {
        LL sum_droite = p_sum[n] - p_sum[i];
        if (vus.count(sum_droite)) {
            cout << sum_droite << endl;
            return;
        }
        vus.insert(p_sum[i]);
    }
}

2. Triplets Croissants (Recherche Binaire)

Pour trouver le nombre de triplets $(a_i, b_j, c_k)$ tels que $a_i < b_j < c_k$, on trie les trois tableaux et on effectue une recherche binaire pour chaque élément du tableau central $B$.

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

using namespace std;

long long calculer_triplets() {
    int n;
    cin >> n;
    vector<int> A(n), B(n), C(n);
    for (int &x : A) cin >> x;
    for (int &x : B) cin >> x;
    for (int &x : C) cin >> x;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());

    long long total = 0;
    for (int cible : B) {
        auto it_a = lower_bound(A.begin(), A.end(), cible);
        long long count_a = distance(A.begin(), it_a);
        
        auto it_c = upper_bound(C.begin(), C.end(), cible);
        long long count_c = n - distance(C.begin(), it_c);
        
        total += count_a * count_c;
    }
    return total;
}

3. Discrétisation avec Map (Peinture de clôture)

Quand les positions sont éparses sur un axe très long, std::map agit comme un tableau de différences auto-discrétisé, car il maintient les clés triées.

#include <iostream>
#include <map>

using namespace std;

void calculer_couverture() {
    int n;
    cin >> n;
    map<int, int> diff;
    int pos_actuelle = 0;

    for (int i = 0; i < n; i++) {
        int distance;
        char direction;
        cin >> distance >> direction;
        
        int gauche, droite;
        if (direction == 'R') {
            gauche = pos_actuelle;
            droite = pos_actuelle + distance;
            pos_actuelle += distance;
        } else {
            gauche = pos_actuelle - distance;
            droite = pos_actuelle;
            pos_actuelle -= distance;
        }
        diff[gauche]++;
        diff[droite]--;
    }

    int segments_couverts = 0;
    int accumulation = 0;
    int prec_x = diff.begin()->first;

    for (auto const& [x, v] : diff) {
        if (accumulation >= 2) {
            segments_couverts += (x - prec_x);
        }
        accumulation += v;
        prec_x = x;
    }
    cout << segments_couverts << endl;
}

4. Propriété des Intervalles Consécutifs

Un intervalle $[i, j]$ d'une permutation contient des nombres consécutifs si et seulement si :
max(A[i...j]) - min(A[i...j]) == j - i.

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

using namespace std;

int compter_intervalles_consecutifs(int n, const vector<int>& arr) {
    int nb_valides = 0;
    for (int i = 0; i < n; i++) {
        int min_val = 1e9, max_val = -1e9;
        for (int j = i; j < n; j++) {
            min_val = min(min_val, arr[j]);
            max_val = max(max_val, arr[j]);
            if (max_val - min_val == j - i) {
                nb_valides++;
            }
        }
    }
    return nb_valides;
}

5. Couverture d'Intervalle (Algorithme Glouton)

Pour couvrir un segment $[target\_st, target\_ed]$ avec le minimum d'intervalles :

1. Trier les intervalles par borne gauche.
2. Parmi tous les intervalles commençant avant ou à la position actuelle, choisir celui qui s'étend le plus loin à droite.
3. Mettre à jour la position actuelle et répéter.

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

using namespace std;

struct Segment {
    int l, r;
    bool operator<(const Segment& w) const { return l < w.l; }
};

int resoudre_couverture(int start, int end, vector<Segment>& segments) {
    sort(segments.begin(), segments.end());
    int res = 0;
    bool possible = false;

    for (int i = 0; i < segments.size(); i++) {
        int j = i, max_r = -2e9;
        while (j < segments.size() && segments[j].l <= start) {
            max_r = max(max_r, segments[j].r);
            j++;
        }

        if (max_r < start) break;
        
        res++;
        if (max_r >= end) {
            possible = true;
            break;
        }
        
        start = max_r;
        i = j - 1;
    }
    return possible ? res : -1;
}