Énoncé du problème

On dispose d'une grille de dimensions n × m (avec n, m ≤ 10⁹). Initialement, k cellules sont enflammées. Le feu se propage selon la connectivité 8 (distance de Tchebychev), c'est-à-dire qu'après t unités de temps, toute cellule (x', y') telle que max(|x - x'|, |y - y'|) ≤ t est également enflammée.

L'objectif est d'allumer une cellule supplémentaire au départ pour minimiser le temps nécessaire à la combustion complète de la grille. Il s'agit donc de minimiser le moment où la dernière cellule s'enflamme.

La stratégie naturelle consiste à effectuer une recherche dichotomique sur le temps t. Pour chaque valeur testée, on calcule l'étendue (en abscisses et ordonnées) des celllules non encore couvertes par les carrés de propagation. Si le maximum des deux étendues ne dépasse pas 2t, alors un unique point d'allumage supplémentaire peut couvrir tout le reste.

Une approche classique en O(k² log w) repose sur la discrétisation et un tableau de différences. On présente ici une méthode plus efficace.

Version renforcée et complexité améliorée

Considérons une version renforcée où k ≤ 10⁵ et n, m ≤ 10¹⁸. Le principe reste identique : on effectue une recherche dichotomique sur le temps, et chaque point d'incendie génère un carré de demi-côté t. Il faut alors déterminer l'étendue des zones non couvertes par l'union de ces carrés, ce qui s'apparente à la détermination des points du contour.

On adopte une approche par ligne de balayage horizontale (on note (x, y) la ligne x, colonne y). Les quatre sommets de chaque carré sont discrétisés, puis on maintient, au fil du balayage, les extrêmes en y des zones non couvertes pour chaque coordonnée x pertinente.

Maintien de l'étendue en ordonnées

Pour chaque position de balayage, on souhaite connaître le y minimum et le y maximum non couverts. On utilise un segment tree sans propagation descendante (push_down), semblable à celui employé dans l'union de surfaces.

Pour chaque nœud couvrant l'intervalle [a, b], on maintient trois informations :

• cover[a, b] : nombre de fois où l'intervalle est entièrement recouvert (comme dans un segment tree classique de surface).
• lo[a, b] : la plus petite ordonnée non couverte dans l'intervalle, ou +∞ si tout est couvert.
• hi[a, b] : la plus grande ordonnée non couverte, ou -∞ si tout est couvert.

La racine fournit directement lo[1, N] et hi[1, N], donnant les extrêmes en y pour la position de balayage courante.

La remontée (push_up) se gère ainsi :

• Si cover ≠ 0, alors lo = +∞ et hi = -∞ (tout est couvert).
• Sinon, pour un nœud interne, on combine les enfants : lo = min(lo_gauche, lo_droit) et hi = max(hi_gauche, hi_droit).
• Pour une feuille non couverte, lo = hi = position de la feuille.

void remonte(int noeud) {
    if (cov[noeud] != 0) {
        minY[noeud] = INF;
        maxY[noeud] = -INF;
        return;
    }
    int g = noeud * 2, d = g + 1;
    if (deb[noeud] == fin[noeud]) {
        minY[noeud] = maxY[noeud] = deb[noeud];
        return;
    }
    minY[noeud] = min(minY[g], minY[d]);
    maxY[noeud] = max(maxY[g], maxY[d]);
}

Obtention des extrêmes en abscisses

Plutôt que de relancer un balayage vertcial ou de faire pivoter les coordonnées, on peut exploiter directement les résultats déjà calculés :

• Le premier x où maxY[racine] ≠ -∞ corrrespond au x_min.
• Le dernier x où maxY[racine] ≠ -∞ correspond au x_max.

En effet, maxY[racine] = -∞ signifie que la ligne entière est couverte. On combine ensuite les étendues en x et en y : si chacune est ≤ 2t, le point d'allumage supplémentaire peut tout couvrir.

Points d'attention

1. Les quatre coins de la grille globale doivent être inclus dans la discrétisation.
2. Pour un rectangle (x1, y1, x2, y2), l'événement de fin doit être placé en x2 + 1 (et non x2), conformément au principe de différence.
3. Les valeurs x1 - 1 de chaque carré doivent aussi être discrétisées, car elles peuvent constituer des extremums non couverts.
4. Ne pas inclure 0 dans la discrétisation mentionnée ci-dessus.
5. Taille du segment tree : prévoir au moins 12k nœuds, chaque rectangle pouvant générer jusqu'à 3 points significatifs.

Implémentation

On présente ici les composantes principales : structures de données, segment tree, ligne de balayage et fonction de vérification.

struct Source {
    long long ligne, col;
} src[MAXN];

struct Evenement {
    long long pos, debut, fin;
    int delta;
    bool operator<(const Evenement& autre) const {
        return pos < autre.pos;
    }
} evts[MAXN << 1];

vector<long long> axeX, axeY;

struct Noeud {
    int couverture;
    long long valMin, valMax, g, d;
    void reinit() {
        couverture = 0;
        valMin = INF_VAL;
        valMax = -INF_VAL;
    }
    void appliquer(int delta) {
        couverture += delta;
        if (couverture != 0) {
            valMin = INF_VAL;
            valMax = -INF_VAL;
        }
    }
} arbre[MAXN << 4];

void remonter(int nd) {
    if (arbre[nd].couverture != 0) {
        arbre[nd].valMin = INF_VAL;
        arbre[nd].valMax = -INF_VAL;
        return;
    }
    long long g = arbre[nd].g, d = arbre[nd].d;
    int fg = nd * 2, fd = fg + 1;
    if (g == d) {
        arbre[nd].valMin = arbre[nd].valMax = g;
        return;
    }
    arbre[nd].valMin = min(arbre[fg].valMin, arbre[fd].valMin);
    arbre[nd].valMax = max(arbre[fg].valMax, arbre[fd].valMax);
}

void construire(int nd, long long g, long long d) {
    arbre[nd].g = g;
    arbre[nd].d = d;
    arbre[nd].couverture = 0;
    if (g == d) { arbre[nd].valMin = arbre[nd].valMax = g; return; }
    long long mi = (g + d) / 2;
    construire(nd * 2, g, mi);
    construire(nd * 2 + 1, mi + 1, d);
    remonter(nd);
}

void modifier(int nd, long long g, long long d, int delta) {
    if (g <= arbre[nd].g && arbre[nd].d <= d) {
        arbre[nd].appliquer(delta);
        remonter(nd);
        return;
    }
    long long mi = (arbre[nd].g + arbre[nd].d) / 2;
    if (g <= mi) modifier(nd * 2, g, d, delta);
    if (d > mi) modifier(nd * 2 + 1, g, d, delta);
    remonter(nd);
}

bool verifier(long long duree) {
    axeX.clear(); axeY.clear();
    int nbEvts = 0;
    axeX.push_back(1);
    axeX.push_back(nbLignes);
    axeX.push_back(nbLignes + 1);
    axeY.push_back(1);
    axeY.push_back(nbCols);
    axeY.push_back(nbCols + 1);

    for (int i = 1; i <= nbSources; i++) {
        long long xg = max(src[i].ligne - duree, 1LL);
        long long xd = min(src[i].ligne + duree, nbLignes);
        long long yb = max(src[i].col - duree, 1LL);
        long long yh = min(src[i].col + duree, nbCols);

        if (xg > 1) axeX.push_back(xg - 1);
        axeX.push_back(xg);
        axeX.push_back(xd + 1);
        axeY.push_back(yb);
        axeY.push_back(yh);
        axeY.push_back(yh + 1);

        nbEvts++;
        evts[nbEvts] = {xg, yb, yh, 1};
        nbEvts++;
        evts[nbEvts] = {xd + 1, yb, yh, -1};
    }
    sort(axeX.begin(), axeX.end());
    sort(axeY.begin(), axeY.end());
    axeX.erase(unique(axeX.begin(), axeX.end()), axeX.end());
    axeY.erase(unique(axeY.begin(), axeY.end()), axeY.end());
    sort(evts + 1, evts + nbEvts + 1);

    construire(1, 0, (int)axeY.size() - 1);

    int ptr = 1;
    long long xMin = INF_VAL, xMax = -INF_VAL;
    long long yMin = INF_VAL, yMax = -INF_VAL;

    for (int i = 0; i < (int)axeX.size(); i++) {
        if (axeX[i] > nbLignes) break;
        while (ptr <= nbEvts && evts[ptr].pos == axeX[i]) {
            int idb = lower_bound(axeY.begin(), axeY.end(), evts[ptr].debut) - axeY.begin();
            int idh = lower_bound(axeY.begin(), axeY.end(), evts[ptr].fin) - axeY.begin();
            modifier(1, idb, idh, evts[ptr].delta);
            ptr++;
        }
        if (arbre[1].valMax > -INF_VAL / 2) {
            xMin = min(xMin, axeX[i]);
            xMax = max(xMax, axeX[i]);
            yMax = max(yMax, axeY[arbre[1].valMax]);
        }
        if (arbre[1].valMin < INF_VAL / 2) {
            yMin = min(yMin, axeY[arbre[1].valMin]);
        }
    }
    return (yMax - yMin <= 2 * duree && xMax - xMin <= 2 * duree);
}